费 蓉,李莎莎,胡 博,唐 瑜,方金正

1(西安理工大学 计算机科学与工程学院,西安 710048)

2(北京华电优控科技有限公司,北京 100193)

众多复杂系统都可抽象成为网络模型,如计算机网络、信息网络、社会网络和生物网络等得到了广泛应用[1],社区检测问题对于研究复杂网络以及人类生活具有重要意义.社区检测期望将链接最紧密的节点划分至同一社区,有助于更好地了解整个社交网络,进而有效利用资源[2].现实中,Facebook 等以朋友关系为基础的社交网络上,通过社区检测可进行朋友推荐[3,4].另外也可以用社区检测对具有链接关系并且同兴趣的用户进行兴趣推送[5].除此之外,还可用于交通网络中分析交通对城市功能社区(商业区、居民区、学校等)分布之间的关系[6].

近年来,社区检测问题常归于以下类型:基于图分割的社区检测,需要提前定义分割社区个数及体积,通过最小化社区间的链接边的数量实现社区划分,如Kemighan-Lin 算法和谱划分算法;基于聚类的社区检测则是通过节点间的关系利用聚类的思想将其进行社区检测,以GN 算法[7]、Newman 贪心算法和k-means算法为代表;基于模块度最大化的社区检测如Louvain算法,利用模块度获取最优的网络社区划分;基于非负矩阵的社区检测,利用非负矩阵的思想将节点的链接矩阵进行分解得到节点社区归属矩阵,如LANMF 算法[8];基于标签的社区检测算法,以LPA 算法、CORP算法和LPPB 算法等为代表,对每个节点随机生成标签,逐轮刷新所有节点的标签,直到所有节点的标签不再发生变化为止.

节点拓扑势的概念源于认知物理学中的数据场理论[9],2009年,淦文燕提出了一种基于拓扑势的社区检测方法,利用节点的链接信息构造拓扑势场,在拓扑势场内进行社区划分[10].拓扑势原理近年来得到了长足的发展.2018年,Wang 在山谷结构的拓扑势场下基于节点位置进行分析,设计DOCET 算法[11].但拓扑势社区算法在实践中存在一种现象,当获得的模块度值较高时,社区的划分数量过大,当社区网络过于复杂时,真实数据集出现了很多孤立性节点或孤立性小社区.基于拓扑势原理进行社区划分,存在大量3-4 节点孤立为一个社区的现象出现.这种孤立社区的出现为现实的推送,社区的扩大等带来影响.近期研究显示,社区划分不再单纯的考虑链接结构,而是通过增加节点的属性信息进行社区划分.节点的属性信息越来越受到关注[12].

本文面向含标签属性的社区检测问题,针对上述基于拓扑势进行的社区划分存在的孤立性社区问题,提出了一种结合属性标签的拓扑势社区检测算法(TPCDLP).首先,将结合标签传播思想将属性信息构造出节点间的链接权值.其次,把链接权值加入到拓扑势当中构造拓扑势场.然后,利用核心节点进行子群社区的划分.最后,利用子群社区间核心节点的距离进行社区划分.

1 相关工作

李德毅等2008年提出了社区检测中的拓扑势理论,构造了一种在网络拓扑空间中构造的虚拟势场[8].拓扑势借鉴了数学中的拓扑学和物理中的场论思想,将网络G看作一个包含n个节点的及其相互作用的抽象系统.每一个结节周围存在一个作用场,位于场中的任何节点都会收到其周围节点的影响.但是节点的影响力随着网络距离的增加而快速衰减.

定义1.拓扑势场.一个网络G=(V,E),网络所有节点vi,1≤i≤n都存在一个拓扑势φ (vi),所有节点的拓扑势相互作用从而构成拓扑势场.

定义2.拓扑势.给定网络G=(V,E),其中V={v1,v2,···,vn} 为网络节点,E={(vi,vj)|vi,vj∈V,i≠j}为节点边集合,每个节点的拓扑势计算公式如下:

其中,dij表示节点vi与节点vj之间的网络距离或跳数.影响因子 σ是用于控制每个节点的影响范围.m(vj)表示节点vj的质量,可以用来描述每个节点的固有属性,但是通过相似研究,在本文设置为m(vj)=1.

