郭 峰 尤凯丽 李昕泽

（北方工业大学信息学院 北京 100000）

1 引言

社区发现是复杂网络［1～3］及数据挖掘领域中关键的研究内容。社区结构［4～6］作为复杂网络的共同特征，是网络图中最普遍、最重要的属性之一，表现在社区内部节点之间的连接要比社区外其他部分节点的连接要更加紧密［5］。通过社区发现可以帮助我们了解和分析病毒传播行为，有助于推断病毒的传播机制，从而快速地采取有效防范、制定应对措施。社区发现问题具有重要的研究价值和科学意义，近年来，如何对社区结构进行快速、准确地划分成为众多学者研究的热点。

社区结构具有一些明显的属性和特征［7］，使得在重叠社区划分方法上出现不同的优秀思想。2002年，Girvan和Newman基于分裂思想提出经典的GN算法［8］，为复杂网络研究开辟了新的道路；2005年，Palla等对原有非重叠社区发现方法进行扩展，首次提出基于派系过滤思想的重叠社区发现算法CPM［9］。随后，各种重叠社区发现思想层出不穷，典型算法有围绕CPM算法中寻找相邻k阶完全子图的核心思想，Farkas等提出对加权网络的社区划分算法CPMm［10］、Kumpula等提出快速的派系过滤算法SCP［11］等。2007年Raghavan首次运用标签传播思想对图进行划分，提出著名的非重叠社区发现算法LPA［12］。其后，在LPA算法基础上，Steve等引入多标签和隶属度概念提出重叠社区发现算法COPRA［13］；Xie等引入Listener和Speaker概念提出SLPA算法［14］；Xie等结合派系相似度，以派系为载体进行标签传播，提出CSLPA算法［15］等。

局部扩展方法是重叠社区发现任务中比较常用且成功的策略之一。……