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

第39 卷第4 期 电 子 与 信 息 学 报 Vol.39No.4 2017 年4 月 Journal of Electronics Information Technology Apr. 2017 基于个体稳定度博弈的动态社区发现算法研究 许宇光① 蒋 飞① 朱恩强① 潘惊治① 谢惠扬*② ①(北京大学信息科学技术学院 北京 100871) ②(北京林业大学理学院 北京 100083) 摘 要：在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题，提 出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中，网络中的每个节点都是一个独立个体。个体会根据 网络中的其他个体的状态，使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题，该文提出了 格局检测(Configuration checking)等优化策略，从而大大提高了演化网络的社区发现的效率。最后，在真实演化网 络的实验中，与必威体育精装版的静态和动态社区发现方法进行对比，验证了PDG 方法的效率和效果。 关键词：动态社区发现；稳定度；模块度；博弈论；格局检测 中图分类号： TP393 文献标识码： A 文章编号：1009-5896(2017)04-0763-07 DOI: 10.11999/JEIT161077 Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game ① ① ① ① ② XU Yuguang JIANG Fei ZHU Enqiang PAN Jingzhi XIE Huiyang ① (School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China) ② (College of Science, Beijing Forestry University, Beijing 100083, China) 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 dynami