稳定的标签传播社团划分算法研究

张 猛，李玲娟

(南京邮电大学 计算机学院，江苏 南京 210023)

0 引 言

现实世界中的事物都可以用复杂网络模型来表示，例如人与人之间的社会关系、细胞之间的生物关系和万维网之间的链接结构等。随着对网络性质的深入研究，人们发现许多网络都存在着社团结构，其特征是同一社团内节点连接紧密，不同社团间节点连接稀疏[1-2]。揭示网络中的社团结构，对于了解网络结构、分析网络特性和发现复杂网络中潜在的关系等都具有非常重要的意义。

因此，近年来研究人员提出了许多社团划分算法。文献[3]提出了基于边介数的GN算法，基本思想是社团内边介数较小，社团间边介数较大。GN算法的时间复杂度为O(m2n)，其中m代表网络中的边数，n代表网络中的节点数，该算法不适合用于大规模网络。文献[4]基于模块度函数Q提出了一个快速层次聚类算法FastQ，该算法的时间复杂度为O((m+n)n)，提高了社团划分的效率。文献[5]首次提出使用派系过滤算法CPM挖掘网络中的重叠社团结构，其基本思想是认为社团结构由相邻的派系(完全子图)构成，通过寻找相互连通的k-派系方法发现社团结构。文献[6]提出了基于标签传播的社团划分算法LPA(label propagation algorithm)，该算法的时间复杂度近似线性。

LPA算法非常适用于大规模网络，但是该算法在标签传播过程中存在随机性，严重影响了算法划分结果的稳定性。针对这一问题，文献[7]提出带约束的标签传播算法LPAm，将LPA算法转换为优化问题，但是该算法容易使目标函数模块度陷入局部最优。文献[8]提出了LPAm+算法，采用同时合并多个社团策略来避免局部最优。文献[9]提出了基于标签熵的标签传播方法LPA-E(label propagation in entropic order)，将节点按照标签的熵升序进行更新，降低了LPA算法的随机性。文献[10]基于网络预处理的改进标签传播算法KLPA(improved label propagation algorithm based on network preprocessing)预处理阶段删除了网络中的某些节点，一定程度上破坏了网络的原始结构。

虽然上述方法某种程度上能提高LPA算法的准确性、稳定性或者收敛速度，但是并未消除LPA算法的随机性。

文中设计了一种稳定的标签传播社团划分算法S-LPA(a stable label propagation community division algorithm)，综合考虑节点的局部信息和全局信息，计算节点综合影响力，按照综合影响力对节点标签进行更新。然后在标签传播过程中根据标签影响力大小进行标签更新，减少算法的随机性，提高算法的稳定性和准确性。

1 相关知识

1.1 LPA算法

LPA算法是一种基于图的半监督学习方法，基本思想是用邻居节点的标签信息来预测待更新节点的标签信息。该算法在初始阶段给每个节点分配唯一标签，然后随机选择节点进行标签更新；在标签更新过程中，每个节点根据式1选择邻居节点中出现次数最高的标签进行标签更新，其中li表示待更新节点i的标签，N(i)表示节点i的邻居节点集，lj表示节点i邻居节点j的标签，δ(lj,l)为克罗内克函数。

(1)

若次数最多的标签有多个，则随机选择一个标签作为待更新节点的标签；最后经多次迭代至所有节点标签不再变化时，拥有相同标签的节点属于一个社团。

在LPA标签更新过程中存在两种标签更新方式，分别为同步更新和异步更新。同步更新是指在第t次迭代时，待更新节点的标签由其邻居节点在第t-1次迭代时的标签所决定，这种方式应用在具有二分结构的网络上会产生标签震荡现象。异步更新是指在第t次迭代时，待更新节点的标签由其邻居节点在第t-1次和第t次迭代时的标签共同决定，这种方式可以避免标签震荡现象。

1.2 LPA存在的问题

LPA算法时间复杂度低，但是在算法中所存在的随机策略会导致每次运行所产生的结果不尽相同，有时会产生一些琐碎的、无意义的社团结构，影响了算法的准确性和稳定性。LPA算法随机策略主要存在于两个方面：

