基于节点影响力的标签传播社区检测算法

马 秀，冀庆斌

(中北大学 理学院， 太原 030051)

人们发现复杂网络除了拥有小世界特性和无标度特性外，还具有社区结构[1]的拓扑性质。复杂网络中存在一些特殊的节点组，同一组内节点之间的连接较为稠密，不同组之间节点连接较为稀疏[2]。社区结构的研究有助于发现复杂网络中隐藏着的个体关系。

学者们对复杂网络中社区结构的研究做了大量工作，提出了许多社区检测算法。主要有：Kernighan等[3]提出的试探优化算法，时间复杂度为O(n2)；Girvan等[4]提出的基于边介数的分割算法，时间复杂度为O(n3)；Palla等[5]首次提出检测重叠社区结构的派系过滤算法；Clauset等[6]提出的贪婪算法(CNM算法)，使算法复杂度降为O(nlog2n)，已接近线性复杂度；2007年Raghavan等[7]提出了一种基于标签传播思想的社区检测算法(LPA算法)，时间复杂度为O(m)。该算法具有线性的时间复杂度，提高了在大规模网络社区检测的效率。但是LPA算法中存在的随机性，使得算法划分结果稳定性差。

针对LPA算法存在的问题，许多学者提出改进算法。Barber等[8]提出带约束的模块化标签传播算法LPAm，通过引入一个目标函数H，利用标签传播算法检测H函数的最优解，将社区检测问题转化为目标函数最大值问题；然而LPAm算法可能会将网络划分为相似的社区，导致模块度陷入局部极大值的问题，为了避免这种情况的出现，Liu等[9]将LPAm算法与多步贪婪凝聚算法(MSG)相结合，提出基于模块度专业化的标签传播算法LPAm+，该算法复杂度为O(nlogm2)；Zhao等[10]提出了基于标签熵序列的标签传播算法LPA-E，节点将根据标签熵值从小到大进行更新。这些算法从不同的角度对LPA算法进行了改进，在一定程度上提高了算法的稳定性，但均未考虑网络中节点影响力的差异对标签传播的影响。

本文提出基于节点影响力的标签传播社区检测算法(KLPA算法)，在评价网络中节点影响力的基础上，选取部分影响力大的节点为种子节点，在初始标签分配上改进算法。另外，在标签决策过程中，考虑相同标签节点之间的关系，选择影响力大的标签进行更新。通过在不同数据集上实验结果证明，本文改进的算法减少了随机性，提高了算法的稳定性。

1 相关工作

1.1 标签传播算法的随机性问题

LPA算法的基本过程是：标签初始化时给网络中每个节点分配唯一的标签；在传播过程中，各节点的标签更新为邻接节点中频数最多的标签，当出现多个频数最多的标签时，随机选择一个标签更新该节点；若网络中所有节点的标签均更新为其邻接节点中频数最多的标签时，算法结束，此时标签相同的节点形成一个社区。

分析标签传播算法，我们发现该算法中有两个步骤体现随机性：1)在每一次迭代过程，节点的更新顺序都会重新排列。2)在节点标签更新时，当邻接节点中频数最多的标签出现多个时，采用随机选择策略。这些随机性会增加算法的迭代次数，降低算法的稳定性，导致多次实验的结果有差异性。

针对存在的问题，研究者们通过评价网络中节点的影响力，提出了系列改进算法。如LIB算法[11]提出采用文献[12]的方法，选择网络中前k个影响力较大的节点为初始标签开始传播，但该方法无法直接确定k值；黄佳鑫等[13]在衡量网络中节点重要性时综合考虑点权和集聚系数，但该方法中计算集聚系数增加了标签传播算法的复杂度；IPLPA算法[14]在k-shell分解[15]的基础上，通过综合考虑节点被删除时的迭代层数与邻接节点的度值，构造新的衡量节点重要性的计算方法，指导节点的更新顺序和标签更新策略。与该方法不同，本文通过采用k-shell分解衡量网络中节点的影响力，选择部分k-shell值较大的节点为网络的种子节点，在标签初始化时，只给种子节点分配标签。

1.2 节点影响力分析

