基于复杂网络的社区发现算法研究

2020年1月Jan.摇2020COMPUTERTECHNOLOGYANDDEVELOPMENT

基于复杂网络的社区发现算法研究

孟彩霞,李楠楠,张摇琰

(西安邮电大学计算机学院,陕西西安700121)

摘摇要:近年来,高质量社区的挖掘和发现已经成为复杂网络研究的一个热点。目前大多的社区发现算法主要针对无向网络,但现在的很多真实网络通常都是有向加权的。同时,标签传播算法(LPA)是一种接近线性复杂度的社区发现算法,该算法具有简单高效、不需要提供社区规模和社区个数等先验知识的特点,因而得到了广泛关注和应用。针对有向加权网络,提出了一种基于节点重要性和节点相似性的改进标签传播算法(CRJ-LPA)。该算法综合考虑节点的边权、节点的信息传播能力、节点相似度以及节点集聚系数等因素。算法通过加权的ClusterRank获得节点重要性列表用以避免LPA中的随机选择;然后,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),提高了算法的稳定性。实验结果表明,该算法有效可行,且具有较好的鲁棒性。关键词:有向加权网络;标签传播;ClusterRank;节点重要性;Jaccard;节点相似度

中图分类号:TP301.6摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇文章编号:1673-629X(2020)01-0082-05doi:10.3969/j.issn.1673-629X.2020.01.015

ResearchonCommunityDetectionAlgorithmBasedonComplexNetwork

(SchoolofComputerScienceandTechnology,Xi爷anUniversityofPostsandTelecommunications,Xi爷an700121,China)

Abstract:Inrecentyears,themininganddiscoveryofhigh-qualitycommunitieshasbecomeahottopicincomplexnetworkresearch.However,mostcommunitydiscoveryalgorithmsaremainlydirectedatundirectednetworks,butmanyrealnetworksareusuallydirectedweighted.Atthesametime,thelabelpropagationalgorithm(LPA)isacommunitydiscoveryalgorithmclosetolinearcomplexity.Itissimpleandefficient,anddoesnotneedtoprovidepriorknowledgesuchascommunitysizeandcommunitynumber,whichhasbeenwidelyconcernedandapplied.Forthedirectedweightednetwork,alabelpropagationalgorithm(CRJ-LPA)basedonnodesimilarityandnodeimportanceisproposed.ThenodeimportancelistisobtainedbyweightedClusterRanktoavoidrandomselectioninLPA.Then,theJaccardcoefficientisusedtomeasurethesimilarityofthenodes.Combinedwiththenodeimportancelist,anewmetricCRJ(importanceandsimilarity)iscalculatedtoimprovethestabilityofthealgorithm.Experimentshowsthattheproposedalgorithmisfeasibleandeffectivewithstrongrobustness.

Keywords:directedweightednetwork;labelpropagation;ClusterRank;nodeimportance;Jaccard;nodesimilarity

MENGCai-xia,LINan-nan,ZHANGYan

0摇引摇言

在现实世界中存在各种复杂系统,这些系统通常可以以网络的形式表达,比如常见的电力网络、航空网络以及社交网络等复杂网络。复杂网络具有小世界、无标度、社区结构等许多基本特性,而其中最为重要的特性是社区结构。为了挖掘这些社区结构,可以使用一些不同领域的方法,如数据挖掘中的聚类或图论中通常将网络表示为图,图中的点表示网络中具体的实的图分区等,挖掘社区结构的过程统称为社区发现[1]。

体,边表示网络中实体与实体之间的关联[2-3]。大多更精确地说是无向图。然而,很多真实网络具有复杂的关系,并且都是有权值和方向的。此外,将有向图转化为无向图会导致信息的丢失,从而使检测到的社区结构没有真正意义[4]。由于很少有文献提出在有向网络中进行社区检测,因此对有向有权的复杂网络进行社区发现是一项艰巨而有意义的任务[5]。

2007年,Raghavan等[6]提出了一种标签传播算法

数关于社区检测的论文使用图作为网络的数学表示,

收稿日期:2019-02-20摇摇摇摇摇摇修回日期:2019-06-24摇摇摇摇摇摇网络出版时间:2019-09-24基金项目:陕西省自然科学基金(2014JM8303);西安邮电大学研究生创新基金(CXL2016-40)

