张应龙，夏学文，徐 星，喻 飞，吴泓润，余 鹰

1(闽南师范大学 物理与信息工程学院，福建 漳州 363000)

2(华东交通大学 软件学院，南昌 330013)

1 引 言

社团检测是网络研究分析中的一项重要任务[1，2]，它以介观尺度观察和理解网络，有助于分析挖掘团体之间的关系动态、模式和功能，找到隐藏的内在关系与规律并预测复杂网络的行为，从而更好的理解复杂网络.相关术语有社团、社区、图划分、聚团或群组结构等，本文对这些概念统一称之为社团.

自从Newman等人提出社团概念[3]以来，产生了海量的社团检测算法[4]，可分为全局优化和局部优化两大类[5]局部优化通过网络的局部拓扑结构特征，来揭示局部或整个网络的社团结构.相较于全局优化方法，局部优化不仅无需整体的网络结构信息及先验知识的辅助，而且在计算代价、挖掘局部社团特性等方面存在更多优势[5，6].

标签传播算法Label Propagation Algorithm(LPA)[7]凭借其简洁原理及近乎线性的时间代价等优点，成为局部优化方法的代表.在过去的十几年中，研究者发表了大量相关的工作.

目前优秀的社团检测综述[4-5，8-11]尚未重点关注LPA算法.文献[4，8]从全局的角度分析了社团检测研究现状.文献[5，11]概括了局部优化的社团检测方法.文献[9，10]重点介绍了动态社团检测方法.尽管这些综述有助于了解社团检测研究现状，然而缺乏对LPA算法这一分支的详细介绍、分析与总结.

鉴于上述，有必要系统分析与总结标签传播算法研究现状、面临问题以及前景，从而为其……