网络中节点的影响力具有差异性，快速准确地识别影响力较大的节点，有助于网络中信息更快地传播。很多评价节点影响力的指标被提出：传统的度中心性方法计算复杂度低，但没有考虑节点在网络中所处的位置；介数中心性与接近中心性由于都要计算网络中各节点之间的距离，因此时间复杂度都比较高，不适合用于大规模网络。此外，很多研究中将网页排名算法用于分析网络中节点的影响力排序，比如He等[16]采用PageRank作为节点影响力判定标准，但是该方法存在节点排序不唯一的问题；Lü等[17]提出的LeaderRank解决了PageRank存在的问题，指出利用LeaderRank算法对网络节点影响力排序比PageRank算法排序更精准。Kitsak等提出k-shell分解方法，它是利用节点在整个网络中的位置确定节点的影响力。文献[15]指出采用k-shell分解方法衡量节点的影响力比度和介数更为准确，并且具有线性的时间复杂度，适用于大型网络。

k-shell分解方法具体过程如下：首先，去掉网络中所有度值为1的节点及连边，这时可能会出现一些新的度值为1的节点，再去除这些节点及其连边，直到网络中剩下的节点的度值都大于1为止，这些被去掉的点及其之间的连边称为1-shell；随后继续分解，去掉度值小于等于2的节点以及连边，以此类推，直至网络中的每一个节点都被划分到某一个k-shell当中。用k-shell指标来衡量网络中节点对传播的影响力程度，是目前为止被广泛认可的一种度量方法[18]，认为k值越大的节点越处于网络中的核心位置，其影响力就越大。

2 基于节点影响力的标签传播社区检测算法

2.1 种子节点的选取

在KLPA算法中，考虑到网络中节点影响力的差异性，有效地选取网络中部分影响力大的节点组成种子节点集，在标签初始化时，只为种子节点集中节点分配不同的标签，不仅能减少初始标签的数目，而且可以使标签影响的范围更广。

定义1 给定网络G=(V,E)，其中V表示节点集，E表示边集。定义种子节点集M。

M={i|ki>K}

(1)

其中节点i∈V，ki,(i=1…n)表示节点i的k-shell值，K表示节点k-shell值的平均值。

2.2 节点标签更新策略

在LPA算法中，各节点标签将更新为邻接节点中频数最多的标签，标签更新公式如下：

其中：li表示待更新节点i的标签；N(i)表示节点i邻接节点的集合；lj表示节点i邻接节点j的标签；δ(lj,l)为克罗内克函数。当邻接节点中频数最多的标签不止一个时，节点i会随机选择一个标签更新，这种随机性在很大程度上影响了算法的稳定性。本文提出进一步考虑频数最多的标签影响力，将节点i更新为最具影响力的标签，标签影响力由该标签所对应的节点k-shell值决定。

定义2 给定网络G=(V,E)，标签更新的新公式如下：

其中，p(i)表示节点i的邻接节点j中标签频数最多的节点集合。节点i将更新为频数最多的标签中影响力最大的标签，这样做能降低标签选择的随机性，提高算法的稳定性。

2.3 KLPA算法实现

在分析初始标签分配和标签更新策略基础上，提出基于节点影响力的标签传播算法KLPA，算法如下：

输入：网络G(V,E)。

输出：社区划分结果。

1) 计算种子节点集M，并给M集中的节点分配唯一的标签，其标签表示节点所属社区；

2) 置迭代次数t=1；

3) 随机排列网络中的节点形成序列V；

4) 对网络中每个节点i，i∈V，标签更新规则如下：

5) 如果节点i的邻接节点中频数最多的标签有多个，根据式(3)计算频数相同的标签影响力，选择影响力更大的标签更新该节点。若标签的影响力相同，则随机选择一个标签更新。

6) 如果每个节点的标签不再变化，则停止算法，具有相同标签的节点归为同一个社区。否则，置t=t+1，且返回步骤(3)。

2.4 KLPA算法复杂度分析

假设网络中有n个节点，m条边，则KLPA算法时间复杂度分析如下：

1) 计算网络中节点的k-shell值，时间复杂度为O(n)；

2) 种子节点集的标签初始化，时间复杂度为O(n)；

3) 网络中每个节点i，更新节点标签的时间复杂度为O(di)，因此迭代一次所需的时间复杂度为O(ndi)。

