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

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

作　　者：许宇光[1] 蒋飞[1] 朱恩强[1] 潘惊治 谢惠扬[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]北京林业大学理学院,北京100083

出　　处：《电子与信息学报》2017年第4期763-769,共7页Journal of Electronics & Information Technology

基　　金：国家重点研发计划项目(2016YFB0800700)~~

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

关 键 词：动态社区发现 稳定度 模块度 博弈论 格局检测 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]