作者简介:孟彩霞(1966-),女,研究生导师,研究方向为大数据处理与数据挖掘;李楠楠(1994-),女,硕士研究生,研究方向为复杂网络和数

据挖掘。

网络出版地址:http://kns.cnki.net/kcms/detail/61.1450.TP.20190924.1537.058.html

摇第1期摇摇摇摇摇摇摇摇摇摇摇摇孟彩霞等:基于复杂网络的社区发现算法研究·83·

(LPA),该算法是一种近似线性复杂度的社区发现算法,并且不需要预先知道社区的规模大小和所需要划分的社区个数等,因此受到学者们的广泛关注和应用。但LPA在标签传播过程中存在随机性、振荡、不稳定,划分社区效果差等缺点,为此大量研究人员进行了相关研究。Sun等[7]提出了一种基于琢-degree邻域影响的标签传播算法,缓解了节点更新中随机更新的问题,提高了算法的稳定性。YanXing等[8]提出了KBLPA和NIBLPA算法,该算法以K-shell算法为依据分析节点的重要性。易秀双等[9]提出了一种基于顶点影响的局部社区发现算法,提高了算法的计算速度和效率。黄佳鑫等[10]在标签传播的思想上综合考虑了节点的重要性和标签的影响力,因此提高了原始标签传播算法的稳定性和准确性。彭磊等[11]依据节点相似度进行更新,提出了NSLPA算法。许合利等[12]提出了一种基于核心节点的加权网络中的局部检测算法CRD-LPA。但是以上这些算法大多数是基于无向图的,因此失去了一些有用的信息,只对社区检测结果进行定量分析。

文中考虑边的方向和权值,将标签传播思想应用于有向加权网络,并且通过加权的ClusterRank获得节

ABDB点重要性列表,以避免LPA中的随机选择。其次,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),提高算法的稳定性和社区发现质量。

1摇标签传播算法

标签传播算法是一种接近线性复杂度的社区发现算法,其基本思想是用已知节点标签信息预测未知节点的标签。

具体算法描述如下:

(1)将所有节点的标签初始化为唯一值,例如初(2)随机地对图中的所有节点进行排序。(3)根据步骤2按顺序更新每个节点,将节点的(4)如果网络中的所有节点的标签均稳定不变,基于标签传播算法的社区检测的具体过程如图1所示。

DDDD始化节点标签为其ID号。

标签更新为邻居中出现次数最多的标签;若当个数最多的标签不唯一时,随机选一个标签赋给当前节点。则算法终止。否则,返回步骤2继续。

12121212C34DC34DC34DD34D图1摇基于LPA的标签传播过程

摇摇在图1中有四个节点,每个节点ID为1,2,3,4,它们的标签被初始化为A,B,C和D。

在标签传播过程中,节点1的标签随机选择为节点4的标签D后,与节点2相邻的节点中,标签D的数量最多,因此节点2的标签也设置为D,这样的过程不断持续下去,直到所有可能聚集到一起的节点都具有了相同的社区标签,此时图1中所有节点的标签都变成了D,所有节点都已达到算法的终止然后退出循环。

标签的更新策略分为:同步更新和异步更新。同步更新是指对于节点x,在第t代时,根据其邻居在t-1代时的社区标签进行更新。异步更新是指节点x,在第t代时,根据其邻居最新的社区标签进行更新。同步更新标签的方法对于二分或者近似二分的网络来说,可能会导致标签的振荡,所以选择异步更新节点标签的方式。

LPA算法的随机性有以下两个方面的问题:(1)节点更新顺序的随机性。每次迭始时,

机性的方法不仅可以产生最佳值,也可能会产生最差值,因此,增加了算法的不稳定性。

(2)当个数最多的标签不唯一时,标签选择是随

机的。这种随机性可能会使得算法的迭代次数增加,并且导致算法不稳定,划分出来的结果也会相对较差。

针对第1个问题,提出基于加权的ClusterRank算法获得节点重要性列表来依次更新节点,避免随机选择;针对第2个问题,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),选择度量值最高的标签进行更新,提高算法的稳定性和社区发现质量。

2摇CRJ-LPA:改进的标签传播算法

LPA的效率吸引了众多学者和研究人员的关注

