高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

许宇光, 蒋飞, 朱恩强, 潘惊治, 谢惠扬. 基于个体稳定度博弈的动态社区发现算法研究[J]. 电子与信息学报, 2017, 39(4): 763-769. doi: 10.11999/JEIT161077
引用本文: 许宇光, 蒋飞, 朱恩强, 潘惊治, 谢惠扬. 基于个体稳定度博弈的动态社区发现算法研究[J]. 电子与信息学报, 2017, 39(4): 763-769. doi: 10.11999/JEIT161077
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 and 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 and Information Technology, 2017, 39(4): 763-769. doi: 10.11999/JEIT161077

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

doi: 10.11999/JEIT161077
基金项目: 

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

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

Funds: 

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

  • 摘要: 在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题,提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中,网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态,使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题,该文提出了格局检测(Configuration checking)等优化策略,从而大大提高了演化网络的社区发现的效率。最后,在真实演化网络的实验中,与最新的静态和动态社区发现方法进行对比,验证了PDG方法的效率和效果。
  • 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.
  • 加载中
计量
  • 文章访问数:  673
  • HTML全文浏览量:  43
  • PDF下载量:  564
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-13
  • 修回日期:  2017-02-22
  • 刊出日期:  2017-04-19

目录

    /

    返回文章
    返回

    官方微信,欢迎关注