一种新的复杂网络影响力最大化发现方法

被引：3

作者：

胡庆成

张勇

许信辉

邢春晓

陈池

陈信欢

机构：

[1] 清华大学计算机科学与技术系信息技术研究院清华信息科学与技术国家实验室

来源：

物理学报 | 2015年 / 64卷 / 19期

基金：

国家高技术研究发展计划(863计划);

关键词：

复杂网络; 影响力最大化; 信息传播; 贪心算法;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一,其研究在理论和现实应用中都有重大的意义.在给定s值的前提下,如何寻找发现s个最大影响范围的节点集,这是个组合优化问题,Kempe等已经证明该问题是NP-hard问题.目前已有的随机算法时间复杂度低,但是结果最差;其他贪心算法时间复杂度很高,不能适用于大型社会网络中,并且这些典型贪心算法必须以了解网络的全局信息为前提,而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的.我们提出了一种新的影响力最大化算法模型RMDN,及改进的模型算法RMDN++,模型只需要知道随机选择的节点以及其邻居节点信息,从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题,算法的时间复杂度仅为O(s log(n));然后,我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示,RMDN,RMDN++算法有着和现有典型算法相近的影响力传播效果,且有时还略优,同时在运行时间上则有显著的提高;我们从理论上推导证明了方法的可行性.本文所提出的模型算法适用性更广,可操作性更强,为这项具有挑战性研究提供了新的思路和方法.

引用

页码：27 / 38

页数：12

共 5 条

[1] 网络重要节点排序方法综述 [J].

任晓龙 ;

吕琳媛 .

科学通报, 2014, (13) :1175-1197

[2] 一种新的网络传播中最有影响力的节点发现方法 [J].

胡庆成 ;

尹龑燊 ;

马鹏斐 ;

高旸 ;

张勇 ;

邢春晓 .

物理学报, 2013, 62 (14) :9-19

[3] Ranking the spreading influence in complex networks [J].

Liu, Jian-Guo ;

Ren, Zhuo-Ming ;

Guo, Qiang .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2013, 392 (18) :4154-4159

[4] Identification of influential spreaders in complex networks [J].

Kitsak, Maksim ;

Gallos, Lazaros K. ;

Havlin, Shlomo ;

Liljeros, Fredrik ;

Muchnik, Lev ;

Stanley, H. Eugene ;

Makse, Hernan A. .

NATURE PHYSICS, 2010, 6 (11) :888-893

[5]

Power laws, Pareto distributions and Zipf's law[J] . MEJ Newman.Contemporary Physics . 2005 (5)

← 1 →