翟镇新 於跃成 谷 雨 景道月
（江苏科技大学计算机学院 镇江 212003）
随着互联网技术的发展和社会网络规模的不断扩大，人与人之间的交流形式发生了巨大变化，人们获取的信息量也呈爆炸式增长。社会网络具有信息大、无标识、社区结构等特性，其中社区结构是社会网络的基本性质。所谓社区结构是指一个网络可以分为若干个社区，社区内节点相似度较高且连接相对紧密，社区间节点相似度较低且相对稀疏。社区发现可用于社交平台用户群组的发现，以实现相关商业广告的投放；
通过社区发现并挖掘群组的最新讨论话题，可以向用户更好地推荐感兴趣的话题。
为了能够实现社区的有效划分，基于随机游走的方法［1］、基于模块度优化的方法［2～3］以及基于图分割的方法［4～5］被相继提出。这些方法主要依据网络结构进行划分，当应用于数据规模较大的社会网络时，便会面临迭代周期较长，算法复杂度较高等一系列问题。
2007 年，KUMARA 等学者［6］首次在面对非常繁琐的社会网络时，尝试将标签传播模型（Label Propagation Algorithm，LPA）运用其中做社区发现的研究。实验结果表明，使用LPA模型的社区发现时间效率等方面指标都有了巨大的突破。该算法模型不需要提前知道真实的社区个数有多少，仅依赖于社会网络的自身结构。LPA 算法复杂度较低，被广泛应用于大规模社会网络的社区发现。
然而，LPA 在每次的迭代过程中存在着随机性，致使每次社区发现的结果都不一致。造成LPA算法稳定性较差和随机性较高的主要原因在于该算法没有充分考虑节点自身的影响力，网络中所有节点均被平等看待。为此，本文引入LeaderRank［7］算法来计算节点的影响力，在根据影响力值对节点进行排序的基础上，采取一定的节点选取策略，筛选出网络中的关键节点；
接着，在初始化网络节点时，这些关键节点被赋予唯一的标签，并将这些节点视为初始传播源；
最后，采用逐层更新的方式更新节点标签。
2.1 标签传播算法
标签传播算法（LPA）的基本思想：一个拥有n个邻居节点x1,x2,…,xn的给定节点x，和该节点x相互连接的节点都有所属于自身的唯一标签，那么该节点的标签信息将由和其相互连接的节点标签信息共同决定。标签传播算法可简述为
1）对图中节点标签初始化时，为每个节点赋予唯一的标签，用来标识节点所在的社区。
2）对图中所有的节点开始迭代更新，节点将会接受和其相连接的节点标签信息，选取和其相连接的节点标签中标签出现频率最大的那个。当多个标签数量相同时，将随机选取其中一个标签作为更新节点的标签。经过多次迭代，使得图中所有的节点标签趋于稳定，社区结构也随之显现出来
3）根据每个节点的标签，将所有的节点进行划分，标签相同的节点将划分为同一社区。
图1 为标签传播过程的一个简单案例。由图可以明显看出，标签为a 的节点在接受邻居节点的标签信息后，由于标签c 的节点数量为2，根据上述原理，标签为a的节点将更新为标签c。
图1 标签传播过程
上述算法有两种更新方式：同步更新和异步更新。采用同步更新将会在二分图上产生循环震荡的问题。如图2 所示，假设p-1 时刻的状态如图2（a）所示，p 时刻的状态如图2（b）所示，那么如此循环下去将无法形成真正的社区。采用异步更新时，那么该节点的标签信息将会由和该节点相连接的节点标签信息中部分p时刻的信息和部分p-1时刻的信息所共同决定。
图2 标签震荡
LPA 模型在时间效率等指标方面有着绝对的优势，现阶段已经在百万级的复杂网络中有着较高的使用频率，但是该算法模型会存在一些无意义的节点标签更新，往往会导致“无意义”的小型社区或者大型社区的形成，这些都是没有研究价值的成果。
赵卓翔等［8］综合考虑了在标签的传播过程中边的权重、每个标签的个数以及需更新节点的邻居节点的度，提出了平均权重的概念。Zhao 等学者［9］将LPA算法模型与物理学中熵相结合，形成一种新的算法模型，该模型主要是计算每个节点所拥有标签的熵值，按照熵值的大小来决定节点更新顺序，从而消除原始算法中的节点更新随意性。康旭彬等［10］采用Jaccard 系数计算节点之间的相似度，并以此决定节点标签的更新选择。张鑫等［11］在通过寻找不重叠三角形的方式来优化标签初始化，并结合邻居节点的影响力来选择标签，提高了社区发现的稳定性。马秀等［12］利用k-shell 方法计算节点的影响力，但k-shell 方法只是一种粗粒度的划分，对节点影响力的计算不够精确。石梦雨等学者在原始标签传播算法的基础上，融合进了LeaderRank算法模型，提出了新的标签传播算法（LRLPA）。Zhang 等［16］将节点重要性融入到原始算法中，计算网络中节点重要性，并以此来替代节点标签的重要程度，形成了一种新的标签传播算法（LPA_NI）。龚宇等［17］将LeaderRank算法与典型的COPRA算法相结合，对发现更加复杂的重叠社区的精准度有了较大的提升。
尽管以上方法在一定程度上提高了LPA 检测社区的精确度，但这些方法在进行网络节点初始化时，为所有节点都赋予了唯一标签。这也意味着，网络中的所有节点均被平等对待，弱化了核心节点的影响力，变相地抬高了边缘节点的影响力，忽略了网络中各节点之间的差异。
2.2 LeaderRank算法
目前用于衡量节点影响力的经典方法有很多，但大多数方法考虑的因素过于单一。如度中心性方法，仅仅从节点的度数进行考虑，忽略了节点自身影响力、邻域节点影响力等诸多因素。以PageRank 为代表的一类算法中还含有参数，在面对不同网络结构时，还需进行参数测试的方式来选取最优参数。
LeaderRank 算法由Zhang 等提出，是一种对社会网络中的节点进行排序的方法。该算法综合考虑了节点度数、邻居节点影响力等因素，无需任何参数，能够自适应网络结构，符合网络中的传播特性，因此被广泛用于复杂网络中节点影响力的度量。
LeaderRank 算法被用于计算网络中节点的影响力，在整个网络图G=（V，E）中加入了一个背景节点vg，该节点与原图中的所有节点均相互链接，使得整个网络图成为强连通图。
首先对背景节点vg分配0 个资源单位的S 值（即LeaderRank值），除背景节点vg外的节点均分配1 个资源单位的S 值，使用式（1）计算每个节点的S值，直至达到稳态。
式（2）用于将背景节点vg的S 值平均分给每个节点。其中，tc表示稳定时刻，Si(tc)表示节点vi在稳定时刻的S 值，Sg(tc)表示背景节点vg在稳定时刻的S值，N为网络G中的节点总数。
本文在LeaderRank算法的基础上，对标签传播算法的节点初始化进行优化并给出新的标签传播策略，提出了一种新的标签传播算法CNE_LPA。在对节点初始化时选取核心节点，并为核心节点提供唯一标签，以减少后续标签传播过程中无意义的判断，提高标签传播过程的整体效率。在标签传播过程中，本文采用逐层更新的方式更新节点标签。
3.1 节点初始化
由于CNE_LPA 算法仅选取部分节点作为初始传播源，为此，从网络中筛选出的核心节点应尽可能地辐射到所有的节点，并尽可能散落于每个社区之中。为实现上述目的，CNE_LPA 算法首先计算网络中所有节点S 值的平均值，将S 值大于平均值的节点优先加入核心节点集中，并确保加入核心节点集的节点不是核心节点集中已存在节点的邻居节点。那么，对于对于网络G=（V，E），其中V 和E分别为网络G 的顶点集和边集，核心节点K 的选取策略可以概述如下。
1）对于∀vi∈V，以S（vi）和avg分别表示节点vi的S 值和网络G 中所有节点S 值的平均值，若S（vi）＞avg，则节点vi将被视为核心节点集K的候选节点；
2）对于∀vj∈K，以Neighbor（vj）表示节点vj的邻居节点，若候选核心节点vi∈Neighbor（vj），那么可以将vi加入核心节点集K。
算法1 核心节点集选取算法
输入：网络G=（V，E）
输出：核心节点集K
算法：
1）对于∀vi∈V，计算所有节点S 值的和Snum，即Snum+= S（vi）；
2）计算网络G 中节点S 值的均值avg=Snum/N，其中N 为网络G中的节点总数；
3）初始化核心节点集K=∅，并将节点集V 拷贝至集合V′，若S（vi）＜avg，将vi从V′中删除，然后将V′中节点按照其S值进行降序排列；
4）若V′≠∅，从节点集V′中任意选取节点vi；
否则，跳转至5）；
（1）将节点集K拷贝至集合K′，跳转至（2），测试节点vi是否为K中节点的邻居；
否则跳转至（5）；
（2）从集合K′中任取一个节点vj，如果vi∉Neighbor（vj）成立，跳转至（3）；
否则跳转至（5）；
（3）将节点vj移出集合K′ ，若K′≠∅，跳转至（2）；
若K′=∅，跳转至（4）；
（4）将节点vi移入集合K，将节点vi从集合V′中删除，跳转至4）；
（5）清空集合K′，将节点vi从集合V′中删除，跳转至4）；
5）输出核心节点集K。
3.2 标签传播策略
在标签传播过程中，如果待更新节点的邻域中拥有最大节点数量的标签不止一个时，传统LPA算法便会随机选取其中的一个标签。这种随机选取标签的方式往往导致相同数据集上多次检测到的社区结果却不一致。
为了降低LPA 在标签传播过程中的随机性，CNE_LPA 算法选取待更新节点vi邻域Neighbor（vi）中影响力最大的节点vk的标签label（vk）作为节点vi的待更新标签labelnew（vi）。也就是说，如果∃vk∈Neighbor（vi），并且对于∀vj∈Neighbor（vi），满足S（vk）≥S（vj），那么labelnew（vi）=label（vk）。直觉上，社会网络中的节点受到与其相邻的所有节点的影响，而这些邻居节点又可能隶属于不同的社区。这意味着，一个节点的影响力实际上是其在多个社区上的影响力的综合表现。为简化起见，如式（3）所示，本文以节点影响力与该节点度的比值来表示该节点在特定社区上的影响力。另外，在节点vi的领域节点中可能存在多个节点与影响力最大的节点vk具有相同标签的情形，为此，CNE_LPA算法以这些具有相同标签的节点局部影响力之和来更新该节点的影响力。因此，当节点vi的标签以节点vk的标签更新后，节点vi的影响力Snew（vi）将按照式（3）所示的方式进行更新：
其中，Neighbor（vi）表示节点vi的邻居节点集合，S（vj）表示节点vj的影响力，d（vj）表示节点的度。
由于CNE_LPA 算法对节点标签采用逐层更新的方式，为此，本文引入多级邻居节点这一概念。按照网络层次结构，一级邻居节点为核心节点的邻居节点，二级邻居节点为一级邻居节点的邻居节点，以此类推。当进行标签传播时，以核心节点集中的核心节点为初始传播源，首先更新一级邻居节点标签；
然后再以一级邻居节点作为传播源来更新二级邻居节点；
以此类推，直到所有节点的标签更新完毕。
当节点标签首次更新时，将采用上述方式更新节点标签，并根据式（3）更新节点的影响力值。如果在更新过程中节点vi已有标签，那么在以影响力值最大的标签label（vk）更新label（vi）之前，需要先计算若以待更新标签label（vk）更新label（vi）后Snew（vi）的值。如果Snew（vi）＞Sold（vi）成立，以label（vk）更新label（vi），即执行labelnew（vi）=label（vk）；
否则label（vi）保持不变。当这个网络G 中的节点标签更新的变化率小于设定的阈值时，算法停止。
算法2 标签传播算法
输入：网络G=（V，E），核心节点集K，节点S值
输出：网络节点标签集L
算法：
1）初始化核心节点集K 中每一节点的标签，并以Null值初始化其余节点标签；
2）初始化集合K″=K，V′=V；
3）若K′≠∅，继续执行1）；
否则跳转至4）
（1）若K′≠∅，从集合K′中任取一个节点vj，否则跳转至（4）
//更新K中一个核心节点vj的所有近邻的标签
（2）从集合V′中搜索节点vj的邻居节点集合N=｛vi|vi∈Neighbor（vj）且vi∈V′｝；
①如果N≠∅，任取其中一个节点vi；
否则，跳转至（3）；
②在vi的邻居中搜索S 值最大且标签值不是Null 的节点vk，即S（vk）=max｛S（vi）|vi∈N且S（vi）≠Null｝；
③根据式（3）计算Snew(vi)，如果Snew(vi)＞Sold(vi)，以label（vk）更新label(vi)，否则保持label(vi)不变；
④将节点vi并入集合K″，跳转至①；
（3）从V′中删除节点vj；
（4）K′=K″，K″=∅，返回3）
4）结束标签更新，算法终止。
3.3 CNE_LPA算法描述
CNE_LPA 算法从原始算法的节点初始化过程以及标签传播过程两个方向进行了优化。CNE_LPA算法的总体步骤如下：
输入：网络G=（V，E）
输出：社区C
算法：
1）初始化迭代次数t=1
2）调用算法1，生成重要节点集K；
3）调用算法2，完成节点标签的一轮更新；
4）t=t+1，如果迭代次数t 小于阈值，返回到步骤2）；
否则结束标签更新；
5）输出社区划分C。
3.4 CNE_LPA算法时间复杂度
在复杂网络G=（V，E）中，有x 个节点和y 条边，核心节点的候选节点为t，核心节点的个数为k。节点影响力的计算时间复杂度为O(x2)，核心节点的筛选时间复杂度为O(x+t2)，初始化核心节点集中的核心节点时间复杂度为O(k)，节点标签的更新迭代时间复杂度为O(x+xyk2)，将所有标签相同的节点划分为同一个社区的时间复杂度为O(x)。那么CNE_LPA 算法的时间复杂度为O(x2+3x+t2+xyk2)。
实验数据主要采用LFR 人工数据集和五种真实网络数据集（Zachary，Football，Dolphin，Jazz，Netscience），在这些数据集的基础上，将使用将使用其他社区检测算法（LPA，LRLPA）来评估本文提出的CNE_LPA算法的性能。
4.1 实验数据
1）LFR人工数据集
LFR 准基网络数据集［13］是如今被广泛用于评测社区发现算法优劣性的人工数据集。LFR 中的信息如表1所示。实验数据集如表2所示。
表1 LFR数据集的信息
表2 4组LFR网络的参数
2）真实数据集
真实数据集如表3所示。
表3 5组真实数据集
4.2 社区划分评价标准
1）模块度［14］
复杂网络划分社区质量的评判指标如式（6）所示：
其中，m代表社区中边的数量，kv与kw分别表示节点v 和w 的度，A 为邻接矩阵。若节点v 和节点w 之间没有连接关系，那么Avw=0，反之，Avw=1。δ(cv,cw)表示节点v和节点w是否在同一个社区内，若在同一个社区内，δ(cv,cw)=1，否则δ(cv,cw)=0。
2）NMI［15］标准
标准化互信息（NMI）用以衡量一个方法下社区划分结果与标准划分的社区相似程度，其公式如下：
其中，CA为标准社区划分的结果，CB为算法所检测到的社区结果，N 代表着节点数，Ci是矩阵C 的第i 行的总和，Cj是矩阵C 的第j 列的总和。Cij是指实际的社区为i但出现在发现社区j中的节点数。
4.3 实验结果及分析
4.3.1 LFR人工数据集分析
在这些实验中，由于传统的LPA算法有着较高的随机性，将LPA 算法在B1、B2、B3、B4 这四组人工数据集上均运行10次。测试效果如图3所示，为了能够体现LPA算法的不稳定，将在四张图中直接用误差线进行描述。
图3 三个算法实验结果折线图
从图中可以明显看出，随着社区结构越来越复杂，LPA 算法的波动性也就越来越大，但CNE_LPA和LRLPA 依然能够稳定地检测社区。总体来说，CNE_LPA 算法在量化节点标签的重要程度时，主要考虑了与其相连接的节点的局部重要性，从而导致在更新时，在精准度上有着较大的提高。从稳定性以及社区检测质量两方面综合考虑，CNE_LPA算法相较于其他两种算法能够更加稳定精确地实现社区检测。
4.3.2 真实数据集分析
在本节中，使用模块化度量将CNE_LPA 算法的性能与之前所提的其他两种算法进行了比较，其中由于LPA算法的不稳定性，因此以LPA算法运行30次的平均值来做对比。为了评估CNE_LPA算法的准确性，本文将在两个真实世界采集的网络节点数据集进行多次试验，并对实验结果进行详细分析。
1）Karate网络分析
真实的Karate 网络有两个预定义的社区，CNE_LPA算法检测到的结果如图4所示，不同社区之间用不同的颜色表示。从图中可以看出，CNE_LPA 算法不但可以准确地检测出两个社区，而且在准确划分社区的基础上可以发现两个社区分别以节点1 和节点34 为中心，由此说明CNE_LPA算法能够发现网络中潜在的社区结构。
为了比较LPA 和CNE_LPA 算法的稳定性，本文将CNE_LPA 算法和原始算法在这两个真实数据集上分别运行30次，算法运行结果的模块度如图5所示。从图中可以明显看出，CNE_LPA 算法有着较高的稳定性，LPA算法波动性较大。
图5 LPA、CNE_LPA算法在Karate上的Q值变化
2）Dolphin网络
Dolphin 网络有两个预定义的社区。本文在Dolphin 这个数据集上测试CNE_LPA 算法并检测到如图6 所示的三个社区，不同社区之间用不同的颜色加以区分。
图6 CNE_LPA算法实现的社区划分结果
从图7 可以看出，LPA 算法因其自身的随机性，产生较大的波动性，并不能有效地检测社区。CNE_LPA算法则能够稳定有效地检测出社区。
图7 LPA、CNE_LPA算法计算出的模块度变化
在表4 中可以看出，从模块化值以及社区发现数量上综合考虑，LPA 算法因为其高随机性的影响，其社区检测结果有着较大的波动性。CNE_LPA 算法相对于其他两种算法，则有着较高的模块度，能够稳定有效地检测出社区。
表4 五种真实数据集在不同算法上运行的社区结果
本文针对标签传播算法的节点初始化进行改进以及给出新的标签传播方法，引入LeaderRank算法衡量网络中节点的影响力，在此基础上选出核心节点作为初始标签传播源，减少了传播过程中的计算复杂度。算法采用逐层更新的方式进行标签更新，并且在传播更新过程中考虑到与更新节点相连接的节点标签重要性，消除了算法更新时极强的随意性。多个数据集上的实验表明，相较于其他算法，CNE_LPA 算法能够更加稳定有效地实现社区的有效检测。
猜你喜欢 复杂度影响力节点 柬语母语者汉语书面语句法复杂度研究华文教学与研究(2022年1期)2022-04-27分区域的树型多链的无线传感器网络路由算法现代电子技术(2022年4期)2022-02-21预期功能安全场景库复杂度量化方法研究汽车工程学报(2022年1期)2022-02-20太极拳，风縻世界的影响力金桥(2021年3期)2021-05-21基于移动汇聚节点和分簇的改进节能路由算法卫星电视与宽带多媒体(2020年7期)2020-06-19Kerr-AdS黑洞的复杂度华东师范大学学报（自然科学版）(2020年1期)2020-03-16My Hobby阅读（快乐英语高年级）(2019年8期)2019-09-10基于点权的混合K-shell关键节点识别方法华东师范大学学报（自然科学版）(2019年3期)2019-06-24非线性电动力学黑洞的复杂度华东师范大学学报（自然科学版）(2019年2期)2019-06-11你凭什么影响别人商业评论(2016年5期)2016-06-07