基于个体稳定度博弈的动态社区发现算法研究

doi:10.11999/JEIT161077

Abstract
Figure/Table
References (30)
Related Citation (15)

Download: PDF (2897 KB)
Export: BibTeX | EndNote (RIS)

Abstract

In dynamic networks, detecting community structure is a complicated and vital issue. With respect to the community detection problem in dynamic networks, a novel game-theoretic algorithm based on the permanence of agents called Permanence Dynamic Game (PDG) is proposed. In PDG algorithm, each node in the dynamic network is regarded as a self-fish agent. Every agent chooses the best response strategy to select communities he will belong to according to the statuses of other agents. For the evolution of community structure in dynamic networks, the optimization strategy of configuration checking is applied. The configuration checking strategy have many improves the efficiency of the original algorithm. Finally, to verify the effectiveness and efficiency of the proposed method, the method is compared with the state-of-art community detection algorithms on real dynamic networks.

Key words： Dynamic community detection Permanence Modularity Game theory Configuration checking

Received: 13 October 2016 Published: 07 March 2017

PACS:

TP393

Fund:

National Key Research and Development Project of China (2016YFB0800700)

Corresponding Authors: XIE Huiyang E-mail: xhyang@bjfu.edu.cn

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	XU Yuguang
	JIANG Fei
	ZHU Enqiang
	PAN Jingzhi
	XIE Huiyang

Cite this article:

XU Yuguang,JIANG Fei,ZHU Enqiang等. Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game[J]. JEIT, 2017, 39(4): 763-769.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT161077 OR http://jeit.ie.ac.cn/EN/Y2017/V39/I4/763

[1]	BARABÁSI A and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. doi: 10.1126/ science.286.5439.509.
[2]	WATTS D J, DODDS P S, and NEWMAN M E. Identity and search in social networks[J]. Science, 2002, 296(5571): 1302. doi: 10.1126/science.1070120.
[3]	WU X, ZHU X, WU G Q, et al. Data mining with big data[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(1): 97-107. doi: 10.1109/TKDE.2013.109.
[4]	BURKE M, MARLOW C, LENTO T. Social network activity and social well-being[C]. International Conference on Human Factors in Computing Systems, Atlanta, Georgia, USA, 2010: 1909-1912. doi: 10.1145/1753326. 1753613.
[5]	GIRVAN M and NEWMAN M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826. doi: 10.1073/pnas.12653799.
[6]	FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2009, 486(3/5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.
[7]	XIN Y, XIE Z Q, YANG J, et al. An adaptive random walk sampling method on dynamic community detection[J]. Expert Systems with Applications, 2016, 58: 10-19. doi: 10.1016/ j.eswa.2016.03.033.
[8]	PALLA G and VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667. doi: 10.1038/ nature05670.
[9]	ZAKRZEWSKA A. A dynamic algorithm for local community detection in graphs[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015: 559-564. doi: 10.1145/2808797. 2809375.
[10]	NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(1/2): 40-45. doi: 10.1137 /S003614450342480.
[11]	王莉, 程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报, 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015. 00219.
	WANG Li and CHENG Xueqi. Dynamic community in online social networksp[J]. Chinese Journal of Computers, 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015.00219.
[12]	CHAKRABORTY T, SRINIVASAN S, GANGULY N, et al. On the permanence of vertices in network communities[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, USA, 2014: 1396-1405. doi: 10. 1145/2623330.2623707.
[13]	NEWMAN M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582. doi: 10.1073/pnas.0601602103.
[14]	CHEN M, KUZMIN K, SZYMANSKI B K, et al. Community detection via maximization of modularity and its variants[J]. IEEE Transactions on Computational Social Systems, 2015, 1(1): 46-65. doi: 10.1109/TCSS.2014.2307458.
[15]	PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818. doi: 10.1038/nature03607.
[16]	ROSVALL M and BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123. doi: 10.1073/ pnas.0706851105.
[17]	HELD P, KRAUSE B, KRUSE R, et al. Dynamic clustering in social networks using Louvain and Infomap method[J]. arXiv.org, 2016, arXiv: 1603.02413.
[18]	RAGHAVAN U N, ALBERT R, KUMARA S, et al. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76(3 Pt 2): 036106. doi: 10.1103/PhysRevE.76.036106.
[19]	ALVARI H, HASHEMI S, and HAMZEH A. Detecting Overlapping Communities in Social Networks by Game Theory and Structural Equivalence Concept[M]. Iran, Springer Berlin Heidelberg, 2011: 620-630. doi: 10.1007/978- 3-642-23887-1_79.
[20]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112. 2014.04.016.
	LENG Zuofu. Community detection in complex networks based on greedy optimization[J]. Acta Electronica Sinica, 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112.2014.04. 016.
[21]	XIE J, KELLEY S, SZYMANSKI B K, et al. Overlapping community detection in networks: The state-of-the-art and comparative study[J]. ACM Computing Surveys, 2011, 45(4): 115-123. doi: 10.1145/2501654.2501669.
[22]	SUN J, FALOUTSOS C, PAPADIMITRIOU S, et al. GraphScope: Parameter-free mining of large time-evolving graphs[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, 2007: 687-696. doi: 10.1145/1281192.1281266.
[23]	XIE J, CHEN M, and SZYMANSKI B K. LabelRankT: Incremental community detection in dynamic networks via label propagation[C]. The Workshop on Dynamic Networks Management and Mining, 2013: 25-32. doi: 10.1145/2489247. 2489249.
[24]	CAZABET R, AMBLARD F, HANACHI C, et al. Detection of overlapping communities in dynamical social networks[C]. IEEE Second International Conference on Social Computing, Socialcom/IEEE International Conference on Privacy, Security, Risk and Trust, Passat 2010, Minneapolis, Minnesota, USA, 2010: 309-314. doi: 10.1109/SocialCom. 2010.51.
[25]	LIN Y R, CHI Y, ZHU S, et al. FacetNet: A framework for analyzing communities and their evolutions in dynamic networks[C]. Proceedings of the 17th International Conference on World Wide Web, Beijing, China, 2008: 685-694. doi: 10.1145/1367497.1367590.
[26]	LÃQ D, YONG H C, SOONG B H, et al. An Introduction to Game Theory[M]. Switzerland, Potential Game Theory. Springer International Publishing, 2016, Chapter 1. doi: 1007/978-3-319-30869-2_1.
[27]	NEWMAN M E and GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2 Pt 2): 026113-026113. doi: 10.1103/PhysRevE.69.026113.
[28]	BARTHELEMY M and FORTUNATO S. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36-41. doi: 10.1073/pnas.0605965104.
[29]	AGARWAL G and KEMPE D. Modularity-maximizing graph communities via mathematical programming[J]. Physics of Condensed Matter, 2008, 66(3): 409-418. doi: 10. 1140/epjb/e2008-00425-1.
[30]	CAI S and SU K. Local search for Boolean satisfiability with configuration checking and subscore[J]. Artificial Intelligence, 2013, 204(9): 75-98. doi: 10.1016/j.artint.2013.09.001.