(1)在标签初始化时，LPA算法给网络中的每个节点分配一个唯一标签，将节点随机排列得到一个节点序列并以此作为初始节点更新顺序。每次迭代时节点的更新顺序都是随机的，而LPA算法对节点更新顺序又非常敏感。这种更新顺序忽略了节点自身的重要性差异，使得重要性较小的节点可能影响重要性较大的节点，产生标签“逆流”现象。

(2)在标签更新过程中，当待更新节点的邻居节点中次数最多的标签有多个时，LPA算法随机选择一个标签作为待更新节点的标签，没有考虑邻居节点信息对标签选择的影响。

2 S-LPA算法

为了减少算法的随机性，提高LPA算法的准确性和稳定性，文中设计了一种稳定的标签传播社团划分算法S-LPA。该算法在保留LPA算法具有的线性时间复杂度的基础上，结合节点局部影响力、全局影响力以及标签影响力对LPA算法进行改进。首先在节点初始化时，按照节点综合影响力升序排序；其次当候选标签有多个时，根据其标签影响力大小进行标签更新，减少标签更新过程中的随机性。

2.1 节点综合影响力

(1)K-Shell算法。

评价复杂网络中节点影响力的方法有度中心性、介数中心性、PageRank等，但是这些评价方法都存在一定的局限性。例如度中心性方法没有将节点在网络中所处的位置考虑在内；介数中心性方法需要计算各节点之间的距离，时间复杂度较高；PageRank对节点影响力排序不唯一。文献[11]提出了K-Shell分解算法，该算法时间复杂度为O(n)，并能准确地衡量节点在网络中的全局影响力。

假设网络中不存在孤立节点，K-Shell算法的一般步骤为：首先删除网络中所有度为1的节点；若在删除过程中出现新的度为1的节点，则继续删除，直到网络中不存在度为1的节点，此时这些被删除的节点的K-Shell值为1；然后以同样的方法删除网络中所有度为2的节点；反复如此，直到网络中所有节点的K-Shell值都被确定，K-Shell值越大，说明节点在网络中所处的位置越核心，其影响力也就越大。

(2)节点综合影响力计算方法。

虽然K-Shell算法能较好地衡量网络中所有节点的影响力，但是K-Shell是一种粗粒度化的节点影响力方法，同一层的节点被赋予相同K-Shell值，其影响力无法区分。为此，文中借鉴文献[12]的思想，结合节点分解时的迭代层数和K-Shell值来衡量节点全局影响力，其公式如下：

IKs(i)=Ks(i)+t(i)

(2)

其中，Ks(i)表示节点i的K-Shell值；t(i)表示删除节点i时的迭代次数；IKs(i)表示节点i的改进的K-Shell值。

改进的K-Shell值能较好地反映节点全局影响力，但是无法反映节点的局部影响力。为了进一步区分和衡量节点影响力，文中融入能反映节点局部信息的节点归一化度值和邻居节点的影响力来综合考虑节点影响力。节点综合影响力公式如下：

(3)

其中，IKs(i)表示改进的K-Shell值；D(i)表示节点的归一化度值；N(i)表示节点i的邻居节点；CI(i)表示节点i的综合影响力。

节点综合影响力综合考虑能反映节点全局影响力的K-Shell值、迭代次数和局部影响力的度值、邻居节点信息，克服了K-Shell算法的缺点，同时拥有近似线性时间复杂度。

2.2 标签影响力

LPA算法在标签更新过程中，待更新节点标签由其邻居节点中出现次数最高的标签所决定；若存在多个竞争标签，则随机选择一个标签作为待更新节点的标签，该方法很大程度上影响了算法的准确性和稳定性，导致在相同的网络上运行多次该算法，得到的结果不尽相同。考虑到邻居节点的影响力越大，邻居节点中具有相同标签个数越多，其标签越容易传播给待更新节点。文中将邻居节点中出现标签的次数和邻居节点影响力相结合来计算标签综合影响力，公式如下：

(4)

其中，Nl(x)表示节点x的标签为l的邻居节点集合。

2.3 S-LPA算法设计与分析

(1)S-LPA算法设计。

