吴卫江，桑睿彤+，郑艺峰,3,4

(1.中国石油大学(北京) 石油数据挖掘北京市重点实验室，北京 102249；2.中国石油大学(北京) 信息科学与信息工程学院，北京 102249；3.闽南师范大学数据科学与智能应用福建省高等学校重点实验室，福建 漳州 363000；4.闽南师范大学 计算机学院，福建 漳州 363000)

0 引 言

社区发现是复杂网络研究的热点问题之一，大多数传统方法主要针对整个网络[1-3]，进行全局遍历，从而找出网络内部内聚性高且网络剩余部分相对分离的节点簇。其不足之处在于，算法的时间复杂度较高。现有方法包括模块度最大化算法[4-6]、谱聚类算法[7,8]和标签传播算法[9,10]等等。需要注意的是，从大规模的网络中获取全局信息较为困难，因此，全局算法不适用于大型网络。为了解决上述问题，研究人员转向大型网络的局部结构(即局部社区发现算法)，从目标社区中已知的少数成员开始，恢复社区中的剩余成员。研究表明，基于种子集扩展的方法[11]可有效发现局部社区，具体包括局部谱方法[12]、个性化PageRank方法[13]和热核扩散方法[14]等等。上述方法能有效降低大型网络的时间复杂度，但对于目标社区恢复的准确度还有待提高。为此，本文提出局部社区发现方法(LRW-LSA)，采用限制性随机游走作为大型图探索的预处理步骤，从而得到较小范围的子图以降低计算复杂度。同时，结合快速聚类融合方法，进一步提高子图对要恢复社区的覆盖率。最后，使用Lanczos方法进行快速迭代恢复得到局部社区。

1 相关研究

基于PageRank的局部社区发现是一种经典的局部社区发现算法。……