基于节点中心性和社区相似性的快速标签传播算法

0 引言

自然界与人类社会中的许多系统都可以用复杂网络模型表示，网络社区结构是复杂网络中最普遍和最重要的拓扑属性。社区发现算法可以通过分析网络中节点之间的关联性，挖掘复杂网络中的社区结构，从而揭示复杂网络中隐含的特性和功能，对于网络结构的理论研究和网络分析的实际应用有着重要的作用。

2007年 Raghavan等［1］首次将标签传播算法(Label Propagation Algorithm，LPA)应用于社区发现。与传统的社区发现方法(基于层次聚类的算法［2－3］、基于随机游走的算法［4］等)相比，LPA仅依赖于网络的传播特性，且具有线性的时间复杂度，适合用于对复杂网络进行社区发现和分析的优点。但是LPA也有一些缺点:1)节点更新顺序具有随机性，并且当邻接节点中出现次数最多的标签(最大值标签)有多个时，会随机选择一个标签;2)存在不必要的标签更新过程;3)更新标签时仅仅考虑邻接节点中标签出现的次数，忽略邻接节点的局部结构信息。这些缺点会导致算法延迟收敛，社区发现的结果准确率低且稳定性差的问题。针对以上问题，2014年，Xing等［5］提出了基于节点影响力的标签传播算法(Node Influence Based Label Propagation Algorithm for community detection in networks，NIBLPA)，该算法使用k-shell分解方法计算每一个节点的影响力值，依据影响力值从高到低的顺序更新标签和选取标签，提高了算法的稳定性和准确率，但是时间复杂度也有所提升。2015年，Sun等［6］提出了基于中心性的标签传播算法(Centrality-based Label Propagation algorithm for community detection in networks，Cen_LP)，该算法为每一个节点定义了节点中心值和节点偏向值，依据节点中心值从低到高的顺序更新标签并且利用节点偏向值选取标签，算法在不增加时间复杂度的情况下，提高了社区发现的准确率。2017年，Ma等［7］提出了基于节点重要性和随机游走的标签传播算法(An improved Label Propagation Algorithm based on Node Importance and random walk for community detection，NILPA)，该算法依据节点的度数计算节点重要性，并且依据随机游走理论形成节点相似度矩阵，在两者的基础上形成新的度量标准来衡量节点之间的紧密程度，依据该度量标准更新标签。算法提高了社区发现的准确率，但由于计算节点相似性依赖于矩阵相乘，在网络规模不断扩大时，会消耗越来越多计算资源，而且时间复杂度也较高。综上所述，尽管上述算法在准确率上有所提高，但是都提高了算法的时间复杂度，降低了算法的执行速度。

为了在加快算法的执行速度的基础上提高算法准确率和稳定性，本文提出了基于节点中心性和社区相似性的快速标签传播算法(Fast Label Propagation Algorithm based on the Node Centrality and Community Similarity，FNCS_LPA)。FNCS_LPA首先计算每一个节点的中心性度量值，按照中心性度量值从低到高的顺序排序并加入到节点信息列表中，用节点信息列表指导更新过程，通过记录节点信息列表中每一个节点的状态信息，判断当前节点是否需要更新，从而避免了不必要的更新，提高了运行速度。在更新过程中，FNCS_LPA利用基于社区相似性的更新规则，即不仅仅考虑邻接节点中标签出现的次数，还会评估每个邻接节点与待更新节点的相似性，社区相似性依赖于节点相似性求和，待更新节点会选择社区相似性最高的社区，从而提高算法的准确率。

1 基于节点中心性的快速标签传播算法

1．1 基于节点中心性的更新顺序

在LPA的每一次迭代过程中，节点的更新顺序是随机的，这等同于平等对待网络中的所有节点。事实上，网络中的每个节点的重要程度依赖于其在网络中的局部信息，并不是同等的，如果平等对待，按随机的顺序更新标签，可能会造成结果与实际不符，导致算法准确率低且稳定性差的问题。基于此，本文提出了基于节点中心性的更新顺序，其中，节点中心性依赖于节点的聚集系数(Clustering Coefficient)和节点密度。假设节点i和节点j是网络中的两个节点。

定义1 节点的聚集系数。节点i的聚集系数定义如下:

 

其中:Ni表示节点i的邻接节点集合，|Ni|表示节点i的邻接节点数，E(i)表示节点i的邻接点之间实际的连边数。节点的聚集系数可表示为当前节点的所有邻节点之间实际连边数与所有可能连边数的比值，由于节点的邻接点之间实际存在的边不会大于可能存在的最大值，因此节点的聚集系数的取值范围在0～1:当节点的度数为0或1时，或者当节点的邻接点之间相互独立时，该节点的聚集系数为0;当节点的聚集系数为1时，则表示该节点与其邻接点之间构成完全图。因此节点的聚集系数越高，说明节点具有越高的聚集度。

定义2 节点密度。节点i的密度定义如下:

 

定义3 节点中心性度量值。

 

节点中心性度量值表示为节点密度和节点聚集系数的乘积，δi的值越大，表明节点在网络中的重要程度越高。在实际生活中，重要程度高的节点为专家，而重要程度低的节点为普通求知者，普通求知者都是听取专家的知识，从而完成知识传播。同样，在标签传播过程中，标签就是知识，节点就是人，重要程度低的节点往往要先采纳周围重要程度高的节点的标签，从而完成标签传播。因此，节点δi的值越小，该节点就越先更新标签，这样得到的结果才会与实际相符，因此节点的更新顺序按照节点中心性度量值升序更新。

1．2 基于节点中心性的快速标签传播算法

LPA运行在线性时间内，具有执行速度快的优点。LPA在前几次迭代过程中节点改变标签的概率是非常高的，但是，在5次迭代以后，95%以上的节点都会被正确地划分(当前节点的标签已经变为邻接节点中最大值标签)。为了说明这一现象，本文将 LPA分别应用在 CA-Hepth、CA-GrQc、Email和PGP这4种常用的真实网络数据集上进行社区发现，本文实验将每一个真实网络都看作无向无权图，每一个图都没有自循环的边并且只取图的最大连通子图。本文所有的实验均使用Python语言实现，在 Window 7，AMD Core A8-4555 CPU 1．6 GHz，8 GB 内存环境下进行。

1．2．1 实验一:LPA的收敛性

例1～例5“非”修饰谓语，两部文献中“非”最多的就是此种用法，例6、例7“非”修饰数词，例8“非”也与“不”连用，构成双重否定，表肯定后更有强调意味，仅在《齐》中见2例。

数据集详细信息如表1所示，计算5次迭代以后已被正确划分的节点占总节点的百分比。每个网络重复100次实验，4种网络的收敛信息如表2所示。

 

表1 第一部分数据集介绍Tab．1 Introduction of the first part datasets

  

网络名称 节点数 边数 描述Email 1133 5451 Email社交网络［8］CA-GrQc 4158 13422 广义相对论研究网络［9］CA-Hepth 8638 24807 高能物理学研究网络［9］PGP 10680 24316 PGP算法的研究团体网［10］

 

表2 网络的收敛信息Tab．2 Convergence information of networks

  

网络名称 5次迭代后正确划分节点所占百分比/%算法收敛所需的迭代次数Email 96．64 17．89 CA-GrQc 99．37 15．70 CA-Hepth 98．97 59．75 PGP 99．37 21．90

从表2可以看出，在5次迭代以后，Email网络有96．64%的节点被正确划分，CA-Hepth网络有98．97%的节点被正确划分，Email和PGP网络有99%以上的节点都已被正确划分。这说明无论总的迭代次数是多少，LPA在5次迭代以后，95%以上的节点都已经得到了正确的划分，而5次迭代后的每一次迭代，仅仅较少的节点标签会发生改变，而对于大部分的节点来说，即使更新标签，也不会改变标签，这些不必要的更新拖慢了算法的收敛速度。针对这一问题，本节提出基于节点中心性的快速标签传播算法。

1．2．2 实验二:LPA与FNC_LPA的对比

12) maxS ← S(i，l);

基于节点中心性的快速标签传播算法(Fast Label Propagation Algorithm based on Node Centrality，FNC_LPA)的具体流程如下:

第一步 按照式(1)、式(2)和式(3)计算节点的中心性度量值，将所有的节点按照节点中心性度量值降序排序并加入节点信息列表当中。每一个节点都被初始化为一个独一无二的标签，都被设置为主动节点。

第二步 从节点信息列表中随机选择一个主动节点或干扰节点，按照节点标签更新规则，对当前节点的标签进行更新。标签更新完成后对该节点及其邻接节点进行状态更新，节点在更新状态时，可能会更新为被动节点、主动节点和干扰节点。

基于双因素理论的公共部门劳务派遣人员激励研究 ………………………………………………………………… 陈龙英（3/49）

第三步 根据节点状态判断节点信息列表中是否还有主动节点:若有，继续执行第二步;否则，算法结束。

为了评估FNC_LPA的有效性，本次实验包括表1和表3中的8个真实网络数据集。对8种数据集分别使用FNC_LPA和LPA进行社区发现，对比算法收敛时所需的迭代次数和模块度［11］。模块度是一种比较重要的衡量网络社区结构强度的方法，计算公式如下:

 

/* 更新当前节点i和i的邻接节点的状态*/

 

表3 第二部分数据集介绍Tab．3 Introduction of the second part datasets

  

网络名称 节点数 边数 描述karate 34 78 空手道俱乐部网络［12］dolphins 62 159 海豚数据网络［13］polbooks 105 441 亚马逊政治书销售网络［14］netscience 379 914 网络科学论文合著网络［15］

 

表4 LPA和FNC_LPA平均模块度对比Tab．4 Comparison of average modularity between LPA and FNC_LPA

  

网络名称 LPA FNC_LPA 网络名称LPA FNC_LPA karate 0．345 0．332 Email 0．234 0．301 dolphins 0．483 0．478 CA-GrQc 0．775 0．774 polbooks 0．493 0．499 CA-Hepth 0．628 0．640 netscience 0．794 0．801 PGP 0．802 0．804

为了使算法具有可比性，FNC_LPA与LPA使用相同的更新规则(当前节点的标签选取邻接节点中的最大值标签)。FNC_LPA的迭代次数记为算法总更新次数和节点总个数的比值。模块度和迭代次数为对每一个网络重复100次实验后所求得的平均值，迭代次数对比如图1所示，可以看出，因为FNC_LPA避免了很多不必要的更新，所以迭代次数明显少于LPA。在 karate、dolphins、polbooks和 netscience 网络上，FNC_LPA的迭代次数是LPA的1/5至1/2左右，在Email和CAGrQc网络上，FNC_LPA是LPA的1/6左右，在CA-Hepth和PGP网络上，FNC_LPA是LPA的1/10左右。平均模块度对比如表4所示，可以看出，与 LPA相比，FNC_LPA除了在Email和CA-Hepth网络上模块度有小幅提升以外，在其余网络上模块度几乎没有发生变化。因此，实验结果证明FNC_LPA在没有改变社区发现效果的基础上，能够大幅度降低迭代次数。

  

图1 FNC_LPA和LPA的迭代次数对比Fig．1 Comparison of iterations between FNC_LPA and LPA

2 基于社区相似性的更新规则

LPA的更新规则仅仅考虑邻接节点的标签出现次数，并且当前节点的标签更新为邻接节点中最大值标签，具有相同标签的节点看作一个社区，这种更新规则默认是将每一个邻接节点与当前节点的相似性(社区相似性依赖于节点相似性求和)看作是相同的，LPA最终是将最大值标签所代表的社区作为与当前节点相似性最高的社区。实际上，每一个邻接节点与当前节点的相似性并不是同等的，如果同等对待，会导致算法准确率低且稳定性差的问题。本章提出基于社区相似性的更新规则，社区相似性是由节点相似性求和得到，其中节点相似性依赖于节点之间的公共节点个数和节点的度数，基于社区相似性的更新规则会使待更新节点选择邻接节点的社区中相似性最高的社区。

本章对算法中使用的主要概念进行形式化定义，如下所示:

定义4 边缘度数比。假设节点i和节点j是图中的两个节点，i与j的边缘度数比定义如下:

面对数量庞大的2型糖尿病患者和沉重的经济负担,作为无法治愈的慢性疾病,治疗目的在于实现对血糖有效控制,同时防止并发症出现;患者自我管理是2型糖尿病患者治疗的核心所在,这是需要紧随病情所采取的方式[1-2]。因此不管是在血糖控制上,还是自我管理上,均需要重视关键因素。目前全球调查结果显示,在自我管理水平方面2型糖尿病患者整体偏低。他们在管理能力上表现不强,血糖控制不稳定,可引起急慢性并发症,同时使患者产生焦虑和抑郁情绪M。因此如何提高2型糖尿病患者自我管理状况已成为迫切需要解决的问题[3-4]。

 

其中:sim(i，j)表示节点i和节点j的公共节点的个数，di表示节点i的度。

定义5 节点相似性。节点j对节点i的重要程度定义如下:

 

其中:c1和c2是取值在0～1的两个常数，ρij是节点i和节点j的边缘度数比。

定义6 社区相似性。节点i与社区l的相似性定义如下:

 

定义7 近似最大值标签。在LPA中，当前更新的节点的标签选取邻接节点中的最大值标签，将这个标签的出现次数记为max;然而，如果邻接节点某类标签的出现次数(计为n)和max的值相差不大时，这类标签称为近似最大值标签。算法引入一个取值在0～1的常量Radio来衡量近似程度。

 

若邻接节点中标签出现次数n满足式(8)，都称之为近似最大值标签。正在更新的当前节点也可能选择近似最大值标签，其中，在更新过程中为了不考虑节点数量较少的标签，Radio的值不宜设置过大，应在0～0．5。近似最大值标签的引入，避免了对每一个社区进行相似性计算，提高了算法效率。

定义8 基于社区相似性的更新规则。假设集合T中保存了节点i的邻接节点中的最大值标签(社区)和近似最大值标签，L(i)表示节点i的标签，基于社区相似性的更新规则如式(9)所示:

 

式(9)是在集合T中，让节点i选择使得S(i，l)最大的一类标签，如果有多类标签使得S(i，l)最大，就从中随机选取。

为了验证该更新规则的有效性，本次实验在LPA中使用基于社区相似性的更新规则形成基于社区相似性的标签传播算法(LabelPropagationAlgorithmbasedonCommunity Similarity，CS_LPA)，CS_LPA的节点更新的顺序是随机的。其中式(6) 中的c1取值1，c2取值0．2，式(8) 中的Radio值取0．4。本次实验除了使用表1和表3中的8种真实网络数据集，还应用了LFR(Lancichinetti Fortunato Radicchi)基准网络。LFR基准程序是由Lancichinetti等［16］提出的专门用于生成模拟网络的算法，该算法主要根据输入的参数，尽可能地生成符合真实网络特征的人工合成网络，因此具有较高的实验价值，是当前社区发现研究中最为常用的模拟数据集。在生成LFR基准网络时常用的参数如表5所示，其中mu表示节点与社区外部连接的概率，其值在0～1，mu值越大，表明社区的结构越不明显，社区发现的难度也越大。本次实验使用的LFR基准网络数据集如表6所示，其中包含4组LFR基准网络，每组包含15个不同 mu值的网络，mu的取值在0．1 ～0．8，间隔为0．05。相比2000S(5000S)网络，2000B(5000B)网络中每一社区内的节点个数较多。

 

表5 LFR基准网络的主要参数Tab．5 Parameters of LFR benchmark network

  

参数 含义 参数 含义N 网络中的节点个数 cmin 社区内的最少节点个数k 网络的平均度数 cmax 社区内的最多节点个数kmax 网络的最大度数 mu 节点与社区外部连接的概率

 

表6 LFR基准网络数据集描述Tab．6 Description of LFR benchmark network datasets

  

网络 N k kmax cmin cmax mu 2000S 2000 10 50 10 50 0．1 ～0．8 2000B 2000 10 50 20 100 0．1 ～0．8 5000S 5000 10 50 10 50 0．1 ～0．8 5000B 5000 10 50 20 100 0．1 ～0．8

归一化互信息(Normal Mutual Information，NMI)［17］能够量化算法对网络进行的划分和网络的真实划分之间的关系，是一种在社区发现领域常用的度量标准。NMI的取值在0～1，其计算式(10)所示:

 

其中:A是网络的真实划分，B是算法对网络所进行的划分，CA表示A种划分的社区个数，CB表示B种划分的社区个数，N表示一个矩阵，Nij表示A种划分第i个社区中的节点出现在B种划分第j个社区中的节点个数，Ni·表示矩阵N第i行的求和，N·j表示矩阵N第j列的求和。n表示整个网络节点的个数。如果A种划分和B种划分是相同的，则NMI(A，B)的值为1。NMI的值越高，表示算法社区发现的准确率越高。

将CS_LPA和LPA分别用在表1和表3的8种真实网络数据集和4种LFR基准网络数据集上进行社区发现，对每一个网络重复100次实验。在8种真实网络数据集上与LPA对比平均模块度，对比如表7所示:在所用的数据集上，CS_LPA的模块度都比 LPA要高;其中，在 Email、CA-Hepth、dolphins和netscience网络上，CS_LPA模块度有明显的提高。由于LFR基准网络已知真实的划分结果，因此在LFR基准网络数据集上与LPA对比平均NMI值。NMI的对比如图2所示。

  

图2 LFR基准网络上CS_LPA和LPA的NMI对比Fig．2 NMI comparison of CS_LPA and LPA on LFR benchmark network

从图2(a)可以看出，mu的值在0．1～0．45时，两种算法都能较好地发现社区结构;mu的值在0．45～0．6时，LPA的NMI值迅速下降，表明社区发现的准确率在下降，而CS_LPA的NMI的值远高于LPA;mu的值在0．65～0．8，LPA已无法进行社区发现，而CS_LPA仍可进行。图2(b)产生了类似于图2(a)的效果，mu的值在0．1～0．4时，两种算法都能较好地发现社区结构，而 mu的值在0．45～0．8时，CS_LPA的NMI值高于LPA。在图2(c)和图2(d)中，当 mu大于0．6时，CS_LPA的NMI明显高于LPA。

综上所述，相比LPA，CS_LPA提高了社区发现的准确率，尤其对于社区结构不清晰的网络，算法的优势更加明显。

 

表7 LPA与CS_LPA平均模块度对比Tab．7 Comparison of average modularity between LPA and CS_LPA

  

网络名称 LPA CS_LPA 网络名称LPA CS_LPA karate 0．345 0．369 Email 0．234 0．465 dolphins 0．483 0．519 CA-GrQc 0．775 0．788 polbooks 0．493 0．518 CA-Hepth 0．628 0．675 netscience 0．794 0．818 PGP 0．802 0．815

3 FNCS_LPA算法

3．1 算法流程

在第1章和第2章中，本文分别引入了基于节点中心性的快速更新过程和基于社区相似性的更新规则，在基于节点中心性的快速更新过程中引入基于社区相似性的更新规则，形成基于节点中心性和社区相似性的快速标签传播算法(FNCS_LPA)。算法的伪代码如下:

非金属夹杂物级别虽然不高，但在样品中心V形裂纹附近出现了硫化物类夹杂物（1级），非金属夹杂物的存在破坏了钢基体的连续性，严重影响钢的力学性能，产生应力集中，拉拔时不能与基体同步变形，在非金属夹杂物与基体结合部位引起应力集中，导致裂纹在此处萌生及扩展，最终导致盘条拉拔断裂。

FNCS_LPA:

3) 从节点信息列表中随机选取一个主动节点或干扰节点，记为i;

在中国古代两件事最为重要，一是祭祀，一是战争。祭祀排在战争的前面，因为只有祭祀才能获得神灵的佑助，而能不能获得神灵的佑助是部落能不能得到发达的根本。从文献资料，中国远在尧舜禹三帝之时，就已经有以乐舞祭神的形式了。而实物的佐证就是良渚出土了玉钺。良渚时代当是大早于禹的尧舜时代，有学者甚至认为，良渚部落就是大舜的部落。从良渚反山发掘的十几座古墓来看，每墓出土玉钺只有一件，可见它极为珍贵。

/*输入图的邻接矩阵和式(6)，式(8)的参数*/

输出 社区划分结果。

1) 为每个节点分配一个独一无二的标签;

斯各格兰德超现实主义摄影创作有如下步骤：首先，搭建精致的装置或舞台；随后，在其中摆放精心挑选的彩色家具等物品，完成这两步通常需要花上她几个月的时间。最后，在场景中加入模特，进行对装置成品的拍摄。她的作品特征鲜明：通常有同一物品的大量重复出现，使用明快色彩形成强烈对比，或是仅应用单个主题色。

2) 按式(1)～(3)计算所有节点的中心性度量值，按照升序的顺序添加到节点信息列表当中，将所有的节点标记为主动节点;

输入 G(V，E)、c1、c2、Radio;

4) 将当前节点i的邻接节点中出现次数最多的标签和近似最大值标签加入集合T当中;

微课平台的开发可与虚拟现实技术相结合，以增强学习者对学习环境的体验性和对知识的感知认知。虚拟现实技术提供的沉浸式场景可以模仿真实复杂场景，使学习者跨越时空限制获得同样的学习体验。

5) 初始化maxLabel集合为空;maxLabel记录与当前节点i相似性最高的一个或多个标签。

6) for each l∈T do

7) maxS←0;

8) 依据式(6)计算S(i，l);

在图2所示的软件接收机中，考虑FPGA的存储资源限制，选取载波测量的FFT长度为32 768，因此，接收机的闭环跟踪精度分为305 Hz，跟踪步长为3.276 8 ms，可跟踪的最大多普勒频率变化率为93 kHz/s。

9) if S(i，l)==maxS then

10) 将l标签添加到maxLabel中;

11) else if S(i，l) ＞ maxS then

LPA在每次迭代过程中，对节点标签的更新有两种情况:一种是邻接节点中的最大值的标签只有一个，另一种是邻接节点中的最大值标签有多个。如果当前节点的标签已经是邻接节点中的唯一最大值标签，这样的节点称为被动节点，被动节点在本次更新中不会再改变标签;如果邻接节点中的最大值标签有多个，当前节点的标签是其中之一，这样的节点称为干扰节点，根据LPA的更新规则，干扰节点会随机选择其中一个标签，干扰节点在本次更新中可能会改变标签。被动节点和干扰节点以外的其他节点是主动节点，主动节点在本次更新中一定会改变标签。如果能避免对被动节点的标签更新，算法会以更快的速度收敛，因此，本文构建一个节点信息列表，其中包含所有的节点和每个节点的状态信息(被动、干扰和主动)。每次只选择信息列表中的干扰和主动节点进行标签更新，标签更新完成后再进行状态更新。

本文算例采用的是风-光-储微电网结构,由光伏列阵、风力发电机、储能系统(蓄电池)以及用户负荷组成。该微电网为并网型微电网,与外网交互时,优先利用微源满足微电网内负荷需求。若发生功率缺额,且自身无法靠蓄电池补给,则可以从外网吸收功率。微电网每小时调度一次,峰平谷分时电价如表1所示。

13) 从maxLabel中移除所有元素;

14) 将l标签添加到maxLabel中;

15) end if

28)将具有相同标签的节点划分到一个社区当中，算法结束

沥青混合料宜采用自卸汽车运输。为防止粘料，装料前应在汽车翻斗内抹1层柴油与水的混合物。装料过程中应前后移动，均衡装料，避免混合料离析。装料后用保温布覆盖，以起到保温和防止污染的作用。

16)end for

17)当前节点i从maxLabel集合中随机选取标签;

18)for each j∈N(i)∩ i do

其中:Lc表示社区c内部的链接数，m表示整个网络边的总个数，Dc表示社区c内部节点的度数总和，L表示整个网络的全部社区。

19) if node j is interference node then

20) 标记j为干扰节点;

21) else if node j is passive node then

癞阿小推的还真是地方，就推在柳红的胸脯上，而且还用了蛮力。胸脯本是女人最柔弱的部位，哪里经得起男人用力推搡，柳红只感到一阵钻心的巨痛，眼泪顿时夺眶而出，整个人像被碾碎了一般，散作无数块痛的碎片；但在每块碎片的疼痛背后，随之而来的却是勾人魂魄的麻酥，柳红嘴里忍不住嘣出急促的呻吟声。

23) else

22) 标记j为被动节点;

24) 标记j为主动节点;

25) end if

26)end for

27)如果节点信息列表仍含有主动节点，跳到第3)步;

公正地讲，“官渡之战”参战双方袁绍与曹操，在军事实力与政治实力上，袁绍都占绝对优势。曹操唯一能跟袁绍比的，是能为“选择”自己的合作者搭建事业平台。战前，袁绍谋士田丰、沮授从战略角度，提出“不宜开战”的理由与若打就打“持久战”的建议。袁绍却以动摇军心为由，囚禁了二人。战中，谋士许攸依据战局，提出乘曹操后方空虚，分兵袭击许都的建议。

3．2 时间复杂度

与LPA相比，FNCS_LPA的总体时间复杂度没有改变。首先按照节点中心性度量值对网络节点进行排序，排序算法选择较快的桶排序，其时间复杂度接近于O(n)，n表示网络中的节点个数。初始化节点信息列表的时间复杂度是O(n);从节点信息列表中随机选择一个节点时间复杂度为O(1);更新当前节点的标签的时间复杂度是O(di)，di是节点i的度数，因此在整个更新过程中，时间复杂度是O(m)，m是边的个数。通过使用节点信息列表，算法的收敛比较简单，仅仅判断节点的状态标记即可，最差的情况是 O(n)。因此FNCS_LPA算法的总体时间复杂度是O(m)。

4 实验结果与分析

为了验证FNCS_LPA的有效性，本次实验选取了第1章提到的 NIBLPA［5］、Cen_LP［6］和 NILPA［7］三种较好的改进LPA，数据集选取了表1和表3中的8种真实网络数据集和表6中的4种LFR基准网络数据集。其中式(6)的c1的值为1，c2的值为0．2，式(8) 的 Radio值为0．4。

4．1 执行速度对比

将FNCS_LPA、Cen_LP、NIBLPA和NILPA分别应用到真实网络数据集中进行社区发现。为了具有可比性，每一个算法的终止条件都是节点标签成为邻接节点中的最大值标签，对每一个网络重复100次实验求平均的迭代次数，得到的结果如图3所示。

(4)C真空泵入口阀门内漏：在该泵备用时，空气从真空泵出口处被倒吸入运行真空泵入口，漏点性质为大漏点，泄漏原因为阀门的密封面损坏，需进行研磨处理。在2018年的C级检修中，对此阀门进行了处理，处理后漏点消失。由于此类型漏点比较隐蔽，查找时不易被发现，需重点关注。

  

图3 FNCS_LPA与三种改进LPA的迭代次数对比Fig．3 Comparison of iterations between FNCS_LPA and other three improved LPA algorithms

从图3可以看出，与Cen_LP相比，FNCS_LPA在所有的数据集上的迭代次数明显要比Cen_LP少很多，这是因为FNCS_LPA避免了很多不必要的更新。在 karate、dolphins、polbooks和netscience网络上，FNCS_LPA的迭代次数是Cen_LP的1/4至1/2左右;在Email、CA-GrQc和PGP网络中，算法的迭代次数是Cen_LP的1/10左右;而在CA-Hepth数据集上，算法的迭代次数是Cen_LP的1/30左右。与NIBLPA相比，FNCS_LPA在各个数据集上的迭代次数为NIBLPA的1/16到1/3左右。与NILPA相比，FNCS_LPA在各个数据集上的迭代次数为NIBLPA的1/14到1/2左右。综上所述，与其他三种算法相比，FNCS_LPA明显提高了算法的执行速度。

4．2 模块度对比

将4种算法应用在8种真实网络数据集上进行社区发现，并在最低模块度、平均模块度和最高模块度方面进行对比，模块度的计算公式如式(1)所示。平均模块度(average)是对每一个真实网络作100次实验求取的平均值，最低模块度(min)和最高模块度(max)分别是对每一个真实网络作100次实验后求取的最差结果和最优结果。模块度的对比如表8所示，其中加粗的数据表明4种算法中对应每一个网络的最好结果。

 

表8 FNCS_LPA与三种改进LPA算法模块度对比Tab．8 Comparison of modularity between FNCS_LPA and other three improved LPA algorithms

  

网络名称 范围FNCS_LPA Cen_LP NIBLPA NILPA karate min 0．371 0．416 0．423 0．371 average 0．371 0．416 0．423 0．371 max 0．371 0．416 0．423 0．371 dolphins min 0．514 0．512 0．521 0．526 average 0．514 0．519 0．521 0．526 max 0．514 0．526 0．521 0．526 polbooks min 0．518 0．511 0．497 0．520 average 0．518 0．518 0．497 0．520 max 0．518 0．523 0．497 0．520 netscience min 0．831 0．772 0．747 0．807 average 0．831 0．773 0．747 0．807 max 0．831 0．774 0．747 0．807 Email min 0．517 0．003 0．427 0．155 average 0．517 0．427 0．427 0．155 max 0．517 0．532 0．427 0．155 CA-GrQc min 0．786 0．737 0．707 0．764 average 0．786 0．740 0．707 0．764 max 0．786 0．744 0．707 0．764 CA-Hepth min 0．672 0．611 0．612 0．627 average 0．672 0．622 0．612 0．627 max 0．673 0．632 0．612 0．627 PGP min 0．814 0．741 0．783 0．788 average 0．814 0．750 0．783 0．788 max 0．814 0．764 0．783 0．788

从表8中可以看出，FNCS_LPA在所有的数据集上的最低模块度、平均模块度和最高模块度均完全一致。在karate网络上，FNCS_LPA和NILPA都将网络划分为两个社区，求得的结果与真实划分完全相同;在dolphins和polbooks网络上，FNCS_LPA在最低模块度、平均模块度和最高模块度上，均接近于最优解;尽管Email网络没有在最高模块度方面取得最好的结果，但是从平均模块度和最低模块度方面，FNCS_LPA仍是最有优势的;而在netscience、CA-GrQc、CA-Hepth和PGP等网络上，FNCS_LPA的模块度明显高于其他几种算法。综上所述，FNCS_LPA相比其他3种算法提高了社区发现的准确率和稳定性;尤其在较大规模的网络算法，算法的优势更加明显。

4．3 归一化互信息对比

本次实验将4种算法应用在表6中的LFR基准网络数据集上进行社区发现，并在归一化互信息度量(NMI)方面进行对比，NMI的计算公式如式(7)所示。对每一个网络重复100次实验求取平均NMI值。实验结果如图4所示。

  

图4 LFR基准网络上FNCS_LPA与三种改进LPA算法的NMI对比Fig．4 NMI comparison of FNCS_LPA and other three improved LPA algorithms on LFR benchmark network

从图4可以直观地看出，随着mu的值不断增大，社区结构越来越不清晰，4种算法的社区发现准确率都在下降。从图4(a)可以看出:当mu的值在0．1～0．4时，4种算法都能较好地发现社区结构;mu的值在0．4～0．8时，FNCS_LPA的NMI的值高于其他3种算法。在图4(b)中，mu的值在0．35～0．45时，FNCS_LPA 略低于 NILPA;但 mu 的值在 0．6～0．8时，FNCS_LPA的 NMI值都是4种算法中最高的。图4(c)和图4(d)产生了类似的效果，当mu的值大于0．5时，FNCS_LPA社区发现的准确率明显高于其他3种算法。综上所述，FNCS_LPA相比其他3种算法提高了社区发现的准确率;尤其对于社区结构不清晰的网络，FNCS_LPA的效果更好，准确率更高。

5 结语

本文提出了基于节点中心性和社区相似性的快速标签传播算法。首先，该算法计算每一个节点的中心度量值，依据节点中心性度量值升序将节点加入节点信息列表，利用节点信息列表指导更新过程，通过记录每一个节点的更新状态，避免了许多不必要的更新，减少了迭代次数，从而提高了社区发现的稳定性和执行速度。为了验证基于节点中心性的快速更新过程的有效性，实验使用了8种真实网络在迭代次数和平均模块度方面与LPA进行了对比。其次，算法引入社区相似性的更新规则，即当前节点会加入与当前节点社区相似性最高的社区，提高了社区发现的准确率，为了验证基于社区相似性的更新规则的有效性，算法在平均模块度、NMI方面与LPA进行了对比。最后，将基于节点中心性的快速更新过程和基于社区相似性的更新规则结合形成本文提出的基于节点中心性和社区相似性的快速标签传播算法，与目前3种改进的LPA在迭代次数、模块度和NMI三个方面进行了对比，实验结果表明FNCS_LPA在提升算法执行速度的基础上，提高了算法的稳定性和准确率。

参考文献(References)

［1］ RAGHAVAN U N，ALBERT R，KUMARA S．Near linear time algorithm to detect community structures in large-scale networks［J］．Physical Review E，2007，76(3):96－106．

［2］ GIRVAN M，NEWMAN M E J．Community structure in social and biological networks［J］．Proceedings of the National Academy of Sciences，2002，99(12):7821－7826．

［3］ NEWMAN M E J．Fast algorithm for detecting community structure in networks［J］．Physical Review E， 2004， 69(6):66 －73．

［4］ PONS P， LATAPY M．Computing communities in large networks using random walks［J］．Journal of Graph Algorithms and Applications， 2006， 10(2):191 －218．

［5］ XING Y，MENG F，ZHOU Y，et al．A node influence based label propagation algorithm for community detection in networks［J］．The Scientific World Journal， 2014， 2014(5):210 －223．

［6］ SUN H， LIU J， HUANG J， et al．CenLP:a centrality-based label propagation algorithm for community detection in networks［J］．Physica A:Statistical Mechanics and its Applications， 2015， 436(15):767－780．

［7］ MA T， XIA Z．An improved label propagation algorithm based on node importance and random walk for community detection［J］．Modern Physics Letters B，2017，31(14):98－116．

［8］ ZHANG X， CHEN S， JIA J， et al．An improved label propagation algorithm based on the similarity matrix using random walk［J］．International Journal of Modern Physics B，2016，30(16):93－108．

［9］ LESKOVEC J， KLEINBERG J， FALOUTSOS C．Graph evolution:densification and shrinking diameters［J］．ACM Transactions on Knowledge Discovery from Data，2007，1(1):2－9．

［10］ ZHANG X， FEI S， SONG C， et al．Label propagation algorithm based on local cycles for community detection［J］．International Journal of Modern Physics B，2015，29(5):15－28．

［11］ NEWMAN M E J．Fast algorithm for detecting community structure in networks［J］．Physical Review E， 2004， 69(6):66 －78．

［12］ ZHOU K，MARTIN A，PAN Q，et al．Evidential label propagation algorithm for graphs［C］//Proceedings of the 2016 19th International Conference on Information Fusion．Piscataway， NJ:IEEE，2016:1316－1323．

［13］ LIU S，ZHU F，LIU H，et al．A core leader based label propagation algorithm for community detection［J］．China Communications，2016，13(12):97－106．

［14］ LI W，HUANG C，WANG M，et al．Stepping community detection algorithm based on label propagation and similarity［J］．Physica A:Statistical Mechanics and its Applications， 2017，472:145 －155．

［15］ SHANG R，ZHANG W，JIAO L，et al．Circularly searching core nodes based label propagation algorithm for community detection［J］．International Journal of Pattern Recognition and Artificial Intelligence，2016，30(8):24－46．

［16］ LANCICHINETTI A， FORTUNATO S，RADICCHI F．Benchmark graphs for testing community detection algorithms［J］．Physical Review E，2008，78(4):46－61．

［17］ NEWMAN M E J．Fast algorithm for detecting community structure in networks［J］．Physical Review E， 2004， 69(6):66 －78．