稳定的标签传播社团划分算法S-LPA的全部流程如下：

输入：网络G=(V,E)，V代表网络中的顶点，E代表网络中的边，最大迭代次数为t；

输出：社团划分结果。

算法步骤：

①初始化网络中每个节点i∈V的标签；

②根据式2计算每个节点的全局影响力；

③根据式5计算每个节点的归一化度值，其中d(i)表示节点i的度，并根据式3计算每个节点的综合影响力，然后将节点按影响力升序排序；

(5)

④设置迭代次数t=1；

⑤对于网络中节点x，按式4计算其邻居节点中出现的标签的影响力，再按式6，将其标签更新为邻居节点标签集中影响力最大的标签；

(6)

⑥若网络中所有节点的标签不再变化或者迭代次数达到最大值，则算法结束，具有相同标签的节点属于同一社团；否则t+1，返回步骤⑤。

可以看出，S-LPA算法用式3来计算网络中所有节点的综合影响力，并在后续的标签传播过程中按照节点综合影响力升序对标签进行更新。之所以采用升序，是由于S-LPA算法的每一步标签更新基本是稳定的，不存在标签逆流现象，从影响力较小的节点开始更新，使得这些影响力较小的节点的标签与未更新的影响力较大的标签一致。图1(a)是一个包含8个节点的简单网络，分别按综合影响力的升序和降序运行S-LPA算法，结果如图1(b)、(c)所示。经计算，各节点影响力为{1:13.25,3:13.25,5: 13.25,8:13.25,2:16.75,6:16.75,4:21.75,7:21.75}。假设节点4和7的标签分别为a、b，若采用降序，首先更新节点4或7，会导致两社区合并成一个社区；若采用升序，首先更新节点1、3、5和8，对于节点1和3，其标签更新为节点4的标签a，当更新到节点4时，节点4选择邻居中标签影响力最大的标签，此时节点1和3的标签影响力之和(即标签综合影响力)为26.5，大于节点7的标签影响力21.75，节点4标签更新为a；同理节点7的标签更新为b。经过2次迭代，算法达到稳定状态而停止。

(2)S-LPA算法时间复杂度分析。

网络中所有节点初始化标签所需的时间复杂度为O(n)；计算所有节点的改进的K-Shell值的时间复杂度为O(n)，计算节点归一化度值的时间复杂度为O(n)，结合每个节点的邻居节点，所需的时间复杂度为O(dn)，d为网络的平均度值，因此计算所有节点综合影响力的时间复杂度为O(n+n+dn)～O(n)；使用计数排序对节点影响力升序排序，时间复杂度为O(n)；节点一次标签传播的时间为O(m)，m为网络中的边数，最多传播t次，所需时间为O(tm)；节点划分到不同社团所需的时间为O(n)。所以S-LPA算法总的时间复杂度为O(3n+tm)～O(n)，继承了LPA算法时间复杂度近似线性的优点。

(a)简单网络

(b)升序结果

3 实验结果与分析

3.1 实验结果评价指标

(1)模块度。

模块度(Q modularity)[13]是由Newman等提出的用来评价网络社团划分质量的指标。对于一个不含重叠社团结构的网络，模块度定义如下：

(7)

其中，m表示网络中的边数；Aij表示网络的邻接矩阵；ki、kj分别表示节点i、节点j的度值；δ(i,j)为克罗内克函数，当节点i和节点j属于同一社团时，δ(i,j)=1，节点i和节点j不属于同一社团时，δ(i,j)=0。模块度的取值为0～1，值越接近1，说明社团划分的质量越好。

(2)标准化互信息。

标准化互信息(NMI)[14]是基于信息论的社区质量评价指标，可以用来衡量已知社团结构与算法所发现的社团结构之间的相似性。其定义如下：

(8)

其中，X表示真实社团的集合；Y表示算法发现社团的集合；H(X|Y)表示X在Y上的规范化条件熵。标准化互信息的取值为0～1，值越接近1，说明算法发现的社团结构与真实社团结构一致性越高。

3.2 实验结果分析

(1)真实网络数据集上的实验。

