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.- Luoyi Fu, Xinbing Wang, P. R. Kumar, "Optimal determination of source-destination connectivity in random graphs," in Proc. of ACM MobiHoc 2014, Philadelphia, PA, USA, Aug, 2014

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. 9- Gong, H., Zhao, L., Wang, K., Wu, W., Wang, X. (2015, June). A distributed algorithm to construct multicast trees in WSNs: An approximate steiner tree approach. In Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing (pp. 347-356). ACM.

This package contains the codes of two classic searching algorithms: depth-first searching and breadth-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.

- Training.csv: The training datasets are made by the Dataset.csv. The last column named ‘Target’ is the result we used to train the model. The suffix of file name indicates the time gap of the prediction, including 1, 5 and 10.
- features,py: Measure the features in different metrics.
- modelComp.py: Train different models and do the prediction, including linear regression (LR), Decision Tree Regression (DT), Random Forest Regression (RF), Extremely Randomized Trees Regression (ExtraTrees), Gradient Boosting Regression (GBDT) and bagged decision trees (BAG).
- lstm.py: Prediction by the Long Short Term Memory(LSTM).
- bpnn.py: Prediction by the multilayer neural network which is composed of four layers, with the size of each layer being 5, 6, 6, 5. Lbfgs algorithm is chosen as the solver for weight optimization and the activation function of the hidden layer is Relu. ztopic2.py provide some auxiliary functions.

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

- - propagation.m : natural propagation based on network link weights.
- - propagation_after_blockage.m : propagation after some nodes are blocked for a duration
- - propagation_with_dynamic_blockage.m : dynamic algorithm in paper, works along the propagation process (each iteration will follow the greedy strategy).

- - ChooseNodesRandom.m : baseline of randomly choosing n nodes
- - ChooseNodesDegree.m : select the n highest degree nodes as candidates
- - ChooseNodesWeightsum.m : select the n candidates according to the sum of outgoing link weights
- - Greedy.m : Greedy algorithm in the paper.

- - covers : rumor affected nodes, matrix with affected as 1, non-affected as 0
- - lambda : coefficient of propagation to multiply link weight
- - times : time interval
- - n : number of candidates
- - block_start: start moment of blockage
- - block_nodes: matrix of blocked nodes with blocked as 1, non-blocked as 0
- - block_duration : length of time-slots that the blocked_nodes are to be blocked.

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:

- (1) Three node sets: Paper node set Np, author node set Na and topic node set Nt. The node in each node set is marked as n_p, n_a and n_t.
- (2) Three inter-edge sets: We denote the edges between every two different node sets as inter-edge sets, and the graph has three inter-edge sets. For example, we refer all edges between paper node and author node as E_pa,E_ap, then an edge e_n_pn_a which belongs to E_pa means author n_a writes the paper n_p.
- (3) Three intra-edge sets: Intra-edge is the edge in the same node set, and our graph has three intra-edge sets, which we refer as E_pp, E_aa, and E_tt. If an edge e_n_a^in_a^j in E_aa, then we know that author n_a^i and n_a^j have cooperation.

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:

- 1) A new node, which can be randomly designated as a paper, an author, or a topic, is added to the graph. For clarity, here we only take the arrival of a new author as example for explanation of the subsequent steps. And the symmetry also holds for paper and topic.
- 2) With probability proportional to degree in B(N_a, N_p) and B(N_a, N_t), two author nodes n_a^p and n_a^t are chosen as prototypes for the new node n_a.
- 3) c_ap neighbors (n_p^1 ,..., n_p^{c_ap}) of n_a^p in N_p and c_at neighbors (n_t^1 ,..., n_t^{c_at}) of n_a^t in N_t are randomly chosen to have connections with node n_a.
- 4) c_ap,c_at edges are added between n_p^1 ,..., n_p^{c_ap} and n_t^1 ,..., n_t^{c_at}.
- 5) Edges between every two author nodes are added with probability beta_ap (beta_at) if they have a common paper (topic).

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).