由上述分析可得，KLPA算法的时间复杂度为O(n+n+ndi)，与网络规模成线性关系。

3 实验

为了测试本文改进算法的有效性，本节将KLPA算法与LPA算法、LPA-E算法进行比较，并且选取3个真实数据集进行实验，数据详细信息如表1所示。

表1 社会网络的基本数据信息

3.1 实验评价方法

1) 模块度[2]。Newman等提出的模块度是一个可以衡量网络社区划分质量优劣的指标，其表达式如下：

2) 准确率。对于已知社区结构的网络，准确率可以衡量社区划分结果中正确的节点占所有节点的比率。

3.2 实验结果与分析

3.2.1 实验1

本实验在Karate、Dolphins网络中运行KLPA算法、LPA算法、LPA-E算法各100次，计算社区划分结果的准确率、模块度以及模块度方差值。模块度可以客观地评价网络社区划分的质量，模块度方差值的大小可以说明社区划分结构的波动大小。因此采用模块度方差值估计社区结构的波动大小，波动越小则说明算法稳定性越好。实验结果如表2、表3所示。在这两个网络中运行KLPA算法，根据公式(1)计算得Karate、Dolphins网络的种子节点集分别为Karate(M)=22，Dolphins(M)=36，因此在标签初始化时，只给种子节点集M中的节点分配不同的标签。

表2 Karate、Dolphins网络实验结果准确率比较 %

表3 Karate、Dolphins网络实验结果模块度值比较

由表2中可以看出，在Karate、Dolphins网络上，通过与已知的社区划分结果相比，KLPA算法的准确率均高于LPA-E、LPA算法，这说明KLPA算法能以较高的准确率发现真实的社区结构，表明了KLPA算法能有效地检测网络中的社区结构。

由表3可以看出，在两个真实网络中KLPA算法的模块度平均值均高于LPA-E、LPA算法，表明KLPA算法检测的社区质量有所提高；同时KLPA算法模块度的方差值也较小，由此说明KLPA算法的划分结果相对稳定。

3.2.2 实验2

本实验在较大的数据集Cond-mat网络上运行KLPA算法、LPA算法、LPA-E算法各100次，验证KLPA算法是否可以有效的检测社区结构。实验结果如表4所示。在Cond-mat网络上运行KLPA算法，根据式(1)计算得该网络的种子节点集M=4 986。因此在标签初始化时，只给种子节点集M中的节点分配不同的标签。

表4 Cond-mat网络实验结果模块度值比较

由表4可以看出：相比LPA算法、LPA-E算法，KLPA算法所得的社区划分结果的模块度平均值略低于LPA-E算法，但模块度的方差值略高于LPA-E算法，由此说明KLPA算法能够在大型网络上检测到社区结构，且算法的稳定性好。

表5 Cond-mat网络实验结果迭代次数比较

表5记录了3种算法在Cond-mat网络中运行的迭代次数。比较结果可以看出，相比于LPA、LPA-E算法，KLPA算法的迭代次数大约减少了一半，由此说明KLPA算法的执行效率更高。这是由于本文通过标签初始化和标签更新策略两个方面改善了算法的随机性，从而减少了算法的迭代次数，使得算法的执行效率更高。

4 结束语

本文考虑了网络中节点影响力的差异性对标签传播的影响，提出基于节点影响力的标签传播社区检测算法KLPA。该算法借鉴k-shell分解方法衡量节点的影响力，通过计算节点k-shell的平均值K，选取节点k-shell值大于平均值K的节点作为种子节点集，标签初始化时只给种子节点分配不同的标签。在标签选择过程中，考虑节点的邻接节点中频数最多的标签影响力，将该节点更新为频数最多的标签中影响力最大的标签。通过实验证明了KLPA算法不仅具有线性时间复杂度，减少了随机性，提高了算法的稳定性，而且减少了算法的迭代次数，社区模块度的值也有所提高。

KLPA算法在选择种子节点时，以节点k-shell值的平均值作为阈值，没有考虑算法对该阈值参数的值是否敏感，下一步将分析不同的节点影响力度量方法对标签传播算法的影响。利用更加优良的节点影响力度量方法选取网络的种子节点，改进标签传播算法是未来研究的重点。