一种基于局部相似性的社区发现算法

一种基于局部相似性的社区发现算法

吴钟刚;吕钊

【摘 要】现有社区发现算法大多仅考虑图的拓扑结构或节点的属性信息,其中结合两者的属性图聚类算法挖掘效果不理想,而基于共享邻居的局部相似性算法却未充分度量节点间相似度.针对上述问题,提出一种新的基于局部相似性的节点相似度社区发现算法.该算法包括基于局部相似性的节点相似度计算和节点聚类2个模块.利用Pagerank算法计算基于图链接结构的节点重要性,衡量节点间的链接强度并结合节点的属性得到节点对相似性.为避免基于共享邻居的节点相似度计算的低估倾向,引入邻居节点集之间的相似度作为节点局部相似性.采用K-Medoids聚类算法将节点与分组中心节点的局部相似性值作为节点类别归属的判断,得到社区划分的结果.实验结果表明,与经典SA-Cluster与k-SNAP等算法相比,该算法能挖掘出质量更高的社区,具有较好的社区划分效果.%Many existing community detection

algorithms focus on topological structure or node attributes.Some attribut

graph clustering algorithms consider both of them but the quality of

community is not good.Shared neighbors based local similarity algorithms

underestimate pairwise of node similarity.Hence,this paper proposes a new

Local Similarity based Community Detection(LS-CD)algorithm.The

proposed algorithm contains two main components:node local similarity

calculation and node clustering.It evaluates the vertex importance using

the Pagerank algorithm and calculates the similarity of pairwise vertexes

by combining connetion strength and node attribute.To avoid

underestimating node similarity based on shared neighbors,the similarity

of vertexes is calculated by the similarity of their local neighborhoods.The K-Medoids

clusteringalgorithmisusedtoidentifycommunitybymeasuringthelocalsimilarityofnodeandclustercentroid.Experimentalresultsshowthat,comparedwithtraditionalSA-Clusterandk-SNAPalgorithms,thisalgorithmcanminehighqualitycommunityandhasgoodcommunityidentificationeffect.

【期刊名称】《计算机工程》

【年(卷),期】2016(042)012

【总页数】8页(P196-203)

【关键词】社区发现;图聚类;属性图;节点重要性;局部相似性;节点相似度

【作 者】吴钟刚;吕钊

【作者单位】华东师范大学 计算机科学技术系,上海 200241;华东师范大学 计算机科学技术系,上海 200241

【正文语种】中 文

【中图分类】TP311

近年来社会网络得到广泛应用,如科学家合作网、博客网络、电子邮件网络等。社会网络中的社区定义为网络中的节点集合以及节点之间产生的联系,使得社区内部节点的链接比较紧密,而社区之间的节点链接相对稀疏[1]。社会网络具有2个重要特征：一个是社区结构,即网络的结构性质;另一个是网络中节点属性信息,能促进更好地理解网络。例如,在科学家合作网络中节点表示对应的论文作者,边则表示论文作者之间的论文合著关系,论文作者的研究主题可作为节点的属性信息,表明了论文作者的研究兴趣。

社区发现作为社会网络研究的重要问题之一,受到了广泛的关注。研究者将社会网络描述为社会网络关系图,通过图聚类算法将节点划分到分组中[2-3]。在传统的图聚类方法中,通过分析图的拓扑结构后进行图聚类,有基于图划分[4-5]、基于密度[6-7]、基于层级聚类[8-9]等。这些方法划分得到的子图的节点属性信息混杂,同质性较低。基于属性相似的k-SNAP算法[10]得到的每个子图内的属性相同,但图结构松散。

为充分考虑图结构与节点属性信息,文献[11]采用类似Newman[12]的模块度的定义方法,通过权重因子调节结构模块度和属性模块度。该方法在节点分组判定时,通过移动节点到某个分组中,并计算混合模块度的增量正负变化以确定节点是否归属到新的分组。文献[13]结合图结构与节点属性生成扩展属性图。其假设同一个分组的结构边的链接方式和节点的属性遵从相同的概率分布,采用概率推理模型衡量属性图的同质性。文献[14]提出基于随机游走模型的算法SA-Cluster,通过把属性作为节点加入到原有图中形成扩展属性图。该方法需要计算2种类型的边的权重:原结构节点与原结构节点,原结构节点与属性节点。该方法首先构建概率转换矩阵,然后利用随机游走算法计算节点之间的距离(即节点间的相似度),最后采用K-Medoids聚类算法实现图的聚类。

相关文献中采用了基于共同邻居的节点相似度计算方法,文献[7]通过构造最近邻子图,计算基于共同近邻的节点相似度值,然后采用密度聚类算法。文献[15]列出了常见的基于共同邻居的节点相似度计算方法,如共同邻居数算法、Jaccard相似度等。基于共同邻居的节点相似度计算方法存在以下不足:1)节点间无共同邻居时,得到相似度值为0;2)需要计算相似度的2个节点本身并没有参与计算,而是依赖于两者的共同邻居;3)未考虑到其他非共同邻居对相似度计算。

