李 明，陈 梅，张 梅

(兰州交通大学 电子与信息工程学院，兰州 730070)

社团检测可以发现复杂网络中结构或功能相似的模块[1]，对复杂网络进行社团检测可以揭示网络隐含的结构和潜在的功能，有极为重要的现实意义[2].研究人员提出了大量的社团检测算法，主要有基于模块度[3]、基于标签传播[4]、基于随机游走[5]和基于相邻节点关系[6]的社团检测算法.基于模块度的方法有追求模块度最大化的Fast Q[3]算法；基于标签传播的方法有根据节点邻居更新节点标签的LPA(label propagation algorithm,LPA)[4]算法；基于随机游走的约束游走过程的Synwalk[5]算法；基于节点间关系的社团检测算法有Black Hole[7]算法、DA(a divide and agglomerate algorithm,DA)[8]算法和棒不打鸳鸯[6]算法.

由于基于节点间关系的社团检测算法可以从网络的拓扑结构层面发现社团结构[8]，近年来，研究人员提出了大量该类的社团检测算法.基于节点间引力与斥力的Black Hole算法通过得到使得整个网络合力最小的分布来检测社团结构；基于全局局部关系的DA算法侧重于同时从全局和局部角度考虑检测社团结构，并在分配无类标节点时利用节点间的影响力对其进行分配[9]；棒不打鸳鸯算法则从“两个互近邻节点极有可能属于同一个社团”出发生成树状图并剪枝检测社团结构.然而，当需要检测任意结构任意规模的网络时，这些算法就难以检测到准确的社团结构了.

为了检测任意结构任意规模的社团，本文提出了一种简单、高效和时间复杂度低的基于k最近邻发现社团主干的社……