实验采用四个真实网络数据集，分别是Zachary空手道俱乐部网络Karate、Lusseau海豚社交网络Dolphins、美国大学足球联赛赛程表网络Football和美国政治书籍网络Polbooks，各自的特征信息如表1所示。

表1 真实网络数据集

文中选择经典的LPA算法、LPA-E算法和KLPA算法同文中算法S-LPA进行对比。由于LPA算法、LPA-E算法和KLPA算法存在随机性，所有实验结果取运行100次后的平均值，文中算法S-LPA运行一次，表2给出了不同算法在四个真实网络数据集上运行时得出的Q值、NMI值，以及平均迭代次数。

表2 真实网络数据集社团划分结果

从表2可以看出，S-LPA算法在四个真实网络上的Q值和NMI值都要好于LPA算法，并且迭代次数也比LPA算法少。其中，在Karate网络中发现的社团结构与实际社团结构一致，通过计算该网络所有节点综合影响力发现：节点1综合影响力最大，为84；节点34综合影响力仅次于节点1，为79.82；而实际情况是，节点1和节点34正好代表俱乐部分裂后分别以管理员和校长为中心的两个社团。综合Q值、NMI值以及迭代次数，S-LPA算法优于LPA-E和KLPA算法，仅仅在Dolphins、Polbooks网络上的Q值和NMI值低于LPA-E、KLPA算法，但是迭代次数比这两个算法少。

(2)人工合成网络上的实验。

为了进一步测试文中算法对不同网络的适用性以及稳定性，使用LFR基准网络生成工具[15]生成两个人工合成网络，分别包含1 000和2 000个顶点，具体参数见表3。

表3 人工合成网络参数

其中，k表示网络的平均度值；maxk表示网络的最大度值；minc和maxc分别表示社团所含节点数的最小值和最大值；mu为混合参数，表示连接不同社团节点的边数占网络总边数的比例，通过设置不同的mu值来测试算法的性能。当mu<0.5时，mu值越小，人工合成的网络社团结构越明显；当mu>0.5时，mu值越大，合成的网络社团结构越模糊。

将S-LPA算法与LPA算法和KLPA算法进行对比，同样，文中算法运行一次，LPA和KLPA算法各运行100次，在节点数N=1 000、2 000和不同mu值下NMI值的变化分别如图2(a)和图2(b)所示。

由图2可以看出，当mu≤0.45时，网络社团结构较为明显，S-LPA算法与LPA算法、KLPA算法相当；当0.5≤mu≤0.6时，网络社团结构渐渐模糊，S-LPA算法的NMI值明显高于LPA算法和KLPA算法；当mu=0.65时，S-LPA在G1网络中的NMI值仍然高于LPA和KLPA算法，而在G2网络中LPA和S-LPA算法失效，KLPA算法的NMI值为0.4；当mu>0.65时，3种算法均失效。总体来说，S-LPA算法在G1和G2人工合成网络上的性能要优于LPA算法和KLPA算法。

为了测试算法的稳定性，分别在N=1 000、2 000和mu=0.5的情况下运行多次LPA算法和S-LPA算法，并统计其平均迭代次数，结果如图3(a)和图3(b)所示。

(a)N=1 000

(b)N=2 000

(a)N=1 000

(b)N=2 000

由图3可以看出，LPA算法在不同运行次数下平均迭代次数均不同，而文中的S-LPA算法在N=1 000和N=2 000的情况下迭代次数都为6次。相比于LPA算法，S-LPA算法不仅降低了LPA算法的随机性，还明显减少了LPA算法的迭代次数。

4 结束语

传统的LPA算法以及一些改进的LPA算法虽然具有近似线性的时间复杂度，但是仍然存在结果不稳定的问题。文中对LPA算法的标签更新序列进行改进，综合考虑节点的局部信息和全局信息，以此来计算节点在网络中的综合影响力，并进一步用标签影响力对LPA算法标签更新策略进行改进。通过在真实的网络数据集和人工合成网络上的实验证明了S-LPA算法仅需运行一次就能得到社团划分结果，并且划分结果的Q值和NMI值优于传统的LPA算法，在继承了LPA算法线性时间复杂度的同时，提高了社团划分的质量，增强了算法的稳定性。