-
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
Catalog
Metrics
- Abstract views: 7282
- PDF Downloads: 652
- Cited By: 0
下载:
