在现实世界中, 存在着各种各样的复杂网络, 如: 社交网络、万维网、神经网络等. 这些网络可以用图来表示, 对网络的研究可以转化为对图论问题的研究. 如图论中的聚类问题, 目的是挖掘复杂网络的社区结构, 使得类内节点联系紧密, 类间节点联系稀疏. 挖掘复杂网络的社区结构对于研究网络结构和应用具有非常重要的意义, 如识别社交网络中的顶级传播者^[1], 根据用户关系进行兴趣或好友推荐^{[2, 3]}和通信网络中的故障恢复^[4]等.

为了挖掘复杂网络的社区结构, 学者们提出了许多社区发现的算法. Girvan等人^[5]提出了GN算法, 该算法的主要思想是每次删除边介数最高的边, 直到网络中每个节点表示一个社区为止, GN算法的时间复杂度为O(m²n), 其中, m表示网络的边数, n表示网络的节点数. Newman等人^[6]提出了一种模块度最大化的贪婪算法FN, 该算法的时间复杂度为O((m+n)n). Pons等人^[7]基于随机游走提出的Walktrap算法, 其主要思想是采用随机游走算法计算节点的相似性矩阵, 根据相似性矩阵合并社区, 直到所有节点合并为一个社区为止. Raghavan等人^[8]提出了标签传播算法(Label Propagation Algorithm, LPA), 该算法的主要优点是时间复杂度低, 适用于在大型网络上的社区发现.

多数典型标签传播类算法在标签更新时, 没有考虑节点重要性和相似性对节点更新的综合影响, 可能导致影响力小的节点反过来影响具有较大影响力的节点, 造成结果准确性低. 本文基于节点重要性与相似性提出了一种改进的标签传播算法(Label Propagation Algorithm based on node Importance and Similarity, LPA_IS). LPA_IS算法根据节点重要性提出了种子节点集和算法更新序列的获取方法, 并为任意种子节点分配唯一的标签. 在标签更新过程中, 基于节点重要性与相似性提出了一种标签综合影响力的计算方法, 任意节点根据其邻居标签的综合影响力更新自身的标签, 提高算法的准确性和稳定性.

1 相关工作

LPA算法的主要思想是, 首先为图中每个节点分配唯一的标签, 标签代表节点所在的社区. 当节点标签更新时, 根据式(1)选择邻居标签中数量最多的作为节点的待更新标签, 当邻居中标签数量最多不止一个时, 则随机选择一个. 重复上述操作, 直到所有节点的标签趋于稳定或达到最大迭代次数时, 则停止更新.

${l_i} = \mathop {\arg \max }\limits_{l \in T(i)} \sum\limits_{j \in N(i)} {\delta (l,{l_j})} $

(1)

其中, T(i)表示节点i邻居中标签的集合, N(i)表示节点i的邻居节点集, l_j表示节点j的标签, δ(l, l_j)表示克罗内克函数^[9], 如果l=l_j时, 则δ(l, l_j)=1, 否则δ(l, l_j)=0.

在LPA算法中, 初始化序列和标签选择时具有随机性, 导致社区划分时存在准确性低和稳定性差的缺陷. 为了提高LPA算法的准确性和稳定性, 近年来, 许多学者对LPA算法进行改进, 大致分为以下3种. 基于带约束的目标函数优化方法: LPAm^[10]、LPAm+^[11]和LPAh^[9]. 利用目标函数的优化提高社区划分质量, 但没有解决LPA稳定性差的问题. 基于节点在网络中的重要性对LPA算法进行改进的方法: NIBLPA^[12]、IPLPA^[13]和S-LPA^[14]. 根据节点重要性计算标签的影响力, 进而改变算法的更新序列和标签更新方法. 然而, 这些算法没有考虑到网络中节点之间的相似性. 基于节点在网络中的相似性进行改进的方法: NILPA^[15]和HPI-LPA^[16]. 通过计算节点与邻居之间的相似性获取节点的更新标签, 提高算法的准确性.