针对上述算法的不足,本文提出一种新的基于局部相似性的社区发现算法。 社会网络可形式化描述为属性图,类似文献[3,14,16]的定义方法,属性图表示为G=(V,E,X,F),其中,顶点集V={v1,v2,…,vN}对应网络中N个节点;边集合中M条边;X={a1,a2,…,aT}描述网络节点的属性,权重为表示节点的属性及属性值映射关系。图的邻接矩阵A,存在从节点vi到节点vj的有向边时,则Aij=1,否则Aij=0。节点vi入边邻居集为NI(vi),出边邻居集为NO(vi),节点vi的出入边邻居集为NIO(vi),定义vi的局部邻居集为NL(vi)=NIO(vi)∪vi。

属性信息可以分为3种类型:离散型,连续性和文本型,本文仅考虑离散型的属性。本文方法用于发现非重叠的社区,根据社区的定义[1],文中将社区发现转化为属性图的节点聚类问题,满足以下条件:

1)Ci≠Φ,i =1,2,…,K。

,∀Ci⊆V。

3)Ci∩Cj=Φ,i,j=1,2,…,K,且i≠j。

其中,每个节点都仅属于其中一个分组Ci。

在图1中,顶点表示论文作者,边表示作者之间的论文合作关系,每个作者都有对应的研究内容作为其属性信息。v1的局部邻居集为NL(v1)={v1,v3,v4,v5},v2的局部邻居集为NL(v2)={v2,v5,v6,v7,v8},其中,节点v5为两者的共同邻居。v3和v6虽无直接的论文合作关系且不是v1和v2的共同邻居,但都与v1和v2有相同的研究内容。

根据节点聚类目标,转化为衡量节点v1和v2的相似度，需要考虑以下2个问题:

1)相似度计算过程中需要考虑哪些邻居节点;

2)不同邻居节点对相似度计算的影响程度。

本文通过计算v1的邻居集NL(v1)与v2的邻居集NL(v2)的相似度SN(v1,v2)作为节点v1和v2的局部相似性。以往基于共同邻居的节点相似度计算方法,忽略了非共同邻居对节点的影响。实际上,节点和它的邻居节点会有某种程度上的相似性,即节点的邻居节点都一定程度影响着节点之间的相似度计算,因此,在计算vi和vj的局部相似性时考虑所有直接邻居。

为了完成社区发现任务,本文从以下2个方面进行:1)结合节点的结构相似性ST(vi,vj)和属性相似性SA(vi,vj),计算节点对的相似性STA(vi,vj),再计算基于局部邻居相似度作为节点相似度SN(vi,vj);2)采用K-Medoids聚类算法对基于局部相似性的节点进行聚类。

本文提出的LS-CD算法框架如图2所示,该算法包括2个部分:局部相似性度量和节点聚类。该方法的基本步骤如下:首先计算节点的重要性,并衡量节点的链接强度,结合节点的属性相似度,得到节点对相似性。其次在聚类过程中,利用重要性高的节点作为分组初始的中心节点。再计算待分类节点与分组中心节点的局部相似性,判别节点的分组归属。最后更新中心节点以及属性权值调节并进行循环迭代。

2.1 局部相似性度量

节点的局部相似性的度量由节点对相似性计算和节点局部相似性计算2个部分组成。

2.1.1 节点对相似性计算

节点对相似性计算方法如下:

1)节点链接强度。节点在图中的重要程度是不同的,节点之间的链接关系强度也是不同的。文献[17]利用Pagerank算法分析论文引用网络中科学论文的重要性,文献[18]采用PageRank分析网页质量。本文通过Pagerank算法计算每个节点vi基于整个图G的重要性,计算如下:

其中,d表示一个节点通过链接达到其他节点的概率值。d的取值范围为0～1,根据文献[19]的实验,d=0.85时效果较好,因而本文d设置为0.85。

计算得到节点vi的重要性φi后,重新计算节点之间的链接强度。类似节点重要性的计算方式,节点的每条出边权重表示为φi/|NO(vi)|,节点vi到vj的链接强度表示为vi的出边权重与被指向节点vj的重要性φj的比值。定义如下:

其中,如果节点vi的出边权重在vj节点的重要度中比值越高,则相应从节点vi到vj具有更大的链接强度。vi和vj节点间的链接强度ST(vi,vj)计算如下:

ST(vi,vj)=Sl(vi,vj)+Sl(vj,vi)

计算节点间的链接强度,本文考虑到边的有向性,即vi到vj的链接强度与vj到vi的链接强度之和。

2)节点属性相似度。节点属性信息是另一个重要的信息,本文考虑的是离散型的节点属性。对于某个属性ai,属性相似度计算如下:

即如果2个节点的某个属性对应的属性值相同,则该属性的相似度为1,否则为0。在满足,且wm≥0条件下,节点间的属性相似度为:

其中,SA(vi,vj)的取值范围为[0,1]。聚类过程中对属性的权重进行调节[14],使得有利于聚类的属性有更高的权重。