Descrição:
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.