-
复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定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 efficient, 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(klog(n)). We use three different real-life datasets to test the effectiveness and efficiency 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.
-
Keywords:
- complex network /
- influence maximization /
- information diffusion /
- greedy algorithm
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabsi A L, Albert R 1999 Science 286 509
[3] Barabsi A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a
[4] L, L, Zhang Y C, Yeung C H, Zhou T 2011 PloSone 6 e21202
[5] Hu Q C, Yin Y S, Ma P F 2013 Acta Phys. Sin 62 140101(in Chinese) [胡庆成, 尹龑燊, 马鹏斐 2013 62 140101]
[6] Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin 62 128901(in Chinese) [任卓明, 邵凤, 刘建国 2013 62 128901]
[7] Aral S, Walker D 2012 Science 337 337
[8] Liu J G, Ren Z M, Guo Q 2013 Physica A: Statistical Mechanics and its Applications 392 4154
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 6 888
[10] Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175(in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[11] Liu J G, Ren Z M, Guo Q, et al 2013 Acta Phys. Sin. 62 178901(in Chinese) [刘建国, 任卓明, 郭强 等 2013 62 178901]
[12] Domingos P, Richardson M 2001 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, CA, USA, August 26-29, 2001 p57
[13] Richardson M, Domingos P 2002 Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining Edmonton, Alberta, Canada, July 23-26, 2002 p61
[14] DKempe, JKleinberg, ETardos 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137
[15] Leskovec J, Krause A, Guestrin C 2007 Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining San Jose, CA August 12-15, 2007 p420
[16] Goyal A, Lu W, Lakshmanan L V S 2011 Proceedings of the 20th international conference companion on World wide web Johannesburg,South Africa Sep 14-16, 2011 p47
[17] Zhou C, Zhang P, Guo J 2013 Data Mining (ICDM),2013 IEEE 13th International Conference on. IEEE Dallas, Texas, USA Dec 8-11, 2013 p907
[18] Chen W, Wang Y, Yang S2009 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining Paris, France June 28-July 1, 2009 p199
[19] Kimura M, Saito K 2006 Knowledge-Based Intelligent Information and Engineering Systems Bournemouth U K, October 9-11, 2006 p937
[20] Chen W, Wang C, Wang Y 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashingtonDC, USA, July 25-28, 2010 p1029
[21] Wang Y, Cong G, Song G 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashington DC, USA, July 25-28, 2010 p1039
[22] Galstyan A, Musoyan V, Cohen P 2009 Phys. Rev. E 79 056102
[23] Li D, Xu Z M, Chakraborty N 2014 PloS one 9 e102199
[24] Zhou S, Mondragn R J 2004 Commun. Lett. 8 180
[25] Bonacich P 1972 Journal of Mathematical Sociology 2 113
[26] Milgram S 2003 Phys. Rev. Lett. 90 058701
[27] Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S 2012 ACM Web Science 2012: Conference Proceedings Evanston, Illinois, USA, June 2224, 2012 p45
[28] Six Degrees of Separation, Twitter Style fromSysomos Apr 30, 2010
[29] Cohen R, Havlin S 2003 Phys. Rev. Lett. 90 058701
[30] Newman M E J, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 026118
[31] Leskovec J, Mcauley J J 2012 Advances in neural information processing systems South Lake Tahoe, Nevada, United States, December 3-6, 2012 p539
[32] Xie N 2006 Social network analysis of blogs M.Sc. Dissertation, University of Bristol
[33] Li G, Chen S, Feng J 2014 Proceedings of the 2014 ACM SIGMOD international conference on Management of data New York, NY, USA, June 22-25, 2014 p87
[34] Clauset A, Shalizi C R, Newman M E J 2009 SIAM Rev. 51 661
[35] Barabsi A L, Albert R, Jeong H 1999 Physica A 272 173
[36] Newman M E J 2005 Contemporary Physics 46 323
-
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabsi A L, Albert R 1999 Science 286 509
[3] Barabsi A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a
[4] L, L, Zhang Y C, Yeung C H, Zhou T 2011 PloSone 6 e21202
[5] Hu Q C, Yin Y S, Ma P F 2013 Acta Phys. Sin 62 140101(in Chinese) [胡庆成, 尹龑燊, 马鹏斐 2013 62 140101]
[6] Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin 62 128901(in Chinese) [任卓明, 邵凤, 刘建国 2013 62 128901]
[7] Aral S, Walker D 2012 Science 337 337
[8] Liu J G, Ren Z M, Guo Q 2013 Physica A: Statistical Mechanics and its Applications 392 4154
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 6 888
[10] Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175(in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[11] Liu J G, Ren Z M, Guo Q, et al 2013 Acta Phys. Sin. 62 178901(in Chinese) [刘建国, 任卓明, 郭强 等 2013 62 178901]
[12] Domingos P, Richardson M 2001 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, CA, USA, August 26-29, 2001 p57
[13] Richardson M, Domingos P 2002 Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining Edmonton, Alberta, Canada, July 23-26, 2002 p61
[14] DKempe, JKleinberg, ETardos 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137
[15] Leskovec J, Krause A, Guestrin C 2007 Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining San Jose, CA August 12-15, 2007 p420
[16] Goyal A, Lu W, Lakshmanan L V S 2011 Proceedings of the 20th international conference companion on World wide web Johannesburg,South Africa Sep 14-16, 2011 p47
[17] Zhou C, Zhang P, Guo J 2013 Data Mining (ICDM),2013 IEEE 13th International Conference on. IEEE Dallas, Texas, USA Dec 8-11, 2013 p907
[18] Chen W, Wang Y, Yang S2009 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining Paris, France June 28-July 1, 2009 p199
[19] Kimura M, Saito K 2006 Knowledge-Based Intelligent Information and Engineering Systems Bournemouth U K, October 9-11, 2006 p937
[20] Chen W, Wang C, Wang Y 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashingtonDC, USA, July 25-28, 2010 p1029
[21] Wang Y, Cong G, Song G 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashington DC, USA, July 25-28, 2010 p1039
[22] Galstyan A, Musoyan V, Cohen P 2009 Phys. Rev. E 79 056102
[23] Li D, Xu Z M, Chakraborty N 2014 PloS one 9 e102199
[24] Zhou S, Mondragn R J 2004 Commun. Lett. 8 180
[25] Bonacich P 1972 Journal of Mathematical Sociology 2 113
[26] Milgram S 2003 Phys. Rev. Lett. 90 058701
[27] Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S 2012 ACM Web Science 2012: Conference Proceedings Evanston, Illinois, USA, June 2224, 2012 p45
[28] Six Degrees of Separation, Twitter Style fromSysomos Apr 30, 2010
[29] Cohen R, Havlin S 2003 Phys. Rev. Lett. 90 058701
[30] Newman M E J, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 026118
[31] Leskovec J, Mcauley J J 2012 Advances in neural information processing systems South Lake Tahoe, Nevada, United States, December 3-6, 2012 p539
[32] Xie N 2006 Social network analysis of blogs M.Sc. Dissertation, University of Bristol
[33] Li G, Chen S, Feng J 2014 Proceedings of the 2014 ACM SIGMOD international conference on Management of data New York, NY, USA, June 22-25, 2014 p87
[34] Clauset A, Shalizi C R, Newman M E J 2009 SIAM Rev. 51 661
[35] Barabsi A L, Albert R, Jeong H 1999 Physica A 272 173
[36] Newman M E J 2005 Contemporary Physics 46 323
计量
- 文章访问数: 8805
- PDF下载量: 661
- 被引次数: 0
下载:
