Efficient collective influence maximization in cascading processes with first-order transitions.
Efficient collective influence maximization in cascading processes with first-order transitions.
复制标题
DOI：
10.1038/srep45240
复制
发表时间：
2017-03-28
影响因子：
4.6
通讯作者：
Makse HA
中科院分区：
文献类型：
--
作者：
Pei S;Teng X;Shaman J;Morone F;Makse HA
在许多社会和生物网络中，整个系统的集体动态可以由一小部分有影响力的单元通过全局级联过程来塑造，表现为动态行为中突然的一阶转变。尽管其在应用中很重要，但对于大型网络来说，在级联过程中有效识别多个有影响力的传播者仍然是一项具有挑战性的任务。在这里，我们通过探索级联过程的一般阈值模型中的集体影响来解决这个问题。我们的分析表明，吊具的重要性取决于级联传播的亚临界路径：每个吊具所附的亚临界路径的数量决定了其对全局级联的贡献。亚临界路径的概念使我们能够为大规模网络引入可扩展的算法。合成随机图和真实网络的结果表明，与其他可扩展的启发式方法相比，在给定相同数量的种子的情况下，所提出的方法可以实现更大的集体影响。
In many social and biological networks, the collective dynamics of the entire system can be shaped by a small set of influential units through a global cascading process, manifested by an abrupt first-order transition in dynamical behaviors. Despite its importance in applications, efficient identification of multiple influential spreaders in cascading processes still remains a challenging task for large-scale networks. Here we address this issue by exploring the collective influence in general threshold models of cascading process. Our analysis reveals that the importance of spreaders is fixed by the subcritical paths along which cascades propagate: the number of subcritical paths attached to each spreader determines its contribution to global cascades. The concept of subcritical path allows us to introduce a scalable algorithm for massively large-scale networks. Results in both synthetic random graphs and real networks show that the proposed method can achieve larger collective influence given the same number of seeds compared with other scalable heuristic approaches.