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 | |
Hot Topic Prediction in Scholarly Networks | |
Dynamic Rumor Blocking in Online Social Netorks | |
Scholarly Networks Evolution |
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
We generate a large set of scholarly topics information in the field of Computer Science with reliable ground-truth communities based on Microsoft Academic Graph (MAG). The MAG dataset contains over 100 million scientific papers with titles, references, publish time, and sets of “Field of Study” (FoS).
We extract the topic information with 17 features listed below and do the time serialization to all the features. Then we measure the features in different metrics and predict the future trends of all the topics in this dataset.
If you find theses useful, we would be grateful if you could cite the following paper:
- Jinghao Zhao, Hao Wu, Fengyu Deng, Wentian Bao, Wencheng Tang, Luoyi Fu, Xinbing Wang, "Maximum Value Matters: Finding Hot Topics in Scholarly Fields"This package contains the code （written in Matlab) for the realization of rumor blocking in online social networks.
The package is divided into two folders, with one describing the rumor propagation models and the other describing the rumor blocking methods.
Brief introduction: We propose a model of dynamic rumor influence minimization with user experience (DRIMUX). Our goal is to minimize the influence of the rumor (i.e., the number of users that have accepted and sent the rumor) by blocking a certain subset of nodes. A dynamic Ising propagation model considering both the global popularity and individual attraction of the rumor is presented based on realistic scenario. In addition, different from existing problems of influence minimization, we take into account the constraint of user experience utility. Specifically, each node is assigned a tolerance time threshold. If the blocking time of each user exceeds that threshold, the utility of the network will decrease. Under this constraint, we then formulate the problem as a network inference problem with survival theory, and propose solutions based on maximum likelihood principle.
For more details, please refer to the paper
If you find theses useful, we would be grateful if you could cite the following paper:
- B. Wang, G. Chen,L. Fu, L. Song, X. Wang, "DRIMUX: Dynamic Rumor Influence Minimization with User Experience in Social Networks," to appear in IEEE Transactions on Knowledge and Data Engineering, 2017we design a novel model to capture these properties and we name this model as: Evolving Scholarly Model. In our evolving scholarly model, the graph is denoted as G(Np,Na,Nt). Then we use tripartite graph to present the inter-correlation between elements. Besides, we also focus on the intra-features of every element. For an intuitive understanding, we illustrate the framework of our evolving scholarly model in the Figure. It contains:
While we defer the detailed evolving process of the proposed model to Algorithm , we would also like to provide a corresponding brief summary of the process.
We first fix parameters including alpha_i, beta_ij and c_ij where i != j belong to {p,a,t}, and then assume that the evolution starts from an initial case that can be modeled as an initial graph, showing that each node in the graph is linked to a number of nodes in other node sets. After initialization, for every time slot, we classified the process into five main steps:
For a better intuitive understanding of this evolving process, let us, for instance, consider the arrival of a new author. He is likely to learn from an influential author, who is thus selected as a prototype and influences the new author on choosing research topics. In addition, when conducing the new research, this new author probably has on mind some other author who have many publications as another prototype, from whom he chooses some old papers for references. Obviously, the topics and the papers chosen by the same author are often relevant, indicating that these papers belong to these topics with a high possibility. Last but not least, let us consider a co-author network, where a new author may want to collaborate with others who are also interested in these topics and papers for a joint piece of work. Similarly, when a new topic emerges in the literature, it is usually inspired by some existing topics (prototypes), and when a paper arrives, it is often based on a number of old papers (prototypes).