Algorithms types | |
---|---|
S-D Connectivity of Uncertain Networks | |
S-D Connectivity in Random Graphs | |
Distributed Steiner Tree Construcution | |
Depth-first/Breadth-first Searching | |
Alternating Greedy Leaf Removal | |
Multicast Energy Optimization Algorithm |
This package contains the simulation codes of "Complexity vs. Optimality: Unraveling Source-Destination Connection in Uncertain Graph".
The experimental dataset is selected from Twitter ego network. All the codes are programmed in Python 3.
The algorithms proposed are used to determine the connectivity of designated source-destination pairs in uncertain network modeled as a directed graph, where each edge exists with a differnt probability, and testing each edge incurs a different cost.
For the detailed description of the uncertain networks and the proposed algorithms involved, please refer to the paper "Complexity vs. Optimality: Unraveling Source-Destination Connection in Uncertain Graph" by Xinzhe Fu, Zhiying Xu, Qianyang Peng, Luoyi Fu and Xinbing Wang. The detailed usage of each files is listed in the following.
0_gengraph: generated graph files from source data (twitter ego network).
1_mincost: the Greedy algorithm
2_adasub: the Adaptive Submodular algorithm
3_intersect: the Intersection Sort algorithm
4_optsort: the optimistic sort algorithm
5_pessort: the pessimistic sort algorithm
To run the simulations, first run the 0_gengraph and then run the corresponding algorithm files.
The results are printed in separate files.
If you find theses useful, we would be grateful if you could cite the following paper:
- Xinzhe Fu, Zhiying Xu, Qianyang Peng, Luoyi Fu and Xinbing Wang, °Complexity vs. Optimality:Unraveling Source-Destination Connection in Uncertain Graphs¡±, in Proc. of IEEE INFOCOM 2017.This package contains the simulation codes of the proosed Alternating Algorithm that can optimally determining source-destination connectivity in Erdos-Renyi (ER) random graph. Here the optimality refers to the fact that the algorithm can find out whether the designated source and destination pair is connected or not using the fewest expected number of testing steps, given that the existence of each edge is determined by one testing step.
For more details of the Alternating Algorithm, please refer to our paper "Are We Connected? Optimal Determination of Source-destination Connectivity in Random Graphs" by Luoyi Fu, Xinbing Wang and P. R. Kumar. The detailed usage of each files is listed in the following.
All the simulation codes are written by Matlab. To run the simulations, put all the three .m files in the same folder, and then run the main.m file, which can return the expected number of steps for determining S-D connecivity in different ER random graphs. Particularly, you can set the total number of nodes n and the edge existence probability p in this file according to your own preference. The results are presented in the form of figures.
If you find these useful, we would be grateful if you could cite the following two papers:
- Luoyi Fu, Xinbing Wang, P. R. Kumar,"Are We Connected? Optimal determination of source-destination connectivity in random graphs," in IEEE/ACM Transactions on Networking,2016.This package contains the simulation codes of Distributed Steiner Tree, which, alternatively, is named as Toward Source Tree (TST) construction in our paper (provided at the end) under three different node distributions: uniform distribution, exponential distribution and normal distribution. We calculate the tree length, the message complexity and the number of nodes engaged in transmission. An illustrative process of how TST is constructed is given in the following figure:
In this code, sumLength refers to the tree length, sumMsg refers to the message complexity, and sumHops refers to the number of transmitting nodes. For more details of the TST algorithm, please refer to our paper "Distributed Multicast Tree Construction in Wireless Sensor Networks" by Hongyu Gong, Luoyi Fu, Xinzhe Fu, Lutian Zhao, Kainan Wang and Xinbing Wang.
The detailed usage of each files is listed in the following.
Before running the code, make sure that proper C++ and Python2 compilers are installed.The node distribution data is generated by test.py.
The following example generate 100 relay nodes among 10000 nodes following uniform distribution. Each node has a transmission radius of 2sqrt(log(10000) / (10000)).
$ python test.py 10000 100 uniform 2.0
python test.py n m d c
The n, m, d, c options control the distribution of nodes, described as following:
n(int) : number of all nodes(including relay nodes)
m(int) : number of receivers(first m lines of point are considered as receivers)
d(string) : distribution of nodes across [0..1), possible choices:{uniform, normal, exponential}
c(int) : constant of radius, radius = c * sqrt(log(n) / (n))
Then, compile and run the C++ source file display.cpp as following:
$ make display
$ ./display
If you find these useful, we would be grateful if you could cite the following two papers:
If you find these useful, we would be grateful if you could cite the following two papers:
- Gong, H., Fu, L., Fu, X., Zhao, L., Wang, K., Wang, X. (2017). Distributed Multicast Tree Construction in Wireless Sensor Networks. IEEE Transactions on Information Theory, 63(1), 280-296. 9This package contains the codes of two classic searching algorithms: depth-first searching andbreadth-first search , the main behavior are illustrated in the following figure.
The codes are written in Matlab but stored in .txt files. Anyone who wants to use them can paste the content from .txt file into .m file in Matlab. Note that in our codes, we use adjacency list to store the graph, and can somehow lead to less consumption of space.
This package contains the simulation codes of Greedy Leaf Removal algorithm in interdependent networks.
The experimental dataset is selected from real networks and Erdos Renyi graphs. The resource of dataset can be found in our paper. All the codes are programmed in Python 2.7.
The algorithms proposed to be used to calculate the fraction of remaining nodes after Alternating GLR Process which includes both theoretical part and experimental part. An illustrative of such a node removal process in interdependent network is shown in the following figure:
For the detailed description of the coupled networks and the proposed algorithms involved, please refer to the following paper: J. Pan, Y. Yao,L. Fu, X. Wang, "Core Percolation in Coupled Networks" in ACM MobiHoc 2017 poster , Chenai, India.
The detailed usage of each files is listed in the following:
0_generate doubled network: generated graph from data source (real networks) or erdos renyi graph.
1_theory.py, which is used to calculate the theoretical result, i.e., the fraction of remaining nodes after Alternating GLR Process.
environment: Python 2.7
Call library : networkx
1.main_real(G_file) used to run Alternating GLR Process in a doubled network by real data source. To run the code, just need to change G_file to the file you want to load.eg: main_real("twitter_combined.txt")
2.main_er(np) used to run Alternating GLR Process in a doubled network which consist of two same erdos renyi graph and connections between them. np means average degree of erdos_renyi graph
The fraction after each iteration will be displayed on the screen.
Warning: The n factotial overflow when n>171
2_experiment.py, which is used to calculate the experiment result, the fraction of remaning nodes after Alternating GLR Process.
environment: Python 2.7
Call library : networkx
1.main_real(G_file,pp) used to run Alternating GLR Process in a doubled network by real data source. To run the code, just need to change G_file to the file you want to load.
eg: main_real("twitter_combined.txt")
pp:the connect possibility among nodes between two networks
2.main_er(n,p,pp) used to run Alternating GLR Process in a doubled network which consist of two same erdos renyi graph and connections between them.
n:number of nodes in one erdos renyi graph.
p: the connect possibility among nodes in erdos renyi graph.
n*p means average degree of erdos_renyi graph
pp:the connect possibility among nodes between two networks
The fraction after each iteration is shown in screen.
The fraction after each iteration is shown both in theory and experiment part.
If you find those useful, we would be grateful if you could cite the following paper:
This folder provides the source code for the ConMap optimization framework in the paper "ConMap: A Novel Framework for Optimizing Multicast Energy in Delay-constrained Mobile Wireless Networks".The main goal of ConMap is a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. It first converts the problem into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. An illustrative example of ConMpa is provided in the following figure. More details of the algorithm can be deferred to the above paper .
Note that the directed Steiner tree embedded in ConMap is the FasterDSP algorithm developed in "FasterDSP: A Faster Approximation Algorithm for Directed Steiner Tree Problem" .
To run the program, first go to the /graph/test_prog folder. Then, use the command like the following in the terminal:
./mihs-example c 20-100-10-1-500.2.tr 2
where the second parameter 'c' is the parameter tuning the subprocedure in FasterDSP (please refer to the mihs-example program for the details of this parameter), the third parameter is the source file for the intermediate graph in ConMap and the last parameter specifies a variable in FasterDSP.
The file 'conversion.cpp' is the program for intermediate graph construction in ConMap.
If you find these useful, please cite:
X. Fu, Z. Xu, Q. Peng, J. You, L. Fu, X. Wang and S. Lu, "ConMap: A Novel Framework for Optimizing Multicast Energy in Delay-constrained Mobile Wireless Networks", in Proc. ACM MobiHoc, 2017.
M. I. Hsieh, E. H. K. Wu and M. F. Tsai, "FasterDSP: A Faster Approximation Algorithm for Directed Steiner Tree Problem", in Journal of Information Science and Engineering, vol. 22, no. 6, pp. 1409-1425, 2006