本文首先利用了信息传播的特性将节点的属性结构In和链关系E转换成节点间的链接权重关系R.随后,利用拓扑势将具有链接关系的网络结构转化成山脉形状的拓扑势域.其次,在山脉形状的立体结构中找到局部最高点,由局部最高点出发进行子群社区的划分.最后根据子群社区的分布情况,将子群社区进行合并得到社区的划分结果C.

2 一种基于标签传播的拓扑势社区检测算法

2.1 节点间链接权值计算

拓扑势算法利用的是链接关系构造拓扑势场,未考虑结节间的属性关系.社区的定义是将具有链接紧密程度的节点化为一个社区,但是结节间的属性关系同样会影响到社区划分的质量和现实场景的应用.

本文利用节点间的属性关系和链接关系构造节点间拓扑势的环境影响因子rij,从而保证节点i和 节点j之间的拓扑势能够受到环境影响因子影响.公式如下:

借鉴标签传播的思想,计算标签从节点vi传播到节点vj的概率P(vi→vj),随后令节点vi和节点vj的环境影响因子rij=P(vi→vj).

2.2 标签传播特性

定义3.节点影响力.设网络G=(V,E)中每个节点vi都拥有一个影响力值,用In fi表示.由于大多网络并不是连通图,因此本文采用文献[13]所提出LeaderRank算法,计算节点的LR 值.

LeaderRank 算法提到社交网络不是一个强连通图,所以引入一个节点g(Ground Node),与其他节点相互连接,使社交网络变成一个强连通图.LeaderRank 算法核心公式:

其中,aij表示节点j到节点i是否有链接,有为1,无为0;表示节点j的出度个数;N表示节点总个数;LRi(t)表示i节点在t时刻的得分;tc表示LRi(t)收敛的得分;表示tc时刻地节点的得分;LRi表示i节点最终的得分.

图1是一个小社交网络拓扑结构图,一共有18 个节点,每个节点代表一个人,每个人都有一个兴趣爱好,将兴趣爱好分为两类,并用两种不同的图标表示人们的兴趣爱好.节点间的连线代表人们之间的关系.通过上述的公式,计算得到这个简单的社交网络数据集每个节点的节点影响力,如表1所示.

图1 小社交网络

表1 小社区网络的节点影响力LR

定义4.传播特性k.定义ki←j为标签从节点j到节点i的传播特性度量值.

该传播特性是由节点vi和节点vj的节点影响力决定的.当LRi远大于In fj时,ki←j≈1,说明vj的影响力较大,节点vi容易受节点vj的影响.反之,当LRj远大于LRi时,ki←j≈0,说明vi的影响力较大,节点vi不容易受节点vj的影响.

以节点1、2、3 为例,已知LR1=0.762 913,LR2=0.915 51,LR3=1.068 08,根据定义4 的公式,可得:

节点1 的影响力LR1小于节点3 和节点4 的影响力.通过比较发现节点1 到节点2 的传播特性要低于节点2 到节点1 的传播特性,同样的节点1 到节点3的传播特性也低于节点3 到节点1 的传播特性.由此,传播特性值可以反映出影响力高的节点与影响力低的节点之间受影响程度的差异.

2.3 节点间的相似度计算

社会网络不仅具有拓扑结构特征,而且网络中节点的内在属性也容易获取,如C-DBLP 中的学者记录都拥有研究方向、工作单位等信息,因此节点的属性特征S(节点的相似度)包含两部分:结构属性S t和节点内在属性In.

结构属性:

节点内在属性:

N(i)表示节点i的所有邻居与节点i的集合.ini={in1,in2,···,inz}为 节点i的内在属性集合,iniz是节点vi的第z个属性值;z是内在属性总个数.

图1所示的社交网络数据集中,节点1 和节点2 都有一个相同的邻居节点3 和节点4,所以结构属性节点1 和节点2 节点都有相同的兴趣爱好,所以内在属性Ln1,2=(1/2)×(1+1)=1.由此节点1 和节点2 间的属性特征S1,2=0.577 35+1=1.577 35.同理,S1,3=1.516 40,S1,4=1.516 40.

2.4 节点间的传播概率计算