和研究。有很多算法可以改善LPA的上述问题。NSLPA算法最大改进之处在随机选择。如果有多个可选标签,则节点将选择相似度的邻居节点的标签,而不是随机选择。此方法在一定程度上避免了LPA的随机性问题,

都需要重新随机生成节点更新的顺序。但是,这种随

·摇84摇·摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第30卷

但仍存在逆流问题。CRD-LPA算法将ClusterRank系数与节点局部密度(localdensityofnode,LDN)结合起来进行节点更新。此方法提高了LPA的准确性和稳定性,但CRD函数降低了节点影响力相同的概率,仍存在随机选择的可能性,同时该算法也忽略了节点边的方向性对结果的影响。2.1摇加权的ClusterRank算法

Chen等[13]根据节点的度和聚类系数对有向复杂网络的节点重要性进行了分析,并以此为基础提出了ClusterRank算法。该算法在考虑节点的邻居节点的{ejkj,k沂祝i}为i的两个追随者之间的连接集合。如果kout臆1,则ci=0。i

现有研究提出了计算适用于有向网络和加权网络

其中,kout为节点i的出度,即i的追随者的数量;i

的局部聚类系数的方法,但这些并不适用于加权定向网络。考虑到这一点,文中融合Garas等提出的节点强度概念和信息传播的因素,定义了加权定向网络上的局部聚类系数,如下所示:

ci=

{wjkj,k沂祝i}

'out'out

wout-1)iki(ki

(5)

数量的同时,还考虑到聚类系数对网络中信息传播的巨大影响。ClusterRank算法是对LeaderRank和PageRank算法做了进一步的优化和改进

[14]

ClusterRank没有考虑网络中节点周围的结构信息和,但是

边的权值,因此,无法有效地衡量有向加权网络中节点的重要性。考虑到这个问题,文中结合含权网络中节点强度的定义提出了基于加权的ClusterRank算法。2.1.1摇在加权定向网络中含权网络中的节点强度

,节点vi的度称为强度,节点的

强度可分为出强度bouti和入强度biniout

边的权值之和,bin。bi为与相连的出

i为与相连的入边的权值之和。定义如下所示:

bouti=ij

bin

i

=

其中,移移j沂祝outw

i

(1)j沂祝inw

ji

i

(2)

祝outi为节点vi的出边的集合;祝ini为节点vi

的入边的集合。

上面定义的缺点很明显,忽视了节点的度,在网络中往往存在节点的邻居多而节点强度却很小的情况。Garas等[15]提出了另一种节点强度的定义方式,即用节点的邻居数量和边权重共同表示节点的度值,更加细致地刻画了节点的属性。在这里,节点vi的强度为:

k'ki

i=[k琢i

(移w茁ij)]

琢1

+茁

j

(3)

其中,ki为节点vi的度;wij为节点vi与其邻居vj

之间连边的权值;琢和茁为自由参数,用来调节度和权值之间的比重。

2.1.2摇许多社交网络把有向网络从含权的局部聚类系数

i到j的连接表示为j

是i的追随者,意味着j从i接收信息。将祝i表示为i的追随者集合,即i的出边集合,并且i的追随者之间的相互作用密度可以用i的局部聚类系数表示。有向网络的聚类系数定义为:

c{keoutjkj,k沂祝i=i(kout

i}i

-1)(4)

s.t.摇

k

'out

=[(kout(koutiii

)

琢

茁

琢1

+茁

其中,w

outj

{wi

为节点v移wij)]

i的出边的权值之和;

jkj,k沂祝i}为节点vi的追随者之间连边的权值2.集合1.3摇。

对于含权的ClusterRankClusterRank只考虑节点的聚类系数算法,不适用

于加权网络的问题,提出了适用于加权定向网络的ClusterRank算法。根据式5定义的加权定向网络上的局部聚类系数,重新定义了节点vi的ClusterRank的评分sis:

i'out

s.t.=ff((cic)

j沂祝i

k

j

+wij)(6)

i其中,祝)=移10(-c

i

咨是节点vi的邻居节点集合;wij是节点vi

与节点vj直接相连的边的权值;f(ci)是节点vi的聚类系数的函数。

在复杂网络中,聚类系数越大播,因此随着c2.2摇Jaccard相似度

i增大的f(ci)值将变小,越会阻碍信息的传

。

在复杂网络中,节点之间通常具有一定的相似性,Jaccard为描述相似度的重要指标。在包含节点集V和边集E的图G(V,E)中,节点vJaccard相似度定义如下:

i和节点vj之间的Jaccard(vi,vj)=

NNii疑N胰NNjj

(7)

其中,i表示节点vi的邻居节点的集合,Jaccard的值介于0~1之间,该值越接近1,表示节点vi和节点vj之间的相似度越高。

在LPA算法中,即使通过文中提出的基于加权的ClusterRank算法进行节点重要性排序后进行标签的更新,仍然有可能会出现一定的随机选择。因此,定义了一种新的度量CRJ,通过综合考虑节点重要性和相似性来提高LPA算法的准确性,定义如下:

CRJ(i,j)=

Si

N2

+

Ji

移(8)

j=1

S

j

移NJ

2j=1

j

摇第1期摇摇摇摇摇摇摇摇摇摇摇摇孟彩霞等:基于复杂网络的社区发现算法研究·85·

其中,Si表示节点vi的重要性,Ji表示节点vi和节点vj之间的相似度。采用同趋化函数g(x)=x

对Si和Ji同时进行处理,使CRJ(i,j)能够综

准,该值在[0.3,0.7]的区间内,表示社区划分质量较好。

3.2摇实验结果

数据集Lesmis与Celegansneural是两种有向有权复杂网络数据集,其基本信息如表1所示。

表1摇真实复杂的网络数据集信息

数据集LesmisCelegansneural

节点数N=77N=297

边数E=2E=2359

合衡量节点重要性Si和相似度Ji不同作用的结果,准确地将节点重要性和相似度结合起来。2.3摇CRJ-LPA算法描述

针对有向加权网络,基于原始的LPA算法,文中提出了一种基于节点重要性和相似性的改进CRJ-LPA算法。该算法具体步骤如下:

Step1:初始化,根据节点ID为每个节点分配一个移x

2

摇摇在这两种真实数据集上对算法进行分析与验证,唯一的标签;

Step2:根据式6计算所有节点的重要性,并根据节点重要性由高到低对节点集合V进行排序;

Step3:根据式7计算节点的相似度;

Step4:从节点集合V中依次取出节点进行更新,并且优先更新邻居节点间具有最大影响力的节点,如果出现影响力相同的情况,则根据式8计算邻居节点的CRJ(v,v'CRJ(v,v')的邻居节点),然后将节点v'的标签v的标签更新为具有最高;其次,在标签更新过程中,如果节点的邻居节点中个数最多的标签出现两个或多个时,同样根据CRJ(v,v'标签;

)来更新节点v的Step5:如果网络中的所有节点的标签均稳定不变,则循环停止并退出算法。否则,跳转到Step4继续循环。

