This folder contains the source code for the Online Influence Maximization with Persistence algorithms, as described in this paper and the model-free extension. The source code is header-only.

Compiling

The Makefile is in the main folder, so simply execute make:

make clean; make

The output binary is oim.

Dependencies

The Makefile requires GCC 4.9.0 (or superior) and uses C++14 features.

The code needs the Boost C++ library headers. It assumes the include files are present in /usr/local/include. If your Boost installation is someplace else, you have to modify the INCLUDE_DIRS directive in Makefile. The binary library does not need to be linked.

Datasets

The networks used in the experimental section of our paper are available here. We provide scripts to generate your own datasets in the graph/ folder.

Methods and usage

The program expects as input a tab delimited graph file of the following format:

node1 <TAB> node2 <TAB> prob

where node1 and node2 are the endpoints of a graph edge, and prob is the influence probability.

The following methods are currently supported:

1. exponentiated gradient, which is run as follows:

    ./oim --eg <graph> <alpha> <beta> <exploit> <trials> <k> [<model>
    <update> <update_type> <cascades>]
   

2. missing mass, which runs as follows:

    ./oim --missing_mass <graph> <policy> <reduction> <budget> <k>
    <n_experts> [<model> <cascades>]
   

3. real graph, which executes on the real graph:

    ./oim --real <graph> <exploit> <trials> <k> [<model> <samples>
    <cascades>]
   

Parameters

The parameters are set as follows:

• graph is the name of the graph file
• alpha, beta are the global prior on the edges of the graph
• exploit, explore can take any of the following values: 0 Random, 1 Discountdegree, 2 Maxdegree, 3 CELF, 4 TIM, 5 SSA, 6 PMC
• samples is the number of spreads to estimate the expected value of chosen seeds
• trials is the number of trials, k is the number of seeds in each trial
• update is 1 if the graph is updated, 0 otherwise
• update_type is the type of update: 0 local only, 1 least squares or 2 maximum likelihood
• reduction can take the following values: 0 max cover, 1 highest degree
• policy can take the following values: 0 random, 1 Good-UCB
• model can take the following values: 0 Linear Threshold, 1 Independent Cascade
• cascades contains the path to the file containing real cascades (logs)

Output

The different methods write on the standard output with the following format:

1. exponentiated gradient:

    stage <TAB> cum spread <TAB> expected spread <TAB> tselection <TAB> tupdate <TAB>
    tround <TAB> ttotal <TAB> theta <TAB> memory <TAB> k <TAB> model <TAB> seeds
   

2. missing mass:

    stage <TAB> cumulative spread <TAB> treduction <TAB> tselection <TAB> tupdate <TAB>
    tround <TAB> ttotal <TAB> memory <TAB> k <TAB> n_experts <TAB> n_policy <TAB>
    n_reduction <TAB> model <TAB> seeds
   

3. real graph:

    stage <TAB> cumulative spread <TAB> expected spread <TAB> tround <TAB>
    ttotal <TAB> k <TAB> model <TAB> seeds
   

Contributors

• Paul Lagrée (Université Paris-Sud)
• Siyu Lei (University of Hong Kong) on code published in 2015
• Silviu Maniu (University of Hong-Kong, then Université Paris-Sud)
• Luyi Mo (University of Hoong-Kong) on code published in 2015

License

The source code is provided as-is under an MIT License. If it is useful to you, please cite the seminal paper and the model-free extension.