定义5.标签传播概率(节点间的关联强度,也就是边的权值).节点j的标签以概率P(i←j)传 播到节点i,P(i←j)取 决于节点i和j的相似性度量Si,j、传播特性度量ki←j和邻接矩阵δ (i,j).

节点j到节点i的标签传播概率体现了标签从节点j传播到节点i的能力,也可以认为是节点j到节点i的有向边的权值.由此可得,节点j到节点i的有向边的权值:

由上述公式可以计算r12=S1,2×k1→2×δ(1,2)=1.577 35×0.465 892×1=0.734 87,r13=0.664 62,r14=0.664 63.由于节点的拓扑势公式φ(vi)=可以先计算节点vi的如图2所示,节点1 的=r12+r13+r14=0.734 87+0.664 62+0.664 63=2.064 12.节点1 到节点2 的标签传播概率决定了节点1 将信息传递到节点2 的能力强度,由此也决定了节点1 到节点2 节点的属性信息和链接信息影响后拓扑势变化.表2是将每个节点到邻居节点的环境影响因子进行加和的结果.

图2 小社交网络的节点1 的环境影响因子

表2 小社交网络的节点环境影响因子求和

表3是通过改进后的拓扑势公式计算出图1的社交网络数据集的每个节点的拓扑势值.并且将节点中拓普势局部最高的节点用五角星标记在图3中.

2.5 子群社区划分

通过节点拓扑势的计算,将网络的链接结构转变成山脉形状的拓扑势场.社区的划分就如同山的划分,山峰、山谷和斜坡,对应社区的核心节点、重叠节点以及内部节点.

定义6.核心节点.假设在一个社交网络G=(V,E)中,其拓扑势域G′=(V,E,ϕ),Ni是节点vi的邻居节点.∀vj∈Ni,如果ϕ (vi)>ϕ(vj),则节点vi是拓扑势域的局部最高点.

通过上述的定义,可以看出核心节点是局部最高点,也就是山峰节点.如果根据当前的核心节点进行社区划分,将会影响社区划分的质量和数量.由此,当前通过核心节点划分的社区被称为子群社区,后续需要进一步处理.图3中五角星标识的节点为拓扑势局部最高点,也就是当前子群社区的核心节点.

定义7.重叠节点.假设在一个社交网络G=(V,E)中,其拓扑势域G′=(V,E,ϕ),Ni是节点vi的邻居节点.∀vj∈Ni,如果ϕ (vi)<ϕ(vj)并且节点vi处在两个不同核心节点的社区的山谷的位置,则节点vi是拓扑势域的重叠节点,也就是山谷节点.

当山谷节点就直接归属于它邻居节点所在的社区.由此,山谷节点i处在两个不同核心节点的社区之间,才能被称为重叠节点.

定义8.内部节点.假设在一个社交网络G=(V,E)中,其拓扑势域G′=(V,E,ϕ),Ni是节点vi的邻居节点.内部节点满足下面任意一种情况成立:(1)∃vj∈Ni,如果ϕ(vi)<ϕ(vj)并且∃vj∈Ni,如果ϕ (vi)>ϕ(vj),则节点vi处于斜波位置,也就是拓扑势域的内部节点.(2)如果ϕ(vi)<ϕ(vj)并且节点vi处在两个同核心节点的社区的山谷的位置,这该节点是社区的内部节点.

定义9.边缘节点.假设在一个社交网络G=(V,E)中,其拓扑势域G′=(V,E,ϕ),Ni是节点vi的邻居节点,Coverlap是重叠节点的集合,Cno−overlap是不重叠节点的集合.(1)如果vi∈Coverlap,则节点vi是边缘节点;(2)∃vj∈Nj,如果vi∈Cno−overlap,而NjCno−overlap,并且NjCoverlap,则节点vi是边缘节点.

边缘节点可以是社区的内部节点也可以是社区的重叠节点.每个节点vi都记录它到它归属社区的核心节点的最短距离NCDi.

2.6 子群合并

在子群社区划分中,拓扑势值为局部最大值的节点视为山峰节点,一个山峰节点对应一个社区.但子群社区划分中存在特殊两种情况.1)当社交网络数据集节点链接稀疏、节点度数相似时,很容易导致划分社区数量过多,社区包含节点过少等问题,从而影响到社区的划分质量和现实应用.2)划分出的社区为孤立子群社区.这种孤立的子群社区不能通过核心节点间的距离关系进行合并.下面对两种情况给出相应解决方案.

