A Hybrid Matheuristic for the Spread of Influence on Social Networks - Complementary Data

This dataset contains complementary data to the paper "A Hybrid Matheuristic for the Spread of Influence on Social Networks" [1], which proposes a matheuristic for combinatorial optimization problems involving the spread of information in social networks.

For the computational experiments discussed in that paper, we provide:

- Two sets of instances, originally obtained from [2-6];
- The solutions attained by exact and heuristic methods;
- The collected results;
- The matheuristic source code;

The directories "benchmark_*/instances/" contain files that describe the sets of instances. Each instance is associated with a graph containing <n> vertices and <m> edges.

The first <m> lines of each file contain:

<u> <v>

where <u> and <v> identify a pair of vertices that determines an undirected edge.

The next line contains <n> integers corresponding to the costs of the vertices.

The last line contains <n> integers corresponding to the thresholds of the vertices.

The directories "benchmark_*/solutions_*/" contain files describing feasible solutions for the corresponding sets of instances.

The first line of each file contains:

<s>

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

<v>

where <v> identifies a target.

The last line contains an integer that represents the target set cost.

The directory "hmf_source_code/" contains an implementation of the matheuristic framework proposed in [1], namely, HMF.

This work was supported by grants from Santander Bank, the Brazilian National Council for Scientific and Technological Development (CNPq), the São Paulo Research Foundation (FAPESP), the Fund for Support to Teaching, Research and Outreach Activities (FAEPEX), and the Coordination for the Improvement of Higher Education Personnel (CAPES), all in Brazil.

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

References

[1] F. C. Pereira, P. J. de Rezende, and T. Yunes. A Hybrid Matheuristic for the Spread of Influence on Social Networks. 2024. Submitted.

[2] S. Raghavan and R. Zhang. A branch-and-cut approach for the weighted target set selection problem on social networks. 2024. https://doi.org/10.1287/ijoo.2019.0012

[3] J. Leskovec and A. Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. 2024. https://snap.stanford.edu/data

[4] R. A. Rossi and N. K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization. 2022. https://networkrepository.com

[5] J. Kunegis. KONECT – The Koblenz Network Collection. 2013. http://dl.acm.org/citation.cfm?id=2488173

[6] O. Lesser, L. Tenenboim-Chekina, L. Rokach, and Y. Elovici. Intruder or Welcome Friend: Inferring Group Membership in Online Social Networks. 2013. https://doi.org/10.1007/978-3-642-37210-0_40

本数据集包含与论文《一种针对社交网络中信息传播的混合启发式算法》[1]的互补数据，该论文提出了一种用于组合优化问题的混合启发式算法，涉及社交网络中信息的传播。针对该论文中讨论的计算实验，我们提供以下内容：

- 两个实例集，原始数据来源于[2-6]；
- 精确和启发式方法获得的解决方案；
- 收集到的结果；
- 混合启发式算法的源代码。

“benchmark_*/instances/”目录包含描述实例集的文件。每个实例与一个包含<n>个顶点和<m>条边的图相关联。每个文件的最初<m>行包含以下内容：

&u> &v>

其中<u>和<v>标识了一对顶点，确定了无向边。下一行包含<n>个整数，对应于顶点的成本。最后一行包含<n>个整数，对应于顶点的阈值。

“benchmark_*/solutions_*/”目录包含描述相应实例集可行解的文件。每个文件的第一行包含以下内容：

&s>

其中<s>是目标集的顶点数。接下来的<s>行包含以下内容：

&v>

其中<v>标识了一个目标。最后一行包含一个整数，代表目标集的成本。

“hmf_source_code/”目录包含[1]中提出的混合启发式框架的实现，即HMF。

本工作得到桑坦德银行、巴西国家科学技术发展委员会（CNPq）、圣保罗研究基金会（FAPESP）、教学、研究和外展活动支持基金（FAEPEX）以及巴西高等教育人员能力提升协调处（CAPES）的资助。

注意事项：本材料中表达的见解、假设以及结论或建议由作者本人负责，并不必然反映桑坦德、CNPq、FAPESP、FAEPEX或CAPES的观点。

参考文献

[1] F. C. Pereira, P. J. de Rezende, 和 T. Yunes. 一种针对社交网络中信息传播的混合启发式算法。2024. 已提交。
[2] S. Raghavan 和 R. Zhang. 社交网络中加权目标集选择问题的分支定界法。2024. https://doi.org/10.1287/ijoo.2019.0012
[3] J. Leskovec 和 A. Krevl. SNAP 数据集：斯坦福大型网络数据集收集。2024. https://snap.stanford.edu/data
[4] R. A. Rossi 和 N. K. Ahmed. 网络数据存储库：带有交互式图分析和可视化的网络数据。2022. https://networkrepository.com
[5] J. Kunegis. KONECT – 科布伦茨网络收藏。2013. http://dl.acm.org/citation.cfm?id=2488173
[6] O. Lesser, L. Tenenboim-Chekina, L. Rokach, 和 Y. Elovici. 网络社交网络中的入侵者或欢迎的朋友：推断在线社交网络中的群体成员资格。2013. https://doi.org/10.1007/978-3-642-37210-0_40