3摇实验结果与分析

选取Lesmis与Celegansneural两种国际上公认的真实数据集,对CRJ-LPA算法进行测试。算法的实验环境为Python3.5软件,硬件配置为i5-3230M,RAM:4.00G;软件配置:位WIN7操作系统。3.1摇有向加权网络模块度

文献[13]中Newman和Girvan提出了模块度的概念,后来作为衡量社区算法性能的公认评价标准。再后来,Newman等将其拓展到有向、加权网络上[16]定义如下:

,Q=1in

w移ij(wwoutij-iw

wj

)

啄(ci,cj)

(9)

其中,w为网络中所有边的权值之和,wij为节点vi和vj之间连边的权值,wouti为节点vi出边权值之和,winj为节点vj入边权值之和,ci为节点vi所在社区,cj为节点vj所在社区。若ci与cj相等,则啄(ci,cj为1,否则为0。模块度用来衡量社区结构性的强弱)的值,

其值越接近1,表示划分出的社区结构越强,划分的结果越好。通常采用模块度作为社区发现算法的评价标

并且根据模块度来衡量算法划分的社区结构的优劣。同时,将文中算法CRJ-LPA与传统LPA算法(如LPA、NSLPA、KBLPA算法)进行比较。不同算法分别在数据集上进行运算后的模块度如表2所示。

表2摇算法模块度的比较

算法LesmisCelegansneuralLPANSLPA00KBLPA0..13300.CRJ-LPA

0摇0.110.150441287

0.019023900..0723599传统的摇通过对表LPA、NSLPA2中的实验数据进行分析可以看出6

