社交网络影响力传播的演化框架及其应用

软件影响9（2021）100107原始软件出版物社交网络中影响力传播最大化的演化框架Giovanni Iaccaa，Sunday，Kateryna Konotopskaa，Doina Bucurb，Alberto Tondaca意大利特伦托市波沃Via Sommarive 9，38123，特伦托大学信息工程与计算机科学系b特文特大学电气工程、数学和计算机科学学院，Zilverling，Hallenweg 19，7522NH Enschede，荷兰cINRA，UMR 782 GMPA，Avenue Lucien Brétignières，78850 Thiverval-Grignon，France自动清洁装置保留字：社会网络影响力最大化进化算法A B标准社交网络是当今信息传播的主要来源之一。但是，并非所有节点都社交网络是平等的：事实上，一些节点比其他节点更有影响力，即，他们的信息会传播得更广寻找网络中最具影响力的节点-所谓的影响最大化问题- 是一个具有重大社会和经济意义的NP-难问题。在这里，我们介绍一个基于进化算法，包括各种图形感知技术（扩散近似，域特定的运营商，和节点过滤），促进优化过程。该框架可以直接应用于各种社交网络数据集，例如，SNAP仓库中的那些代码元数据当前代码版本v1.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2021-60可复制胶囊的永久链接https://codeocean.com/capsule/6362854/tree/v1法律代码许可证Apache-2.0许可证使用git的代码版本控制系统使用python、bash的软件代码语言、工具和服务编译要求，操作环境依赖python 3.6.8，python 1.0.1，networkx 2.3，numpy 1.16.3，cython 0.29.13，node2vec 0.3.1gensim 3.8.1，pandas 0.24.2如果可用，请链接到开发人员文档/手册https://github.com/tsume82/Influence-Maximization技术支持电子邮件咨询giovanni. unitn.it软件元数据当前软件版本v1.0此版本可执行文件的永久链接https://github.com/tsume82/Influence-Maximization可再生胶囊的永久链接https://codeocean.com/capsule/6362854/tree/v1法律软件许可证Apache-2.0许可证计算平台/操作系统Linux，OS X，Microsoft Windows，类Unix安装要求依赖项python 3.6.8，python 1.0.1，networkx 2.3，numpy 1.16.3，cython 0.29.13，node2vec0.3.1，gensim 3.8.1，pandas如果可用，链接到用户https://github.com/tsume82/Influence-Maximization技术支持电子邮件咨询giovanni. unitn.it软件范围社交网络如今用于各种活动，诸如阅读新闻、搜索工作、观看电影或购物。一社交网络中最重要的问题之一就是所谓的本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。*通讯作者。电子邮件地址：Giovanni. unitn.it（G. Iacca）。https://doi.org/10.1016/j.simpa.2021.100107接收日期：2021年6月1日;接收日期：2021年7月5日;接受日期：2021年7月11日2665-9638/©2021作者。由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表软件影响杂志 首页：www.journals.elsevier.com/software-impactsG. Iacca，K.Konotopska，D.Bucur等人软件影响9（2021）1001072影响最大化（IM）问题，其中一个人想要找到网络中最有影响力的节点。这个问题通常通过概率建模来解决影响如何在网络上传播[1]，从一组种子节点开始。 找到最佳的（即，最有影响力的）种子节点集是一个NP难问题[1]，最近的文献中已经提出了各种算法，如具有可证明保证的启发式算法[2这两类方法都提供了很好的结果，尽管它们的运行时间往往会随着网络的大小而增加。另一方面，IM是一个重要的问题，一些应用程序，如政治运动和营销，因此其影响是相关的。在这里，我们提出了一个开源的Python框架，基于Evo-推理算法（EA）。在EA中，候选解决方案被建模为种子节点标识符的固定大小的序列，智能初始化，变异和交叉算子生成候选解决方案，以形成一个新的人口。候选解的适应度可以通过概率扩散模型的蒙特卡罗模拟来估计，但该框架还包括高级图形感知技术（在[11]中引入），例如扩散模型的近似，候选解的特定于域的初始化和突变，以及节点过滤。这些技术允许EA以有效的方式解决IM问题。正如我们在[11]中所示，所提出的框架确实能够在一个更低的节点中找到好的种子节点集。这使得它在以大网络维度为特征的场景中特别有吸引力。因此，所提出的框架可以在一些研究项目和实际应用中引起兴趣。该框架在GitHub存储库1上公开提供，并包含以下主要元素：• EA的源代码，它基于-spyred2中的库;• 与[11]中介绍的图形感知功能相关的模块，包括用于动态突变选择的UCB 1多臂强盗算法[12]• 准备实验设置和运行执行管道的脚本（后者加载网络数据，使用适当的超参数和启用的元素运行EA，收集输出和日志）;• 影响传播评估部分的Cython包装器的管道，以及相关的脚本来编译它;• 可以用于运行完整管道的json配置文件（包含EA的超级参数）的示例• 来自文献的各种算法的实现（例如，高度[1]和CELF [2]），为测试图形感知EA提供基线结果;• [11]中给出的数值结果的原始数据，从SNAP存储库[13]中获得的各种网络数据（可以使用GitHub存储库中包含的脚本自动下载）。有关上述元素的更详细说明，请参阅README文件在我们的GitHub存储库中可用。影响概述与一些现有的算法相比，与框架一起提供的EA算法在来自SNAP存储库的各种网络数据上实现了最先进的结果（在改善的影响和减少的计算时间方面）。此外，该框架已经被用于解决一些关于影响最大化问题的研究问题，最值得注意的是[11]中讨论的各种图形感知元素对1https://github.com/tsume82/Influence-Maximization。2https://github.com/aarongarrett/inspyred。优化性能据我们所知，没有类似的开源软件或工具箱。然而，该框架可以很容易地扩展到追求新的研究问题。例如，一种可能性可以是将其他目标包括到问题表述中（例如，最小化传播时间）。其他选项包括（但不限于）：分析动态社交网络;将特征与网络中的节点相关联，然后找到种子节点的有影响力的集合，这些种子节点也最大化受影响节点的特征多样性;设计和测试要包括在EA中的新颖算法元素。在所有这些情况下，框架中包含的EA，以及至少一些图形感知机制，都可以重用。目前，该框架正在用于几个学生项目和研究活动，旨在扩展[11]中获得的结果。到目前为止，该框架已经在一些学术出版物中使用。特别是，该框架的原始版本不包括任何图形感知机制，首先在[14]中使用IM问题的单目标公式，后来在[15-最终，该框架已被合并，如本文所示，并使用[11]中引入的图形感知机制进行扩展。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]David Kempe ， Jon Kleinberg ， Éva Tardos ， Maximizing the spread ofinfluencethrough a social network ， in ： International Conference on KnowledgeDiscoveryandData Mining，KDD，ACM，New York，NY，USA，2003，pp. 137-146。[2] Jure Leskovec，Andreas Krause，Carlos Guestrin，Christine Faloutsos，ChristineFaloutsos，Jeanne VanBriesen，Natalie Glance，网络中的成本效益爆发检测，在：知识发现和数据挖掘国际会议，KDD，ACM，纽约，纽约，美国，2007年，pp.420-429[3] Youze Tang ， Yanchen Shi ， Xiaokui Xiao ， Influence Maximization in Near-LinearTime ： A Martingale Approach ， in ： International Conference onManagement ofData，SIGMOD，ACM，New York，NY，USA，2015，pp. 1539-1554年。[4] H.T. Nguyen，M.T. Thai，T.N.陈晓，病毒式营销中的一种最大效益近似算法，北京大学出版社，2001。25（4）（2017）2419-2429。[5] 刘晓波，刘晓波，等.基于进化算法的社交网络中的影响力分析.北京：计算机科学出版社，2000，24（3）：117 - 118. Comput. Sci. 31（2018）77[6] Abel García-Nájera，Saúl Zapotecas-Martínez，Roberto Bernal-Jaquez，遗传算法中最 大影响问 题的选 择方案分 析， 在： 墨西哥 人工智能 国际会 议，MICAI，Springer，Cham，2020年，第10页。211-222[7] Rodrigo Rodrigues，Arthur Silva，Viní cius Vieira，Carolina Xavier，通过遗传算法优化免疫个体的选择，SIR模型，在：计算科学及其应用国际会议，ICCSA，施普林格，Cham，2018年，pp。62比75[8] ArthurRodrigues da Silva，Rodrigo Ferreira Rodrigues，Viníciusda丰-secaVieira，Carolina Ribeiro Xavier，通过遗传算法对线性阈值模型的网络影响最大化，在：计算科学及其应用国际会议，ICCSA，Springer，Cham，2018年，pp. 96比109[9] Krzysztof Michalak，使用机器学习优化流行病预防的知情突变算子，在：遗传和进化计算会议，GECCO，ACM，纽约，纽约，美国，2018年，pp. 公元1294-1301年。[10] 郭建斌，陈福赞，李民强，社交网络中影响力最大化的多目标优化方法，在：工业工程和工程管理国际会议，IEEM，Springer，新加坡，2019年，pp. 706-715[11]Kateryna Konotopska，Giovanni Iacca，Graph-aware evolutionary algorithms forinfluence maximization，2021，arXiv preprintarXiv：2104.14909。[12] Peter Auer ， Nicolo Cesa-Bianchi ， Paul Fischer ， 多 臂 强盗 问 题 的 实时 分 析 ，Mach。学习. 47（2-3）（2002）235[13] Jure Leskovec ， Andrej Krevl ， SNAP Datasets ： Stanford large network datasetcollection，2014，http://snap.stanford.edu/data。G. Iacca，K.Konotopska，D.Bucur等人软件影响9（2021）1001073[14] Doina Bucur ， Giovanni Iacca ， Influence maximization in 社 交 网 络 withgeneticalgorithms，in：EuropeanConferenceontheApplicationsofEvolutionaryComputation ， in ： LNCS ， vol. 9597 ， Springer ， Berlin ，Heidelberg，2016，pp. 379 -392.[15]Doina 布库尔， Giovanni 雅卡， Andrea 玛瑟利 Giovanni 阿尔贝托？斯奎莱罗Tonda，社交网络中影响力最大化的多目标进化算法，在：欧洲进化计算应用会议，在：LNCS，第10199卷，Springer，Cham，2017年，pp. 221-233[16] Doina Bucur ， Giovanni Iacca ， Andrea Marcelli ， Giovanni Squillero ，AlbertoTonda，在社交网络中评估多目标影响最大化的代理模型，在：遗传和进化计算会议伴侣，GECCO，ACM，纽约，纽约，美国，2018年，pp. 1258-1265年。[17]Doina布库尔，Giovanni雅卡，Andrea玛瑟利Giovanni阿尔贝托？斯奎莱罗Tonda，改善社交网络中的多目标进化影响最大化，在：进化计算应用国际会议上，Springer，Cham，2018年，pp。117-124