2.6.1 子群社区划分

由于社交网络数据集的节点数多,如果利用深度遍历的方法计算核心节点间的距离,计算的复杂度很高,时间耗费长,所以为了快速得到上峰节点间的距离,在子群社区划分的同时,计算子群社区中每个节点到达其社区的上峰节点的距离,最后分析了3 种情况计算子群社区间的距离.

由于社交网络数据集的节点数多,在子群社区划分的同时,计算子群社区中每个节点到达其社区的山峰节点的距离,并分析了计算子群社区间的距离的3 种情况.

(1)两个子群社区不重叠但边缘节点相连接

两个子群社区没有重叠节点,但是社区间的边缘节点互联.该情况下,由于每个边缘节点都存储了到达它自身归属的子群社区的最短距离NCD,可以利用边缘节点进行信息交互,得到两个子群社区的核心节点之间的距离.但是,边缘节点自身归属的子群社区的核心节点的距离不一定相同,需要选取其中最短的距离为两个子群社区不重叠但边缘节点相连接的距离CCD.

(2)子群社区不重叠并且边缘节点相也不连接

子群社区的划分是根据节点的拓扑势值由高到低进行的,但是一旦碰到当前划分的节点其拓普势值为局部最低点的时候,也就是划分到山谷节点时,就结束当前子群社区的划分.为了计算不重叠且边缘节点不相连的两个子群社区的核心节点间的距离,采用边缘节点探测方法进行计算.即利用当前子群社区的边缘节点,根据设置的步长向子群社区外部进行跳转.每当跳到下一个节点,首先判断当前节点是否归属于其他子群社区,是,根据跳转的步长以及初始节点和当前节点的信息计算两个社区的距离;否,跳转到下一个节点.在做边缘探测的时候,探测步长值设置为当前边缘节点到达子群社区核心节点的欧式距离的1/2.

(3)子群社区重叠

当子群社区之间有重叠节点,需根据子群社区间的重叠节点到达核心节点的距离加和,取其最短的路径长度.

对于子群社区间的距离的计算,首先分别对上述3 种情况进行处理和计算得到社区的最短距离,然后将3 种情况的结果进行比较取其最小值,最终得到相近两两社区的最短距离.

2.6.2 子群社区合并

通过上述的3 种情况分析和计算,得到了相近的两个社区之间核心节点的最短路径.根据核心节点的距离,可以将相近的社区进行合并,但是实际上很多数据集其节点的链接关系很稀疏,也就是存在很多孤立的节点以及非常小的“孤立”社区,如图4所示.

图4是citeseer 数据集的数据节点分布,图中显示,左上方的节点有着紧密联系,但下方的节点非常稀疏.节点的稀疏易导致划分的社区数被这些稀疏分布的节点所决定,使得社区划分范围过小失去意义.因此在子群社区划分后,需要将子群社区针对稀疏分布情况进行合并.所以子群社区合并分为两种.

图4 Citeseer 数据集的节点分布

(1)相邻子群社区合并

相近的两个社区之间核心节点的最短路径存放在CCD中,计算d=max(CCD),设置φ 为合并参数取值0-1,φd为合并距离.当CCDij<φd时,将两个社区进行合并,随机将两个子群社区中的一个核心节点设置为合并后社区的核心节点.

(2)稀疏子群社区合并

设定规则:核心节点的信息属性相同的稀疏子群社区合并成为一个大社区.

3 算法实验与结果分析

所有实验均在Intel(R)Core(TM)i7- CPU 3300 和8.00 GB RAM 的个人计算机(PC)上使用Visual Studio 2015 上实现.

3.1 标准实验数据集

为验证算法有效性,以下给出3 个同时拥有链接和属性的社区网络数据集信息,见表4.

表4 数据集信息

3.2 评估标准方法

(1)改进的模块度由于本文是对重叠社区进行社区划分,所以对于模块度的评估标准采用的是一种引入隶属系数的优化基础上同时发现重叠和层次社区结构的方法,节点的隶属系数被重新定义为该节点归属社区的个数.并且改进的模块度值越高,说明社区内部链接更为紧密.其具体公式如下:

其中,Oi表示的是节点i所归属社团的数量,其余和非重叠社团发现评价指标模块度Q类似.

(2)信息熵Entropy.信息熵将社区内部节点用于不相同属性的情况利用公式进行放大,由此判断社区对于属性划分的合理性.信息熵值越大,说明划分出的社区内部节点拥有不同属性的情况越多,从属性的角度分析社区划分不合理,由此希望信息熵值小.信息熵的公式如下:

其中,entropy(ai,cj)=−pijlog2pij,pij为 社区j中的节点具有属性值ai的比例.

(3)社区重叠度Overlap.社区重叠节点的个数决定了社区重叠度Overlap的值.它体现了网络耦合度,计算公式如下:

其中,|c|表示社区c的节点个数,m表示网络节点个数.

(4)综合指标F.一般情况下,重叠度高的网络其模块度相对较低,两者呈现负相关性.而对于实验结果而言,模块度越大,信息熵和重叠度越小,社区挖掘的质量就越好.所以综合以上情况,为了输出更为合适的社区结果,定义F值为综合评估指标:

3.3 对比实验

3.3.1 有属性数据集实验对比

在有属性数据集实验中,将子群社区的划分与合并进行详细的分析.并且为了更好地展示本文提出的算法的优越性,将本文提出的算法与DOCET 算法、LANMF 算法、LPPB 算法[14]、Louvain 算法[15]、SCD算法[16]和DEMON 算法[17]进行实验对比.DOCET 算法、Louvain 算法、SCD 算法和DEMON算法只考虑了社交网络数据集中节点的链接信息,而LANMF 算法和LPPB 算法利用社交网络数据集中节点的链接信息和属性信息进行社区划分.这3 个数据集中,DOCET算法、LANMF 算法、LPPB 算法、SCD 算法和DEMON算法都能进行重叠社区的划分,而Louvain 算法主要针对的是非重叠节点的划分.

(1)子群社区划分

对3 个有属性数据集进行子群社区的划分.首先,根据节点拓扑势值的局部最高点确定核心节点.再利用核心节点进行子群社区划分.最后,将子群社区划分结果进行计算汇总,具体如表5所示.

表5 有属性数据集的子群社区划分

如表5所示,在citeseer 数据集的子群社区数489 个但其中有262 个孤立的子群社区数,也就是一半的社区是孤立子群社区.而这些孤立子群社区节点的数量都小于10,由此citeseer 数据集一半的子群社区的节点数过小.cora 数据集的子群社区数是233 个,其中1/4 的子群社区是孤立子群社区.而WebKB 数据集子群社区数是35 个,它的子群社区划分数量相对于其它两个有属性数据集最小但综合指标最高.通过表中的群社区数和综合指标的数据看,WebKB 数据集当前的子群划分效果好,而citeseer 数据集和cora 数据集子群社区数多,孤立子群社区数占子群社区数的比例大,需要将这些数据集进行进一步的合并,确保社区划分的综合质量.

(2)子群社区合并

子群划分实验中,已经将3 个有属性的数据集进行的子群社区的划分,接下来根据子群社区间的距离CCD和设置的合并范围φd进行社区的合并,φ 的取值为0.2,结果如表6所示.

如表5和表6所示,citeseer 数据集由498 个子群社区合并成为了132 个社区,是合并前子群社区数量的1/4;cora 数据集由233 个子群社区合并成为45 个社区,是合并前子群社区数量的1/5;WebKB 数据集由于数据量小,合并后一共由20 个社区,是合并前子群社区数量的4/7.所以本文提出的算法在社区合并后,3 个有属性数据集的社区数都有所下降.而综合指标方面,citeseer 数据集由合并前0.995442 降到0.909849,而cora 数据集也由合并前0.994164 降到0.876 022.citeseer 数据集和cora 数据集合并后综合指标和合并前的综合指标差距在0.1 左右.然而,造成这两个数据集在合并后综合指标下降的原因是合并子群社区后改进后的模块度下降导致.citeseer 数据集的改进模块度由合并前0.684279 降到0.612224,而重叠度和信息熵的变化不明显.同样的cora 数据集的改进模块度也由合并前0.654599 降到0.563148,而重叠度和信息熵的变化也不明显.相反,WebKB 数据集的综合指标比合并前的综合指标高,由合并前1.259545 升高到1.309186,差距在0.05 左右.在进行子群社区的合并过程中,综合指标在0.1 左右浮动,但是社区数量明显减少.

