## 大规模网络中社区结构的近线性时间检测算法 （标签传播算法（LPA））

大规模网络中社区结构的近线性时间检测算法 （标签传播算法（LPA））

一、引言
各种各样的复杂系统可以表示为网络。例如社交网络用节点表示人，用边表示人与人之间的关系;而生物网络通常用生物化学分子表示为节点，用边缘表示它们之间的反应。近年来的研究大多集中在了解网络的演化和组织，以及网络拓扑对系统动力学和行为的影响。在网络中寻找社区结构是理解它们所代表的复杂系统的另一步。现在对于社区结构没有明确的定义，暂且理解为一个团体。
二、标签传播算法介绍
每个节点都初始化一个唯一的标签，在算法的每次迭代中，每个节点都采用其最大邻居数的标签，且节点间的关系均匀随机断开。随着标签以这种方式在网络中传播，密集相连的节点群对其标签形成共识。在算法的最后，具有相同标签的节点被分组在一起作为社区。正如我们将展示的，这种算法的优点是它的简单和时间效率的其他方法。该算法使用网络结构来指导其进程，并没有优化任何特定的选择的社区力量的措施。此外，社区的数量和大小是不预先知道的，并在算法结束时确定。
标签传播算法背后的主要思想如下。假设一个节点x有邻居x1,x2，…每个邻居都有一个标签，表示他们所属的社区。然后x根据其邻居的标签来确定其社区。假设网络中的每个节点都选择加入其最大邻居数量所在的社区，并均匀随机断开连接。我们用唯一的标签初始化每个节点，并让这些标签在网络中传播。随着标签的传播，密集连接的节点群很快就会对唯一的标签达成一致意见，如图2所示。

这个图很形象的描述了标签传播算法的思想，注意在第二个图右下角的节点变成a，是因为当节点的邻居标签数量都相同时，便随机选一个邻居节点的标签作为他的标签。在最后，拥有相同标签的节点组分成一个社区。

LPA标签传播分为两种传播方式，同步更新，异步更新。注意，同步更新会出现一种问题，就是当网络中结构为二分图或近二分图的子图会导致标签震荡，就是下面这种情况：

你会发现在t+1次迭代时，与第t次相比较，左边节点组的标签和右边节点组的标签交换了，这就是标签震荡现象。解决的办法是设置迭代次数，提前结束迭代。而我们目前大多是用异步传播。
理想情况下，迭代过程应该一直持续到网络中没有节点改变其标签为止。然而，网络中可能存在在两个或更多社区中拥有相同最大邻居数量的节点。由于我们在可能的候选节点中随机断开连接，因此即使相邻节点的标签保持不变，这些节点上的标签也会随着迭代而改变。因此，我们进行迭代过程，直到网络中的每个节点都有一个其最大邻居数所属的标签。通过这样做，我们将网络划分为互不相连的社区，其中每个节点在其社区中拥有的邻居至少与它在其他社区中的邻居一样多。如果C1,…Cp为网络中当前活跃的标签，
为节点i与标签为Cj的节点的邻居数，则对于每个节点i，
这其实就是上方加粗语句的公式化描述。

以下是标签传播算法步骤的具体描述：

标签传播算法的优缺点很明确，优点是算法逻辑简单，时间效率高，不需要预先知道社区的大小以及社区信息，缺点是随机性强，容易产生多个社区。因此我们需要引入一个检测机制来判断划分社区的好坏。本文用的是Jaccard index（杰卡德系数）、模块度Q，这两个部分对于社区挖掘非常重要。大家可以看一下。

对于获得的多个社区结构，将他们聚合可以提供包含最有用信息的社区结构。当我们聚合两个解决方案时，如果一个解决方案中的社区T在另一个解决方案中分成两个不同的社区s1和s2，然后通过定义如上所述的新标签，我们更倾向于较小的社区s1和s2而不是T。这只是聚合不同解决方案的多种方式之一。

三、社区结构的检测
因为目前我们已经知道空手道俱乐部和美国橄榄球网络中的社区结构，因此，我们将根据标签传播算法获得的社区结构与这两个已知的社区结构比较，发现可以有效地挖掘出各自的基本社区结构网络。

四、时间复杂度
算法运行到完成需要一段近似线性的时间。用唯一的标签初始化每个节点需要O（n）时间。标签传播算法的每一次迭代都需要以[O（m）]为单位的线性时间。在每个节点x，我们首先根据相邻节点的标签[O（dx）]对其进行分组。然后我们选择最大的组并将其标签分配给x，这需要最坏情况下的时间O（dx），该过程在所有节点上重复，因此每次迭代的总时间为O（m）。