、KBLPA算法相比,文中算法发现,与的社区结构的平均模块度最大。从上述精准的数字描述可以看出,文中算法在这两种有向有权复杂网络数据集上比传统LPA等算法在性能上有明显提升,且模块度的值均在良好社区结构的模块度区间[0.3,0.7]范围内。因此,文中算法划分的社区结构良好,且算法准确性和稳定性较高。文中算法与LPA算法对Lesmis数据集划分的结果如图2与图3所示。

图2和图3将位于不同社区的节点用直线分隔开,并且通过两幅图的对比可以得出,文中算法发现的社区较传统LPA算法所得社区数量多,且较为稳定,没有超大社区。

4摇结束语

针对有向加权网络,提出了一种基于节点重要性和节点相似性的改进标签传播算法(CRJ-LPA)。该算法综合考虑了复杂网络中边的权值和方向性,并且采用标签传播的思想进行社区发现。首先,通过有向加权的ClusterRank算法获得节点的重要性排序列表,然后根据此顺序更新节点标签,提高社区结构的划分质量;其次,在节点更新过程通过节点重要性和相似性计算出一个新的度量CRJ,以此来避免原始LPA中的随机选择,有效克服了传统标签传播算法的随机性。通过真实数据集对算法进行测试,发现该算法具有较

·摇86摇·摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第30卷

好的可行性和准确性,能够准确地衡量节点的重要性,而且与LPA算法具有相似的时间复杂度。

图2摇文中算法效果

图3摇LPA算法效果

摇摇

tectioninnetworks[J].TheScientificWorldJournal,2014,[9]摇易秀双,韩业挺,王兴伟.一种基于节点影响力的局部社区

发现算法[J].小型微型计算机系统,2013,34(9):1975-1979.2014:627581.

参考文献:

[1]摇AGRESTES,MEOPD,FIUMARAG,etal.Anempirical

comparisonofalgorithmstofindcommunitiesindirectedgraphsandtheirapplicationinwebdataanalytics[J].IEEETransactionsonBigData,2017,3(3):2-306.

[2]摇NEWMANMEJ.Thestructureandfunctionofcomplex

networks[J].SIAMReview,2003,45(2):167-256.机时代,2009(3):57-59.

[3]摇王摇丹,刘发升.复杂网络的社区发现算法研究[J].计算[4]摇LEICHTEA,NEWMANMEJ.Communitystructureindi鄄

(11):118703.

[10]黄佳鑫,郭摇昆,郭摇红.融入节点重要性和标签影响力的

36(6):1171-1175.

标签传播社区发现算法[J].小型微型计算机系统,2015,

[11]彭摇磊.基于标签传播的社区发现算法的研究[D].西安:

西安电子科技大学,2015.

[12]许合利,宁念文,牛丽君.一种结合节点局部影响力的标签

传播算法[J].小型微型计算机系统,2017,38(6):1299-1304.

rectednetworks[J].PhysicalReviewLetters,2008,100

[5]摇杨晓光,朱保平.基于复杂网络的社区发现算法[J].南京

理工大学学报:自然科学版,2016,40(3):267-271.[6]摇RAGHAVANUN,ALBERTR,KUMARAS.Nearlinear

timealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J].PhysicalReviewE,2007,76(3):036106.[7]摇SUNHeli,HUANGJianbin,ZHONGXiang,etal.Label

propagationwith琢-degreeneighborhoodimpactfornetworkNeuroscience,2014(1):1306.

[8]摇XINGYan,MENGFanrong,YONGZhou,etal.Anodein鄄

fluencebasedlabelpropagationalgorithmforcommunityde鄄communitydetection[J].ComputationalIntelligenceand

[13]CHENDuanbing,GAOHui,L譈Linyuan,etal.Identifying

influentialnodesinlarge-scaledirectednetworks:theroleofclustering[J].PloSOne,2013,8(10):e77455.

[14]任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通

报,2014,59(13):1175-1197.

[15]GARASA,SCHWEITZERF,HAVLINS.Ak-shelldecom鄄

Physics,2012,14(8):083030.

[16]NEWMANMEJ.Findingandevaluatingcommunitystruc鄄

026113.

tureinnetworks[J].PhysicalReviewE,2004,69(2):

positionmethodforweightednetworks[J].NewJournalof