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



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

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

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

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

动态社区发现；稳定度；模块度；博弈论；格局检测

1 引言

近年来，随着计算机技术的不断发展和移动互联时代的到来，网络科学，特别是社交网络的研究引起了学术界和工业界的广泛关注。其中，社区发现问题是网络科学研究中的一个关键问题。社区是网络中相互连接紧密的节点集合。在不同类型的网络中，社区有着不同的含义。例如，社交网络中，社区通常代表着具有共同兴趣的群 体[8]。社区结构是在中观层面上理解网络结构的有效途径。社区发现问题无论在理论上还是在应用上都有着十分重要的意义[9]。

社区发现问题是一个非常复杂而繁琐的问题。……