陈界全 王占全* 李 真 汤敏伟

1(华东理工大学信息科学与工程学院 上海 200237) 2(天翼电子商务有限公司风险管理部 上海 200080)

0 引 言

社区检测是一种在网络中探索集群或社区的行为。集群或者社区是一组紧密连接的实体，它们在组内的连接比与其他实体的连接更高[1]。对各种领域的真实网络进行社区的发现，对于理解复杂网络的结构和模式起着重要的作用。例如，在社交网络领域，可以根据不同的兴趣和背景将其划分为不同的社会群体进行准确的推荐；在生物学领域，传播网络由疾病和病毒两部分组成，通过对其进行研究和分析，找到易感染人群的关键社区或关键节点，预测传播路径，从而及时控制疾病。综上所述，社区检测在复杂网络的研究中有重要意义。

然而，目前的研究主要集中在检测非重叠的社区，然而真实社交网络中的社区通常是互相重叠的[2]。例如，一个研究者可能属于多个研究群组中，一个人在现实生活或者网络中会加入多个兴趣小组。所以，重叠社区的发现对于进一步分析和利用复杂网络结构具有重要的意义，重叠社区如图1所示。

图1 重叠社区

本文提出一种改进的重叠社区发现算法(L-SLPA)，其扩展了SLPA，在算法的初始阶段先对网络进行一次非重叠社区划分，然后给同一社区中的节点分配相同的标签，而不是像SLPA一样给所有的节点分配不同的标签。标签分配完成后，仅对边界节点执行Speaker-Listener标签传递的迭代过程，最后对各节点包含的所有标签进行过滤。……