Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

XU Yuguang; JIANG Fei; ZHU Enqiang; PAN Jingzhi; XIE Huiyang

doi:10.11999/JEIT161077

Volume 39 Issue 4

Apr. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(4): 763-769

XU Yuguang, JIANG Fei, ZHU Enqiang, PAN Jingzhi, XIE Huiyang. Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game[J]. Journal of Electronics & Information Technology, 2017, 39(4): 763-769. doi: 10.11999/JEIT161077

Citation:

XU Yuguang, JIANG Fei, ZHU Enqiang, PAN Jingzhi, XIE Huiyang. Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game[J]. Journal of Electronics & Information Technology, 2017, 39(4): 763-769. doi: 10.11999/JEIT161077

Citation:

PDF( 2897 KB)

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

doi: 10.11999/JEIT161077

1.
(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)
2.
(College of Science, Beijing Forestry University, Beijing 100083, China)

Funds:

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

Received Date: 2016-10-13
Rev Recd Date: 2017-02-22
Publish Date: 2017-04-19

Abstract

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.
- Dynamic community detection,
- Permanence,
- Modularity,
- Game theory,
- Configuration checking

FullText(HTML)

References(32)

References

BARABSI A and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. doi: 10.1126/ science.286.5439.509.

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.

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.

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.

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.

FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2009, 486(3/5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.

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.

PALLA G and VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667. doi: 10.1038/ nature05670.

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.

NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(1/2): 40-45. doi: 10.1137 /S003614450342480.

王莉, 程学旗. 在线社会网络的动态社区发现及演化[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.

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.

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.

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.

PALLA G, DERNYI 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.

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.

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.

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.

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.

冷作福. 基于贪婪优化技术的网络社区发现算法研究[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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

Relative Articles

Supplements(0)

Cited By

Proportional views