Minimizing the Cost of Leveraging Influencers in Social Networks: IP and CP Approaches - Complementary Data

This dataset contains complementary data to the paper "Minimizing the Cost of Leveraging Influencers in Social Networks: IP and CP Approaches" [1], which studies integer/constraint programming formulations for the Least Cost Directed Perfect Awareness Problem, an NP-hard optimization problem that arises in the context of influence marketing. Regarding the computational experiments conducted in the paper, we make available:

- Two sets of instances;
- The best known attained solutions;
- The source code;
- An appendix with additional details about the results.

The first input set includes 300 synthetic instances composed of graphs that resemble real-world social networks [2]. The second set consists of 14 instances built from online interactions crawled from X (formerly known as Twitter) [3].

The directories "synthetic_instances" and "x_instances" contain files that describe both sets of instances. The first two lines of each file contain:

<n>
<m>

where <n> and <m> are the number of vertices and edges in the graph. Each of the next <n> lines contains:

<v> <c> <t>

where <v> identifies a vertex while <c> and <t> are the cost and threshold associated to that vertex. Each of the <m> remaining lines contains:

<u> <v> <w>

where <u> and <v> identify an ordered pair of vertices that determines a directed edge with weight <w>.

The directories "solutions_for_synthetic_instances" and "solutions_for_x_instances" contain files that describe the best known solutions for both sets of instances. The first line of each file contains:

<s>

where <s> is the number of vertices in the solution. Each of the next <s> lines contains:

<v>

where <v> identifies a seed vertex. The last line contains:

<c>

where <c> is the solution cost.

The directory "source_code" contains the implementations of the mathematical models studied in the paper.

Lastly, the file "appendix.pdf" presents details of the results reported in the paper [1].

This work was supported by grants from Santander Bank, Brazil, Brazilian National Council for Scientific and Technological Development (CNPq), Brazil, and São Paulo Research Foundation (FAPESP), Brazil.

Caveat: the opinions, hypotheses and conclusions or recommendations expressed in this material are the responsibility of the authors and do not necessarily reflect the views of Santander, CNPq or FAPESP.

References

[1] F. C. Pereira, P. J. de Rezende and T. Yunes. Minimizing the Cost of Leveraging Influencers in Social Networks: IP and CP Approaches. Submitted. 2023.

[2] F. C. Pereira, P. J. de Rezende. The Least Cost Directed Perfect Awareness Problem: complexity, algorithms and computations. Online Social Networks and Media, 37-38, 2023.

[3] C. Schweimer, C. Gfrerer, F. Lugstein, D. Pape, J. A. Velimsky, R. Elsässer, and B. C. Geiger. Generating simple directed social network graphs for information spreading. In Proceedings of the ACM Web Conference 2022, WWW ’22, pages 1475–1485, 2022.