表6 子群社区合并结果

表6中,将文本提出的TPCDLP 算法和其他3 个社区检测的算法进行了比较.通过比较可以看出,在citeseer 数据集中,Louvain 算法的综合指标最高,再是本文提出的算法.出现这种情况的原因是由于Louvain 算法是用模块度最优的方法进行社区的划分.所以与其他四个算法的改进模块度比较,Louvain算法的改进模块度最高.虽然本文用改进的模块度作为评估标准,但是当社区为非重叠社区时,改进的模块度计算公式其实就是模块度的公式.所以Louvain算法的改进模块度相对其他算法会高,由此综合指标也高.然而在cora 数据集和WebKB 数据集中,本文提出的算法与其他6 个社区检测的算法比较,改进的模块度和综合指标都是最高.本文算法在cora 数据集上,改进的模块度为0.922984,与其他4 个算法的改进的模块度高出最小为0.1 左右;而综合指标为1.212 7985,与其他6 个算法的综合指标高出最小为0.2 左右.本文算法在WebKB 数据集上,改进的模块度为0.839338,同样与其他6 个算法的改进的模块度高出最小为0.1 左右;而综合指标为1.292 0815,同样与其他6 个算法的综合指标高出最小为0.2 左右.所以,通过上述分析,TPCDLP 相对其它6 个算法具有一定的优势.

4 真实社区应用

为了验证本文算法在现实应用中的有效性,选择了3 个真实社交网络数据,如表7所示.

表7 真实社交网络数据集

Karate 为美国空手道俱乐部跆拳道俱乐部的真实划分.

Dolphin 数据集是 D.Lusseau 等人使用长达 7年的时间观察新西兰 Doubtful Sound 海峡 62 只海豚群体的交流情况而得到的海豚社会关系网络.这个网络具有 62 个节点,159 条边.节点表示海豚,而边表示海豚间的频繁接触,该图为无权图.

Football 网络,根据美国大学生足球联赛而创建的一个复杂的社会网络.该网络包含 115 个节点和616 条边,其中网络中的结点代表足球队,两个结点之间的边表示两只球队之间进行过一场比赛.参赛的115 支大学生代表队被分为12 个联盟.比赛的流程是联盟内部的球队先进行小组赛,然后再是联盟之间球队的比赛.

此处选择了标准化互信息(NMI)评价指标来衡量算法得到的社区划分结果与实际社区的相似性分区结果比较.NMI的计算公式如下:

其中,A和B代表社区网络的两个分区,C是混淆矩阵,混淆矩阵C中的元素Cij表示社区i除以A和社区j除以B的节点数.CA(CB)表示A(B)分区中的社区数,Ci(Cj)是混淆矩阵C中第i行 (j列)元素的和,N是原始社区网络中的节点总数.当NMI值为1 时,表示A和B在社区网络中的划分相同.

由于3 个真实社区数据集不含属性信息,此处采用Louvain 算法、DEMON 算法和DOCET 算法与提出的TPCDLP 算法进行比较.实验结果如表8所示:在海豚数据集(dolphins)上,本文提出的MIFCD算法的NMI值最高;在空手道数据集(karate)上,本文提出的TPCDLP 算法的NMI 值优于DEMON 算法;在足球数据集(football)上,TPCDLP 表现好于DOCET算法.可以看出,TPCDLP 能够基本实现真实社区划分.

表8 归一化互信息评价指标的实验结果

5 总结

本文提出了一种基于标签属性的拓扑势社区检测算法.该算法利用标签传播方法构造节点间的链接权重,保证分割社区中的节点具有紧密的链接,并保持区域内部属性特征高度一致.由于实际网络数据具有冗余关系、数据存储量大、数据分布离散等特点,采用拓扑势最高的局部节点作为社区的核心节点进行社区划分的算法容易导致社区重叠度高、数量多,因此,在划分子社区之后,利用子节点与属性特征之间的距离划分社区,在保证社区节点之间的链接紧密性和属性相关性的同时,能够解决细粒度独立社区问题.