This code was forked from https://github.com/todo314/pruned-monte-carlo on 28th February 2020.
Given a graph with edge probabilities, it selects a seed set of a given size, as well as providing other data
$ make
$ ./pmc_greed tsv_file target_seed_size number_of_random_graphs seed_delta
- tsv_file: input file (see below)
- target_seed_size: the target seed set size
- number_of_random_graphs: the number of random graphs to simulate (larger = more accurate)
- seed_delta: a fixed integer to be added as a seed so as to allow for different seeds
$ make
$ ./pmc_greed samples/sample.tsv 5 100000 0
0 1.12257 0.3489
4 1.09755 0.391786
2 1.00769 0.429225
3 0.97071 0.465096
1 0.80148 0.501
On each line,
- The first integer refers to the seed corresponding to input
.tsv
- The second number refers to the marginal gain of that seed. Submodularity of the independent cascade model of influence means this number should only decrease.
- The third number is the amount of time in seconds used to calculate up to that seed. This number should only increase.
$ ./pmc_est samples/sample.tsv samples/sample_seeds.txt 100000 0
0 1.12257
4 1.09755
2 1.00769
3 0.97071
1 0.80148
On each line,
- The first integer refers to the seed corresponding to the solution. The solution file can be space separated, tab-separated or newline separated integers. They should correspond to the
.tsv
files. - The second number is the marginal gain of that seed. The program processes exactly the order as given. Different orders will result in different marginal gain numbers. In particular, the gain may not be submodular, but should be submodular if the same sequence resulting from a greedy algorithm is used.
u_1 v_1 p_1
...
u_i v_i p_i
...
u_m v_m p_m
- The i-th line means an directed edge (u_i, v_i) with propagation probability p_i (see
samples/sample.tsv
). - Vertices should be described by integers starting from zero.
- Added timing functionality.
- Added seeding functionality.
- Removed verbosity of output.
- Minor changes:
- Renamed items:
samples/sample_graph.tsv
->samples/sample.tsv
samples/sample_graph_seeds.txt
->samples/sample_seeds.txt
src/inf_est.cpp
->src/est.cpp
- Added new flags to Makefile.
- Changed certain variables to unsigned to comply with compiler requirements.
- Removed all instances of
using
. - Added
.gitignore
for outputs ofmake
.
- Renamed items:
- Renamed resulting executable as
pmc_greed
. - Changed
pmc_greed
to also provide marginal gain estimates. Example output:This is expected output as the marginal gains are decreasing as the influence function is submodular under the independent cascade model.$ ./pmc_greed samples/sample_graph.tsv 5 200 0-th seed and marginal gain = 4 1.155 1-th seed and marginal gain = 0 1.11 2-th seed and marginal gain = 2 1.005 3-th seed and marginal gain = 3 0.935 4-th seed and marginal gain = 1 0.795
- Added a new executable
pmc_est
. Essentially, given a seed set file which corresponds to the graph file, thepmc_est
estimates the marginal gain of each seed. The text filesample_graph_seeds.txt
shows how a possible input could be like. The input can also be newline delimited. Example usage:The output agrees with the above as it essentially uses the same setup code and skips the greedy portion.$ ./pmc_est samples/sample_graph.tsv samples/sample_graph_seeds.txt 200 Marginal gain of seed 4 = 1.155 Marginal gain of seed 0 = 1.11 Marginal gain of seed 2 = 1.005 Marginal gain of seed 3 = 0.935 Marginal gain of seed 1 = 0.795
- Changed
pmc.hpp
to not useusing namespace std;
, following common convention. - All other instances of
using namespace std;
have been changed to using specific things withinstd
.
- Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. In AAAI-14, pages 138--144, 2014.