2 LPA_IS算法 2.1 节点重要性

节点重要性能够衡量节点在网络中的影响程度. 主要的方法有: 度中心性、介数中心性、接近中心性、k-shell算法^[17]等.

k-shell算法能够反映出节点在网络中的全局影响力, 但不能反映出同一层节点之间的差异和节点在网络中的局部影响力, 以及节点间的联系程度. 本文基于文献[13]和集聚系数^[18]提出了一种综合衡量节点重要性的方法如式(2)所示.

$NI(i) = \sum\limits_{j \in i \cap N(i)} {({\alpha _1} \times NKsd(j) + {\alpha _2} \times {C_j})} $

(2)

其中, NKsd(j)表示Ksd(j)进行归一化后的值, C_j表示节点j的集聚系数, α₁和α₂的取值是0到1之间的常数, NI(i)表示节点i的重要性. Ksd与NKsd的计算公式如下所示:

$Ksd(i) = Ks(i) + t$

(3)

$NKsd(i) = \frac{{Ksd(i)}}{{\max \{ Ksd(j)|j \in V\} }}$

(4)

其中, Ks(i)表示节点i的ks值^[17], t表示删除节点i时的迭代次数, Ksd(i)表示融合节点i迭代次数的ks值. 集聚系数C_i的计算如式(5)所示.

${C_i} = \frac{{2 \times {e_i}}}{{{k_i} \times ({k_i} - 1)}}$

(5)

其中, e_i表示节点i与其任意两个邻居节点形成的三角形个数, k_i表示节点i的度数. C_i值越大说明邻居节点之间联系越紧密.

2.2 节点相似性

在标签选择时, 本文将节点相似性作为衡量标签综合影响力的标准之一. 根据网络的局部信息计算节点相似性的方法有以下两种: 基于共同邻居数的CN指标^[19], 基于共同邻居节点度数的指标具体有Jaccard指标^[19]、HPI指标^[20]、RA指标^[21]等.

本文选取RA指标作为计算节点相似性的方法. RA指标的计算如式(6)所示, s(i, j)表示节点i和j的相似性, s(i, j)值越大说明节点i和j的相似性程度越高, 则它们越有可能属于同一个社区.

$s(i,j) = \sum\limits_{c \in N(i) \cap N(j)} {\frac{1}{{{k_c}}}} $

(6)

2.3 种子节点集

本文基于节点重要性升序排列获取算法的更新序列, 并根据式(7)计算种子节点集, 其中, i∈V, V表示网络的节点集, S表示种子节点集. 在算法初始化时, 对选取的种子节点分配唯一的标签. 在标签更新过程中, 重要性值小的节点会受到邻居中种子节点的影响, 则这些节点的标签将更新为种子节点的标签, 这有利于提高种子节点在网络中的影响力和减少算法的迭代次数.

$S = \left\{ i|NI(i) > \frac{{\displaystyle\sum\nolimits_{j \in V} {NI(j)} }}{n}\right\} $

(7)

2.4 综合影响力

在标签更新过程中, 节点选择其邻居中综合影响力最大的标签, 作为节点的待更新标签. 本文基于节点重要性与相似性提出了一种计算标签综合影响力的方法. 标签综合影响力的计算如式(8)所示.

$CI(l) = \frac{{N{I_l}(i)}}{{\sqrt {\displaystyle\sum\nolimits_{j \in N(i)} {NI{{(j)}^2}} } }} + \frac{{s(i,{N_l}(i))}}{{\sqrt {\displaystyle\sum\nolimits_{j \in N(i)} {s{{(i,j)}^2}} } }}$

(8)

其中, NI_l(i)表示邻居中标签为l的节点重要性之和, N_l(i)表示邻居中标签为l的节点集, s(i, N_l(i))表示节点i与其邻居中标签为l的相似性之和, CI(l)表示邻居标签为l的综合影响力. 本文使用函数 $ u\left(x\right)=x/\sqrt{{x}^{2}} $ 对NI_l(i)和s(i, N_l(i))进行归一化处理, 使其能正确反映不同作用力的综合结果.

