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

A new approach for influence maximization in complex networks

作　　者：胡庆成[1] 张勇[1] 许信辉[1] 邢春晓[1] 陈池[1] 陈信欢 

机构地区：[1]清华大学计算机科学与技术系信息技术研究院清华信息科学与技术国家实验室,北京100084

出　　处：《物理学报》2015年第19期19-30,共12页Acta Physica Sinica

基　　金：国家重点基础研究发展(973计划)(批准号:02011CB3023302);国家高技术研究发展计划(863计划)(批准号:SS2015AA020102)资助的课题~~

摘　　要：复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一,其研究在理论和现实应用中都有重大的意义.在给定s值的前提下,如何寻找发现s个最大影响范围的节点集,这是个组合优化问题,Kempe等已经证明该问题是NP-hard问题.目前已有的随机算法时间复杂度低,但是结果最差;其他贪心算法时间复杂度很高,不能适用于大型社会网络中,并且这些典型贪心算法必须以了解网络的全局信息为前提,而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的.我们提出了一种新的影响力最大化算法模型RMDN,及改进的模型算法RMDN++,模型只需要知道随机选择的节点以及其邻居节点信息,从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题,算法的时间复杂度仅为O(s log(n));然后,我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示,RMDN,RMDN++算法有着和现有典型算法相近的影响力传播效果,且有时还略优,同时在运行时间上则有显著的提高;我们从理论上推导证明了方法的可行性.本文所提出的模型算法适用性更广,可操作性更强,为这项具有挑战性研究提供了新的思路和方法.Influence maximization modeling and analyzing is a critical issue in social network analysis in a complex network environment, and it can be significantly beneficial to both theory and real life. Given a fixed number k, how to find the set size k which has the greatest influencing scope is a combinatory optimization problem that has been proved to be NP-hard by Kempe et al. （2003）. State-of-the-art random algorithm, although it is computation e-cient, yields the worst performance;on the contrary, the well-studied greedy algorithms can achieve approximately optimal performance but its computing complexity is prohibitive for large social network; meanwhile, these algorithms should first acquire the global information （topology） of the network which is impractical for the colossal and forever changing network. We propose a new algorithm for influence maximization computing-RMDN and its improved version RMDN＋＋. RMDN uses the information of a randomly chosen node and its nearest neighboring nodes which can avoid the procedure of knowing knowledge of the whole network. This can greatly accelerate the computing process, but its computing complexity is limited to the order of O（k log（n））. We use three different real-life datasets to test the effectiveness and e-ciency of RMDN in IC model and LT model respectively. Result shows that RMDN has a comparable performance as the greedy algorithms, but obtains orders of magnitude faster according to different network; in the meantime, we have systematically and theoretically studied and proved the feasibility of our method. The wider applicability and stronger operability of RMDN may also shed light on the profound problem of influence maximization in social network.

关 键 词：复杂网络 影响力最大化 信息传播 贪心算法 

分 类 号：O157.5[理学—数学]