Efficient Epidemic Spreading Model Based LPA Threshold Community Detection Method
DENG Xiao-long1, WEN Ying2
1. Key Lab of Trustworthy Distributed Computing and Service of Education Ministry, Beijing University of Post and Telecommunication, Beijing 100876, China;
2. Department of International School, Beijing University of Post and Telecommunication, Beijing 100876, China
Community detection method is significant to character statistics of complex network.Community detection in inhomogeneous structured network is an attractive research problem while most previous approaches attempted to divide networks into communities which are based on node or edge measurement.The label propagation algorithm (LPA) adopts semi-supervised machine learning and implemented community detection in an intelligent way with automatic convergent process of network node label iteration but it often results in low efficiency in the final convergent process.In this article,aiming to promote low efficiency and stagnant converging rate of LPA in network with overlapping communities,we propose a new method (ESLPA) for community detection using epidemic spreading model combined with network connection matrix's largest Eigenvalue as label propagation threshold.Extensive experiments in synthetic signed network and real-life large networks derived from online social media are conducted to explore optimal mechanism of the most suitable community detecting virus infection threshold.Experiments result prove that our method is more accurate and faster than several traditional modularity based community detection methods such as COPRA,GN,FastGN and CPM.
[1] ZHU X,Ghahramani Z,Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[A].Proceedings of the Twentieth International Conference on Machine Learning[C].Washington DC,USA:AAAI,2003.912-919.
[2] Usha Nandini Raghavan,R'eka Albert,Soundar Kumara.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106,1-11.
[3] Steve Gregory.Finding overlappingcommunities in networks by label propagation[J].New J Phys,2010,12(10):103018,1-26.
[4] 金弟,刘大有,等.基于局部探测的快速复杂网络聚类算法[J].电子学报,2011,39(11):2540-2546. Jin Di,Liu Dayou,et al.Fast complex network clustering algorithm using local detection[J].Acta Electronica Sinica,2011,39(11):2540-2546.(in Chinese)
[5] Cordasco G,Gargano L.Community detection via semi-synchronous label propagation algorithms[A].Proceedings of 2010 IEEE International Workshop on Business Applications of Social Network Analysis[C].Bangalore,India:IEEE Computer Society,2010.45-50.
[6] William O Kermack,Anderson G McKendrick.Contributions to the mathematical theory of epidemics,part I[J].Proceedings of the Royal Society of London,Series A,1927,115(772):700-721.
[7] William O Kermack,Anderson G McKendrick.Contributions to the mathematical theory of epidemics,part Ⅱ.The problem of endemicity[J].Proceedings of the Royal Society of London,Series A,1932,138(834):55-83.
[8] 顾亦然,夏玲玲.在线社交网络中谣言的传播与抑制[J].物理学报.2012,61(23):238701,1-7. Gu Yi-Ran,Xia Ling-Ling.The propagation and inhibition of rumors in online social network[J].Acta Phys Sin,2012,61(23):238701,1-7.(in Chinese)
[9] 王超,杨旭颖,等.基于SEIR的社交网络信息传播模型[J].电子学报,2014,11(1):2325-2330. Wang Chao,Yang Xuying,et al.SEIR-based model for the information Spreading over SNS[J].Acta Electronica Sinica,2014,11(1):2325-2330.(in Chinese)
[10] Yang Wang,Deepayan Chakrabarti,Chenxi Wang.Epidemic spreading in real networks:An eigenvalue viewpoint[A].Proceedings of 22nd Symposium in Reliable Distributed Computing[C].Florence Italy:Institute of Electrical and Electronics Engineers Computer Society,200.25-34.
[11] Jure Leskovec,Kevin J Lang,Michael W.Mahoney.Empirical comparison of algorithms for network community detection[A].Proceedings of WWW ACM 2010[C].Raleigh,NC:Association for Computing Machinery,2010.631-640.
[12] R Pastor-Satorras,A Vespignani.Epidemic dynamics infinite size scale-free networks[J].Physical Review E,2002,65(3):035108,1-4.
[13] Liaoruo Wang,Tiancheng Lou,Jie Tang,John E Hopcroft.Detecting community kernels in large social networks[A].Proceedings of 2011 IEEE 11th International Conference on Data Mining[C].Vancouver,BC,Canada:Institute of Electrical and Electronics Engineers Inc,2011.784-793.
[14] Michael R Garey,David S Johnson.Computers and Intractability:A Guide to the Theory of NP-Completenes[M].San Francisco:W HFreeman Company,1979.90-194.
[15] Girvan M,Newman MEJ.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[16] Andrea Lancichinetti,Santo Fortunato,Filippo Radicchi.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110,1-5.
[17] Leon Vicsek Danon,Jordi Duch,Alex Arenas,Albert Diaz-Guilera.Comparing community structure identification[J].Journal of Statistical Mechanics Theory & Experiment,2005,09:P09008,1-10.
[18] 杨博,刘大有,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66. Yang Bo,Liu Dayou,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1):54-66.(in Chinese)
2016, Vol. 44 