2.5 算法描述

本文提出的LPA_IS算法, 首先根据式(2)计算节点重要性, 并获取算法的更新序列. 然后, 基于节点重要性根据式(7)计算网络的种子节点集, 并为任意种子节点分配唯一的标签. 最后, 根据式(8)计算节点邻居中标签的综合影响力, 通过式(9)选择综合影响力最大的标签作为节点的待更新标签. 节点标签的更新公式如下所示.

${l_i} = \mathop {\arg \max }\limits_{l \in T(i)} CI(l)$

(9)

LPA_IS算法的具体描述如算法1所示.

算法1. LPA_IS

输入: 网络G=(V, E), V表示网络的节点集, E表示网络的边集, T表示最大迭代次数

输出: 社区划分结果

1. 通过式(2)计算节点重要性, 其中设置α₁为0.45, α₂为0.55

2. 按节点重要性升序作为算法的遍历序列V'

3. 根据式(7)计算网络的种子节点集, 并为任意种子节点分配唯一的标签

4. 设置迭代次数t=1

5. while t<T or can_stop(G) == True:

6. 　　for each i∈V' do:

7. 　　　　for j∈N(i) do:

8.　　　　　　若节点j的标签不存在, 则跳过下述操作

9. 　　　　　　计算邻居标签为l的节点重要性之和NI_l(j)

10. 　　　　　 计算节点i与邻居标签为l的相似性之和s(i, N_l(i))

11. 　　　end for

12. 　　　根据公式(8)计算邻居标签的综合影响力CI

13. 　　　根据公式(9)更新节点i的标签

14. 　end for

15. 　 t += 1

16. 如果任意节点标签趋于稳定或达到最大迭代次数, 则停止更新

17. end while

18. 对步骤5的结果进行划分, 输出社区划分结果

2.6 复杂度分析

设n为网络的节点数, m为网络的边数, k为网络的平均度数, S为网络的种子节点集. ① 计算节点重要性的复杂度为O(n), 获取种子节点集的复杂度为O(n), 对任意种子节点初始化标签的复杂度为O(|S|), S的大小远远小于n, 故可忽略不计, 利用桶排序对节点重要性升序排列的复杂度为O(n), 因此LPA_IS算法初始化的复杂度为O(3×n)=O(n); ② 计算节点与其邻居之间相似性的复杂度为O(k×k), 利用式(8)计算标签综合影响力的复杂度为O(k); ③ 每一次迭代, 节点进行标签更新的复杂度为O(n×(k×k+k))=O(n×k×k). 假设算法的迭代次数为T, 故LPA_IS算法的总时间复杂度为O(T×k×k×n+n).

3 实验结果与分析

实验所使用的对比算法包括LPA、LPAm、LPAh、HPI-LPA和S-LPA, 均用Python实现, 部分算法存在随机性, 实验结果取运行100次后的均值. 实验环境为Windows 10操作系统, 内存8.00 GB, 硬件配置Inter(R) Core(TM) i7-7770 CPU, 4.00 GB.

3.1 实验数据

实验选取9个真实网络数据集, 它们来自不同的真实应用场景^[9,14,22,23], 网络具体信息如表1所示.

本文采用由Lancichinetti等人^[24]提出的LFR基准程序人工合成2组网络, 具体参数设置如表2所示, 其中, N表示节点数, k表示平均度数, maxk表示最大度数, minc表示最小社区内的节点数, maxc表示最大社区内的节点数, mu表示社区的混合参数, mu值越大表示网络结构越模糊, 算法越难识别社区结构.

3.2 评价指标 3.2.1 标准化互信息

