Spread Blockers in Dynamic Networks

Overview

The software on this page is for Finding Spread Blockers in Dynamic Networks experiments.


Complete Download

Optimized, pre-compiled binaries are available for Ubuntu platform. The source is also available, and should compile on most systems with an ANSI compliant C/C++ compiler. To compile, just untar the file. Sample make file is also available. Also, included are sample inputs and outputs for each experiment.

Blockers-Complete

Description

There are three types of experiments performed for finding spread blockers in dynamic networks. A short description and set of command line parameters required for each experiments are provided below.

Best blockers

Each individual is blocked/removed from the network while expected spread in the remaining population is calculated. The individual/blocker that reduces the expected spread the most is picked. Incrementally, second, third and so on best blockers in the network are picked until some stopping criterion is met. In this code the stopping criterion is minimizing the spread to 'x'% of the population. 'x' is one of the command line parameters.

The following command line parameters are required:

<inputfilename> Specifies the input file in the format explained above.
<pi>            Specifies probability of activation
<percentActive> Specifies the proportion of population that remains active in the end. 
<ouputfilename> Specifies the output file in which blockers picked in each iteration and their corresponding
		minimal expected spread in the network is saved. 

Code for Best Blockers only.

Random blockers

Individuals are blocked/removed from the network uniformly at random until the minimum spread criterion is met.

The following command line parameters are required:

<inputfilename> Specifies the input file in the format explained above.
<pi>            Specifies probability of activation
<percentactive> Specifies the proportion of population that remains active in the end. 
<ouputfilename> Specifies the output file in which blockers picked in each iteration and their corresponding
		minimal expected spread in the network is saved. 

Code for Random Blockers only.

Measures based blockers

Individuals are blocked/removed from the network in the highest to lowest rank order based on a certain measure like degree, betweennes etc. Starting with blocking the highest ranked individual, expected spread in the remaining unblocked network is calculated. Subsequently more individuals are blocked until the stopping criterion is met.

The following command line parameters are required:

<inputfilename> Specifies the input file in the format explained above.
<pi>            Specifies probability of activation
<percentactive> Specifies the proportion of population that remains active in the end. 
<rankfile>      Specifies the rank ordered list of individuals. 
<ouputfilename> Specifies the output file in which blockers picked in each iteration and their corresponding
		minimal expected spread in the network is saved. 

Code for Measure based Blockers only.

Input dynamic network format

The input dynamic network file format consists of one interaction per timestep. Each line is composed of a tuple of 3 items: Timestep and a pair of interacting individuals. That is, "<timestep> <Individual_ID_i><Individual_ID_j>". There are no blank timesteps. If there are no observations available for a timestep, that timestep is skipped. Following is a small example of a dynamic network data:
T1	N2	N5
T1	N3	N1
T2	N3	N2
T2	N4	N1
T2	N34	N10
T5	N7	N5
T5	N7	N1
T6	N7	N5
T7	N10	N6
T8	N4	N3