| 引用本文: | 王潇杰,赵城利,张雪,等.复杂网络影响力极大化快速评估算法.[J].国防科技大学学报,2019,41(3):166-173.[点击复制] |
| WANG Xiaojie,ZHAO Chengli,ZHANG Xue,et al.Maximizing spread of influence in complex networks through fast evaluation[J].Journal of National University of Defense Technology,2019,41(3):166-173[点击复制] |
|
| |
|
|
| 本文已被：浏览 6557次 下载 5220次 |
| 复杂网络影响力极大化快速评估算法 |
| 王潇杰1, 赵城利1, 张雪1, 易东云1,2 |
|
(1. 国防科技大学 文理学院， 湖南 长沙 410073;2. 国防科技大学 高性能计算国家重点实验室， 湖南 长沙 410073)
|
| 摘要: |
| 分析复杂网络中影响力极大化问题，设计一种新的启发式算法框架。针对信息传递中节点的交互方式进行分析，给出节点在任意时刻处于信息接收态的概率。通过期望计算得到种子节点集传播影响力的近似估计，实现集群影响力快速计算，进而得到基于序列采样的影响力极大化快速评估算法。特别地，对于六个来自不同领域的真实网络上的影响力极大化问题进行了研究，仿真结果表明：该方法能够高效识别网络中具有重要传播影响力的节点集，在三种常见度量准则下的表现均明显优于三种影响力极大化问题基准算法。 |
| 关键词: 复杂网络 传播动力学 影响力极大化 序列采样 启发式算法 |
| DOI：10.11887/j.cn.201903025 |
| 投稿日期：2018-03-07 |
| 基金项目:国家重点基础研究发展计划资助项目（2017YCF1200301） |
|
| Maximizing spread of influence in complex networks through fast evaluation |
| WANG Xiaojie1, ZHAO Chengli1, ZHANG Xue1, YI Dongyun1,2 |
|
(1. College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China;2. State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| In order to study the influence maximization problem in complex networks, a heuristic framework was developed. Based on the in-depth analysis of information transmit process between node pairs, the probability of a node being in the informed state was obtained, and then an approximation of spreading influence of seed nodes was conducted through expectation calculation. A fast evaluation algorithm was proposed based on sequential seeding strategy. Specifically, simulation results on six real networks from various fields all show that the proposed algorithm is able to distinguish a small set of influential seed nodes. Moreover, the influence scope of the seed nodes selected by the method is significantly better than three benchmark influence maximization algorithms under three common measurements. |
| Keywords: complex network spreading dynamics influence maximization sequential seeding heuristic algorithm |
|
|
|
|
|
