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.
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.
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.
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.