若已知网络的真实划分, 则使用标准化互信息(Normalized Mutual Information, NMI)^[25]作为评价指标. NMI的取值为[0, 1]. 若NMI值为1, 则说明算法划分后的社区与网络的真实划分相同. NMI的定义如式(10)所示, 其中, X表示网络的真实划分, Y表示算法得到的社区划分, H(X|Y)表示X在Y上的规范化条件熵.

$NMI(X|Y) = 1 - \frac{{H(X|Y) + H(Y|X)}}{2}$

(10)

3.2.2 平均模块度

当网络的真实社区划分未知时, 选取模块度Q^[26]作为实验的评价指标. 假设算法运行了t次, 每次得到的模块度值为Q₁, Q₂,···, Q_t, 采用Q_avg表示平均模块度, Q_avg的计算方式如式(11)所示.

${{Q_{\rm{avg}}}} = \frac{{\displaystyle\sum\nolimits_{i = 1}^t {{Q_i}} }}{t}$

(11)

3.2.3 模块度标准差

在平均模块度Q_avg的基础上, 本文还采用模块度标准差Q_std作为实验的评价指标. Q_std的计算方式如式(12)所示.

${{Q_{\rm{std}}}} = \sqrt {\frac{{{{\displaystyle\sum\nolimits_{i = 1}^t {({Q_i} - {{Q_{\rm{avg}}}})} }^2}}}{t}} $

(12)

3.3 实验过程和结果分析

(1) 真实网络上的实验

从表3中可以看出, 在平均模块度的对比上, LPA_IS算法在R1、R3和R4网络上的Q_avg值低于其它算法, 而在其它网络上的Q_avg值比其它5种算法好. 在模块度的标准差方面, LPA_IS算法的Q_std值都为0, 说明本文提出的LPA_IS算法具有较好的稳定性. 在真实网络数据集中, R1、R2、R3和R4网络存在真实的社区划分, 在不同算法上比较数据集的NMI值, 从表4中可以看出, LPA_IS算法在R3网络上的NMI值比其它5种算法好, 而在R1网络上的NMI值与S-LPA算法相同都为1, 说明在R1网络上的社区划分与真实网络划分一致.

在算法运行的平均迭代次数方面, 从图1中可以看出, 虽然LPA_IS算法在R2、R3和R5网络上的平均迭代次数多于其它算法, 但在其它网络上的平均迭代次数比其它5种算法少, 这是因为LPA_IS算法利用标签综合影响力更新节点标签, 避免了很多不必要的更新.

综上所述, 在真实网络数据集中, LPA_IS算法不仅能够提高算法的准确性和稳定性, 而且能够有效地减少算法的迭代次数.

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

从图2(a)可以看出, 当参数mu≤0.6时, 即社区结构比较明显时, 6种算法都能较好的发现社区结构, 因此NMI值都比较高. 当0.6<mu≤0.7时, 即社区结构变得越来越模糊时, LPA_IS算法的NMI值高于其它5种算法. 在图2(b)中, 当0.65<mu≤0.7时, 算法发现社区结构的难度增加, 但LPA_IS算法仍能较好地发现社区结构, 并且NMI值也都高于其它算法. 综上所述, LPA_IS算法相比于其它5种算法, 当社区结构变得越来越模糊时, LPA_IS算法仍能保持较高的准确性.

4 总结

针对LPA算法的缺点, 本文基于节点重要性与相似性提出了一种改进的标签传播算法(LPA_IS). 算法首先根据改进的k-shell分解算法和集聚系数计算节点重要性. 其次, 基于节点重要性提出了种子节点集和算法更新序列的获取方法, 并对任意种子节点分配唯一的标签. 最后, 根据节点重要性与相似性计算标签的综合影响力, 任意节点根据其邻居标签的综合影响力更新自身的标签. 在真实网络和人工合成网络上的实验结果表明, 本文提出的LPA_IS算法与其它5种典型标签传播类算法相比, 不仅提高了社区发现的准确性和稳定性, 而且减少了算法的迭代次数.