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

许宇光; 蒋飞; 朱恩强; 潘惊治; 谢惠扬

doi:10.11999/JEIT161077

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

doi: 10.11999/JEIT161077

1.
(北京大学信息科学技术学院北京 100871) ②(北京林业大学理学院北京 100083)

基金项目:

国家重点研发计划项目(2016YFB0800700)

计量
- 文章访问数: 1347
- HTML全文浏览量: 171
- PDF下载量: 594
- 被引次数: 0
出版历程
- 收稿日期: 2016-10-13
- 修回日期: 2017-02-22
- 刊出日期: 2017-04-19

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

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)

摘要

摘要: 在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题，提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中，网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态，使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题，该文提出了格局检测(Configuration checking)等优化策略，从而大大提高了演化网络的社区发现的效率。最后，在真实演化网络的实验中，与最新的静态和动态社区发现方法进行对比，验证了PDG方法的效率和效果。
- 动态社区发现 /
- 稳定度 /
- 模块度 /
- 博弈论 /
- 格局检测
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

HTML全文

参考文献(32)

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.

施引文献

资源附件(0)

访问统计