节点不对称转移概率的网络社区发现算法∗

2019-10-26许平华胡文斌邱振宇唐传慧刘中舟

软件学报 2019年12期

许平华, 胡文斌, 邱振宇, 聂聪, 唐传慧, 高旷, 刘中舟

(武汉大学计算机学院,湖北武汉 430072)

社会网络中的社区由网络中一定数量的节点组成,其内部有着较为紧密的结构.研究网络中的社区结构可以帮助分析复杂网络、预测社会网络的发展趋势,而且在广告投放和作弊用户检测等实际场景中得到应用.

相关文献中已经有很多种社区发现方法被提出,其中一类是优化与图的拓扑结构相关联的社区质量指标,例如由Newman等人[1]提出的模块度.基于优化指标数值来获得更加可靠的社区结构的这一思路,有很多学者提出了相关的社区发现算法,其中较为典型的有优化变体模块度的BiLPA算法[2]、优化结构密度的IsoFdp算法[3]和对混合指标进行优化的EFA算法[4]、MOCD-PSO算法[5]等.这些算法一般是通过相应的迭代步骤来更新需要优化的指标,并在最后输出最优指标对应的社区结构.这类算法的优点是实现简单,在人工构造的网络上可以发挥出很好的效果.然而真实世界的网络要比人工构造的网络复杂许多,很多时候真实社区结构对应的质量指标并不是最优的,导致了上述基于指标优化的算法难以正确地检测到社区.同时,由于上述部分算法是基于全局拓扑结构来进行优化,因此会受到分辨率极限[6]的限制.并且,某些并不具有明显社区结构的网络同样会具有很高的质量指标,例如某些树或类树结构[7].因此,这些缺陷都在一定程度上限制了上述方法的应用场景.

另外有一些学者从节点相似性的角度提出了基于random walk的社区发现方法[8−16],这类方法以马尔可夫模型为理论基础,通常是通过节点的随机转移来评估节点的相似度,并将相似度较高的节点划分到同一社区中.在真实网络中,同一社区质量指标与不同类型的社区结构的匹配程度变化较大,由此可能会导致基于社区质量指标的社区发现算法适应性较弱,而基于random walk的算法受社区类型的影响较小,具有更好的适应性.但是,基于“利用random walk来评价节点相似度”这一思路的社区发现算法对游走过程的迭代次数非常敏感,往往需要先验知识来辅助决策.

将现实世界中的复杂系统抽象为图论中的网络虽然便于研究工作的开展,但也不可避免地会遗漏掉一些重要的信息.例如,Reddit中属于同一兴趣组的用户往往有着相同的兴趣标签,若能将属性信息转化为网络的一部分,可能会使得社区内部的结构更加紧密,也能使处于社区边缘位置上的节点有更大概率被划分到正确的社区中.然而,现有的仅从网络结构层面划分社区的算法无法利用节点的属性信息.

基于以上分析,本文提出了一种可用于无向和有向网络的社区发现算法CDATP(community detection algorithm based on asymmetric transition probability of nodes),此算法可以将节点的属性转化为拓扑结构的一部分,并且受到事件在网络中的传播规律的启发,根据网络的拓扑结构计算每一节点向邻接节点转移的概率,以带有限制的random walk来模拟逆向的事件传播过程,并以此为基础,评估节点在社区中的重要程度(核心系数).在聚类时,无需预先指定社区的数目,节点会根据转移概率等参数向所属社区转移.本文的主要工作可以总结如下:

(1) 充分利用了网络拓扑结构信息,为节点设计了不对称的转移概率,能够反映节点间的不对等关系;

(2) 参考了事件在网络中传播的规律,提出一种基于random walk且具有固定转移步长的方法来评估节点对于社区的重要程度,基于该重要程度指标的聚类不需要预先指定社区数目.

本文第1节介绍相关研究工作.第2节详细介绍CDATP算法.第3节为实验和分析.第4节是总结与展望.

1 相关工作

近年来,普遍存在于网络中的社区结构已经受到了国内外学者的广泛关注.关于社区发现的研究也已经被应用到了许多领域中,并取得了不错的成果.

基于社区质量指标来划分社区是一类很经典的方法,这类方法通常先定义一个基于网络拓扑结构的社区质量指标,若一种社区划分与预先定义的质量指标的“含义”越接近(如社区内部的边数远多于社区边缘上的边数),那么该社区划分的得分越高.这类方法的优点是思路简洁明了,在确定了质量指标后只需通过一系列迭代运算来搜索最优社区划分.但同时,如何确定社区质量指标也成了最大的问题.因为若一个社区质量指标不能较好地体现真实社区的“含义”,或者说一种社区划分得分很高但却与真实社区结构相差甚远,那么基于该质量指标的后续工作都将变得没有意义.经过长时间的研究,学者们提出了一些表现较好的经典社区质量指标,包括结构密度和模块度等.结构密度的大小和社区内部边的数量与社区内部节点的数量比值相关,一般来说,结构较为紧密的社区对应的结构密度较大.You等人[3]提出的IsoFdp算法将网络数据映射到低维空间并自动找出社区的中心节点,然后再以中心节点为基础建立社区,并通过对结构密度的优化来搜索更好的社区划分.相较于传统的基于结构密度的社区发现算法,IsoFdp的最大优势是可以自动识别出社区的中心节点,有较好的可行性.模块度的内涵是评价人工社区划分与随机社区划分的差异性.Newman等人[17]提出的FastQ算法是最为经典的基于模块度的社区发现算法,该算法以贪心策略进行分层聚类,其优点是收敛速度快,可以在较短时间内找到模块度最大的社区划分.虽然很多基于社区质量指标的社区发现算法在人工网络上有很好的表现,但在处理真实网络时,容易产生时好时坏的结果.这是因为真实网络的度分布相较于人工网络随机性较大,社区质量指标有时与真实社区结构不匹配[18].为了减少这种不匹配带来的问题,一些学者开始研究更小粒度的质量指标.Bai等人[19]提出的ISCD+算法中定义了针对节点的质量指标,包含节点的局部重要性和全局重要性.与传统的社区质量指标不同,该指标并非是基于社区划分,而是基于原始网络中的每一个节点.实验结果表明:在一些真实网络上,该算法的表现优于部分基于社区质量指标的算法.受到现有的各类质量指标的启发,本文尝试定义一种新的基于节点的质量指标,并希望该指标能够较好地适应不同类型的真实网络.

将基于马尔可夫模型的random walk用于社区发现也是较为主流的研究方法之一,其主要思想是以一个初始分布释放大量的无规则行走者,在扩散过程之后,可以得到行走者的分布函数.通过一系列研究,国内外学者提出了若干种基于random walk的社区发现算法.Pons等人[8]提出的Walktrap算法是最早的基于random walk的方法之一,该算法的主要思想类似于“在社区结构中,节点间有着更多的联系,而不同社区间的联系则相对较少.因此,一个随机选择方向的行走者将会被更长时间地困在社区内部[20]”.Walktrap算法采用了分层聚类的方式发现社区,得到的社区有很清晰的层级结构.虽然Walktrap算法在准确度上有所欠缺,但该算法的思路对于后来的同类型算法有很强的启发作用.Lai等人[9]通过将边的方向信息转化为边的权重实现了将有向网络转化为无向网络,并进一步通过基于无向网络的算法来发现原来的有向网络中的社区.该算法处理边的方向信息的方式很新颖,且在基于有向网络的社区发现问题中取得了不错的效果,但转化过程计算量较大,且不适用于基于无权值网络算法的拓展.Jiao等人[10]综合考虑了全局拓扑结构和局部拓扑结构,并在此基础上提出了新的节点相似度计算方法,与以往算法相比,对不同类型社区的适应性更强.Huang等人[11]提出的SCMAG算法通过计算节点属性相似度来从节点属性的角度构建社区,并证明了节点属性与社区结构之间存在密切的联系,属于同一社区的节点往往具有相似的属性.本文受其启发,尝试以将节点属性转化为拓扑结构信息的方式来处理节点属性.此外,文献[12−16]各自提出了将random walk与其他经典方法进行融合得到的社区发现算法,在一些特定的网络模型上有较好的表现.然而,上述算法在节点转移的步骤中多采用的是无差别转移概率,不能完全反映真实网络中节点关系的不对称性,且社区划分的准确性受转移迭代次数影响较大,需要较多的先验知识来辅助决策;同时,本文认为,由于random walk在模拟随机过程等方面具备一些优良的特性,可以将其作相应改进后用于评价节点的质量指标,而在目前的工作中,尚未发现有人进行过这样的尝试.

在社区发现领域的研究初期,大部分学者都是以无向网络作为研究对象.但随着社区发现技术在实际生产情景中的应用推广,有越来越多的学者开始关注如何在有向网络中发现社区.早期的一种处理方法是忽略掉边的方向,将其直接作为无向网络来处理.例如,将经典的基于无向网络的LP算法[21]直接用于忽略了边的方向的有向网络,在某些情况下仍有不错的准确率,可用作对有向网络算法测试的基线.但文献[22]中指出:边的方向应该被考虑,否则会使得网络的重要特征丢失.其中一个重要原因就是:当忽略了边的方向后,节点间的相互关系将变得不完整.例如,Twitter中的某一用户单方面关注了另一用户,那他们之间的位置是不平等的,但无向边无法描述这种关系.一部分学者根据有向网络的特征重新设计了质量指标,例如,Newman等人[23]提出了有向版本的模块度,在原来的模块度定义的基础上考虑了边的方向信息,是最早的基于有向网络的社区质量指标之一.Rosvall等人[24]基于信息论提出了Infomap算法,该算法根据网络的拓扑结构来预测数据的流动,然后对其进行信息编码,而平均长度最短的编码方式就对应了最优的社区划分.得益于其简洁而优美的设计思路,Infomap算法可被用于处理各种不同类型的网络,且均有不错的表现.Lancichinetti等人[25]提出的OSLOM算法是另一个非常经典的可用于有向网络的社区发现算法,它使用了一个基于簇的质量指标来评价人工划分得到的簇与随机生成的簇之间的差异,并通过局部优化来找到得分较高的簇,最后基于这些簇来生成社区.Lancichinetti等人对网络中的度分布有较深入的研究,并且开发了基于幂分布的基准网络[26]用于检验社区发现算法的准确性,而OSLOM算法也在人工网络上有非常好的表现.Santos等人[27]基于改进后的模块度提出了ConClus算法,该算法规避了传统的模块度优化算法常常会碰到的分辨率极限问题.实验结果表明,ConClus在人工有向网络上有与OSLOM十分相近的表现,且在真实网络上也有不错的表现.上述的可用于有向网络的社区算法一般在人工网络上有较高的准确率,但在一些真实网络上,其准确率仍有较大的提升空间.因此,提高算法在真实网络上的准确率也是本文尝试去实现的目标之一.

受到现有的社区发现算法的优势及缺陷的启发,本文参考了网络中的事件传播规律,提出一种基于random walk的方法来评价节点对社区的重要程度.与现有的基于random walk的节点相似度评价方法不同,本文设计了基于拓扑结构的不对称节点转移概率,并尝试从模拟事件传播的角度来评价节点对社区的重要程度而非节点相似度,且转移过程具有固定的步长,不需要额外的先验知识的辅助.最后,本文在该评价方法的基础上提出了一种不需要预先指定社区数量,且在真实数据集和人工数据集上都能有较好表现的网络社区发现算法.

2 社区发现算法CDATP

CDATP算法基于random walk方法来计算节点属性相似性、节点间影响力,并以此为基准评估节点对社区重要程度,最后使节点向社区核心靠拢来划分社区.

为使下文的描述简洁,本文将研究对象的相关重要概念进行符号化定义,见表1.

Table 1 Symbols and their remarks表1 相关符号及其注释

2.1 整体框架

图1描述了CDATP进行社区检测的整体框架,输入数据集包括社交网络等复杂社会网络,输出结果为社区序列.

Fig.1 Framework of CDATP图1 CDATP框架

框架包含以下两个部分.

(1) 在子空间构造阶段中找到表现最好的子属性空间,并将相应的属性转化为网络中的虚拟节点,构造属性增强网络;

(2) 在社区划分阶段中,以属性增强网络为对象计算节点转移概率,使用random walk方法评估节点核心系数,在此基础上确定每个节点的聚类方向,创建初始社区,再进行边缘修剪,最终输出社区序列Comms.

CDATP的描述见算法1.

算法1.CDATP.

2.2 子空间构造和属性增强图

“物以类聚,人以群分”.人们通常会依其兴趣爱好、工作内容来发展社交圈,而各种物件也能被按照其特性、功能划分类别,属性是对象间建立起联系的重要“桥梁”.与研究高度抽象的网络不同,在研究现实世界中更为复杂的情景时,若忽略了节点本身具备的属性,很可能就会错过一些重要的信息.属于同一社区的节点往往拥有某些相近甚至相同的属性值,在考虑这些属性后,能更科学地度量节点间联系的强弱,使得社区的边界变得更加清晰,同时还能够从节点属性的角度帮助挖掘社区结构形成的原因.

为了度量属性对节点间联系的影响,本文采用了将属性转化为网络中的虚拟节点来构造属性增强网络的方法.对于属性Ai,若离散化后有Dom(Ai)={a1,a2,…,ak},则在图中加入k个虚拟节点,与Ai的取值一一对应,并在原网络节点与其对应属性值的虚拟节点间建立一条双向边,如图2所示,拥有相同属性值的节点以虚拟节点为中介(虚拟节点可视为边的一部分而非独立的节点)产生了新的联系.

Fig.2 Virtual nodes图2 虚拟节点

但是,并非所有属性都是有价值的.将节点的所有属性直接加入计算不仅会降低计算效率,甚至可能因为在不同社区间产生了过多联系而导致社区检测准确率下降.现在先考虑使用单个属性.如图3(a)所示,网络中存在两个社区C1和C2,C1和C2之间联系非常少.若考虑描述对象性别的二元属性sex,则C1和C2之间sex值相同的节点(假定有这样的节点对存在)间就会产生联系,如图3(b)所示,这种联系的数量是很多的,破坏了C1和C2较为独立的状态,对社区划分的结果产生负面影响;若考虑描述对象身份证号码的属性ID,则由于每个节点的ID的值都不一样,如图3(c)所示,节点间不会产生新的联系,因此对社区的划分同样没有帮助.

Fig.3 An example of an attribute enhancement network图3 属性增强网络的示例

因此,需要选择合适的属性,这种属性应当满足下面两个条件.

(1) 在结构上联系紧密的节点在该属性上有相同属性值的概率较大;

(2) 在考虑该属性之后,不同社区间应尽可能少地产生新的联系.

而且,只有一个属性相同往往不能说明节点间就有很强的联系,考虑的属性数目越多,则属性值相同的偶然性越小,考虑包含多个属性的子属性空间相较于考虑单个属性更加可靠.将子属性空间中的所有属性看作一个复合属性,它同样应该满足前面提到的两个条件.

信息熵可以理解为特定信息的出现概率.对于属性Ai,若Dom(Ai)={a1,a2,…,ak},且对应属性值为ai的节点个数为ni,则其信息熵H(Ai)可用公式(1)计算:

由于不存在重复的取值,所以前文中提到ID属性的信息熵非常大,而这样的属性是没有意义的,因此不应将信息熵超过阈值ht的属性加入子属性空间.

本文构造了属性信息矩阵Y=(yij)N×N来描述虚拟节点对原节点间关系的影响,若节点vi与节点vj具有相同的属性值,则yij=1;否则yij=0.另外,本文构造了增量邻接矩阵来描述加入了虚拟节点后新的网络拓扑结构,若yij与wij之和不为0,则

在此基础上,本文定义了属性的结构影响度Affect(Ai).属性的结构影响度应能反映在将属性信息转化为拓扑结构信息后,原节点间的联系受到了多大的影响.Affect(Ai)可由公式(2)计算得到:

其中,αA是矩阵缩放因子,旨在更加明显地区分属性的结构影响度.

子属性空间应同时满足信息熵较小和结构影响度较小的条件,其构造步骤如下.

(1) 计算每个属性的信息熵,并筛除信息熵大于阈值ht的属性;

(2) 计算剩余属性的结构影响度,并选择结构影响度小于阈值at且信息熵最小的属性加入子属性空间;

(3) 将剩余属性按信息熵从小到大排序,若其中的属性加入子属性空间后,使得子属性空间的信息熵和结构影响度均小于阈值,则将其加入子属性空间.

2.3 聚类方向和社区划分

由于缺少先验知识,需要预先指定社区数目的聚类方法往往难以在社区发现中取得良好效果.为了能够得到更加准确的社区结构,本文提出了一种自动确定社区的核心,并使核心以外的节点按照各自的聚类方向向核心靠拢的聚类方法,由此得到的社区不仅内部聚合度高,并且有着很清晰的层次结构,便于对社区中的事件传播过程做进一步的研究.

文献[28]指出,一个节点的状态有一定概率会因其邻接节点的行为而发生改变.若一个光标可从一个节点向它的任意邻接节点转移,且倾向于向有更大概率会对其状态产生影响的节点转移,那么在进行一定次数的转移后,光标会有较大的概率落到事件传播流中原节点的上游位置.而由于事件在传播过程中,其影响力会呈现衰退的趋势,本文参考了文献[28]中的实验结果,设定光标在寻找上游的过程中,将转移2次.

本文构造了节点影响力force的概念来描述任意节点的邻接节点会对其产生的影响,并假定该影响是由拓扑结构中的出链与入链以及节点间相同的属性产生的.

记forceij为节点vj对节点vi的影响力,,其中,是由节点vi指向节点vj的出链产生的影响力,是由节点vj指向节点vi的入链产生的影响力,是由属性关系产生的影响力.

以微博为例,如图4所示,边的宽度代表影响力的大小,关注关系和粉丝关系可由网络中的有向边表示,属性关系可由原节点与虚拟节点的联系表示.若用户A关注了用户B,说明B产生的内容对A有一定的的影响力.A接收到的内容信息量与其关注的总人数有关,人数越多,信息量越大,B产生的内容的信息量占比就小,对A产生的吸引力也会变弱;相反地,当A关注人数较少时,B对A的影响力会更强.同时,由于A成为了B的粉丝,B因为这种关系,也会在一定程度上被A产生的内容吸引,同样的,影响力的强弱与B的粉丝数有一定关系,不过这种影响力的大小远小于由关注关系产生的影响力大小.此外,由属性产生的新关系同样会作用于影响力,本文假定其大小介于前两者之间.子属性空间包含的属性数目越多,则A与B拥有相同属性值就越不可能是偶然发生的,由属性产生的影响力就越大.类似的,在子属性空间下,拥有相同属性值的节点越多,则该子属性空间越有可能与社区特征相关,由此产生的影响力也越大.本文进行了大量的预实验,试图找到最能体现节点间关系的影响力模型.由于篇幅的限制,本文不对建立影响力模型过程中的相关预实验作展开说明.

Fig.4 Influence of outbound link,inbound link and attribute图4 出链、入链、属性与影响力的关系

根据预实验的结果,本文使用了以自然常数e为底的指数函数来描述的变化,它们的计算公式分别为公式(3)和公式(4),其中,αout和αin分别为出链和入链系数,用于控制函数的收敛速度:

得到影响力矩阵后,按公式(6)将矩阵每一行归一化,即得到转移概率矩阵P=(pij)N×N,pij为光标从节点vi向节点vj转移的概率:

在现实世界中,无论是蚁群还是Reddit的兴趣组,社区中的成员都并非完全平等,而是存在金字塔式的成员结构.受到社区中不平等现象的启发,为了评价节点在社区中是否处于金字塔顶端位置,本文引入了节点核心系数Core=(core1,core2,…,coreN)T,节点vi的核心系数corei越大,就越有可能成为社区的核心.现在介绍节点核心系数的计算方法.假设一个光标依次从网络中各个节点出发,按照P中的转移概率随机选择下一次转移的目标节点,每次出发后共转移2次,取最后所在节点为终点.每个节点的核心系数corei即是该节点为终点节点的次数期望.同时,与一些经典的基于random walk的方法一样,本文设定光标在每次转移后有back几率退回转移前的节点.那些经典的基于random walk的方法加入参数back通常是为了避免光标的转移在进入某些特殊路径后陷入死循环,但本文提出方法的转移次数固定且较小,几乎不受这些特殊路径的影响,加入参数back是为了能更好地模拟数据的传播.设想某人在浏览网络论坛时常常会因为对当前页面的内容不感兴趣而回退到上一级页面,而类似的回退操作在其他场景中也时有发生,本文加入的参数back即蕴含了这类回退操作的含义.

表2为当back=20%时,图3(a)中节点的核心系数.可以看出,处于社区中心位置的节点往往具有非常高的核心系数,这与社区中的金字塔结构也是相对应的.

在核心系数的基础上,本文设计了一种不需要预先指定社区数目的聚类方法,在网络中,每个节点都会按照该方法确定其聚类方向并和对应的节点聚合到一起.

节点的聚类方向Dir=(dir1,dir2,…,dirN)T由转移概率和核心系数共同决定,若pij为转移概率矩阵P第i行的唯一最大值,则节点vi的聚类方向为diri=j;若等于最大值的元素有多个,则取其中核心系数最大的作为聚类方向.

Table 2 Sample of core index表2 节点核心系数示例

构建一个将原网络中边的信息全部去除后的新网络,再按照下面的步骤添加边.

(1) 从节点序列中取出核心系数最大的节点vi,若vi未与任何边相连,则将该节点作为新社区的中心,并将其聚类方向记为空;

(2) 扫描Dir,若有节点vj未与任何边相连且聚类方向dirj=i,则建立一条由节点vj指向节点vi的有向边;

(3) 重复上述步骤,直到没有度为0的节点.

这样就得到了初始社区,下面再继续进行边缘修剪工作.

(1) 对于网络中的每一个节点,计算其所属社区中它的邻接节点的核心系数之和,再计算其他社区中它的邻接节点的核心系数之和,并将最大的核心系数之和对应的社区标记为节点新的所属社区,但暂时不将节点划入到新的社区当中;

(2) 在得到所有节点对应的新社区后,将所有节点划入新社区当中,若有节点的所属社区发生了改变,则重复(1)的工作,否则停止.

图5描述了图3(a)网络的社区发现过程.在新的网络中,任意条边两端的节点都属于同一社区.

Fig.5 Example of community partitioning process图5 社区划分过程示例

3 实验分析

本节通过在多个社会网络数据集上的实验来验证CDATP算法的有效性.第3.1节为实验准备部分,介绍了实验中使用的各类型的数据集、对比算法、CDATP的参数设置和实验结果评价标准.本文将实验按照使用到的数据集类型分为两部分,其中,基于无向网络的实验将在第3.2节中详细介绍,基于有向网络的实验将在第3.3节中详细介绍.

3.1 实验准备

在第3.2节基于无向网络的实验中,本文共使用了Karate[29],Dolphins[30],PolBooks[31],PolBlogs[32]这4个带基准的真实网络数据集(http://networkdata.ics.uci.edu/),表 3介绍了这些数据集的相关特征信息.实验选择ISCD+,ROCONA[33],InfoMap和FastQ算法作为对比算法.其中,ROCONA算法是基于信息粒度观点的最新社区发现算法,通过节点之间的关联度来构建社区.ROCONA算法通过与其他对比算法不同的视角来发现网络中的社区,且有较好的表现,因此本文也将其作为对比算法.

Table 3 Datasets of undirected network表3 无向网络数据集

在第3.3节基于有向网络的实验中,本文使用了有向版本的PolBlogs数据集和LFR基准网络[26].构造LFR基准网络使用的参数见表4,其中:N表示节点总数;μ表示社区间边数与内部边数的比值,μ的值越大,则社区结构越模糊;k表示社区内平均节点度;maxk表示社区内最大节点度;t1表示度序列的负指数;t2表示社区规模分布的负指数;mins表示社区节点数下限;maxs表示社区节点数上限.对于μ和N以外的参数,本文使用了文献[26]中的推荐取值.另外,本文参考了现有工作中对参数μ和N的设置[27],对于每一种μ和N的组合(对应不同环境下的网络)都生成5个网络,累计起来一共是120个人工网络.实验选择ConClus,OSLOM和LP作为对比算法.

Table 4 Parameters of LFR表4 LFR参数

在第3.2节和第3.3节中所使用的数据集均是带有基准信息的,因此本文使用NMI[34]评价实验结果.NMI=1时,说明实验结果与基准信息完全一样.NMI的值越大,说明社区划分的准确度越高.公式(7)是NMI的计算公式:

表5中介绍了CDATP的参数设置.在预实验中,本文发现:在较小规模(包含的节点数小于5 000)的网络中,与force相关的3个收敛因子取表5给出的预设值时准确度较高,且在预设值附近的小范围变动对社区划分的准确度影响非常小.受篇幅限制,本文在后面的实验中对收敛因子的取值不作展开讨论.参数back对实验的准确度有一定影响,在第3.2节和第3.3节中,本文针对不同的back取值进行了实验并对实验结果进行了比较.

Table 5 Parameters of CDATP表5 CDATP参数

3.2 基于无向网络的CDATP有效性验证

Karate数据集是Zachary对一个美国大学空手道俱乐部进行了2年观察而构建出的一个社会网络,它被广泛应用于社区检测方法的测试.网络中的节点表示俱乐部中的成员,而边表示成员之间的朋友关系.由于俱乐部中一名管理人员和一名教练的矛盾,导致俱乐部分裂成了两个派系.图6描述了该网络的拓扑结构,节点的颜色对应基准信息中的两个社区.紫色虚线表示CDATP初始社区划分,红色虚线表示边缘修剪引发的节点转移.

Fig.6 Karate network and community division result of CDATP图6 Karate网络及CDATP的社区划分

图7是不同back取值下各节点Core的平均值,可以观察到,节点1和节点34的Core总是最大或第二大的.而在现实世界中,节点1和节点34分别对应两个派系的领导[29],因此他们处于社区的核心位置,所以对应的Core才会较大.CDATP的节点对社区重要程度的评价方法能很好地适应真实网络条件.

Fig.7 Core index of nodes in Karate network图7 Karate中各节点的Core

Dolphins数据集共包含62个节点和159条无向边.网络中的每个节点代表一只宽吻海豚,被每条边连接起来的两节点对应的海豚间有频繁的互动.如图8所示,网络中原本有两个社区,以节点的颜色作为区分,绿色虚线是CDATP的初始社区划分,紫色虚线表示边缘修剪引发的节点转移.

当网络按照标记被划分为两个社区时,模块度Q=0.396,并未达到最大值,因此,以模块度为基础的算法会继续让社区分裂,难以找到正确的社区数目.如图8所示:当back=0.1时,当初始聚类结束后,只有节点“DN63”和“Oscar”被划分到了错误的社区,此时的NMI值为0.780 3.以“DN63”为例,它同时和“Upbang”“SN9”这两个核心系数较大的节点相连,而“SN9”的核心系数为1.356 8,略大于“Upbang”的1.308 7,所以“DN63”在聚类初始化时选择了错误的聚类方向,但是在边缘修剪过程中,由于左边社区对“DN63”有更大的吸引力,所以“DN63”转移到了左边的也即正确的社区中.

Fig.8 Dolphins network and community division result of CDATP图8 Dolphins网络及CDATP的社区划分

PolBooks数据集中的每个节点都代表一本美国的政治类书籍,如果有两本书被同时从Amazon.com买走,则对应的两个节点间会有边相连.书的类型按政治倾向分为“左派”“右派”和“中立派”这3类,其中,“中立派”数量最少.

CDATP的社区划分结果以紫色虚线形式在图9中标出,橙色代表“右派”,绿色代表“左派”,浅蓝色代表“中立派”,红色虚线表示边缘修剪引发的节点转移.CDATP识别出了两个最大的社区,并且只有很少量“保守派”节点被划分错误,但CDATP没有识别出包含节点数量最少的“中立派”社区,而是将其分散到了另外两个大的社区当中,这是由于“中立派”书籍总是与其他类型的书籍被一起购买,而不同“中立派”书籍间联系又比较少导致的.

PolBlogs网络是围绕2004年美国总统大选时的政治类型博客建立的,其中的每个节点代表一个博客,按政治倾向分为“左派”和“右派”,节点间的边代表博客间的超链接,与对比算法一样,CDATP将其作为无向边处理.由于节点数目太多,在图10中使用了超节点来表示社区,其中,浅蓝色代表“左派”,深蓝色代表“右派”,其大小和包含节点的数目成正比,虚线上标的数字为边缘修剪时的转移节点数,而孤立节点未在图中标出.从图中可以看到,使用CDATP算法划分社区后,只有少量的节点被错误划分.

如图11所示,本文在实验中测试了不同back值的条件下,CDATP聚类初始化和边缘修剪完成后的聚类效果.由于PolBlogs数据集中有266个节点未与其他节点产生联系,所以理论上最大NMI为0.666 3.可以看出,除了在PolBooks数据集中部分情况下,边缘修剪后导致NMI有小幅度下降,大多数情景中,边缘修剪都能使NMI有一个不错的提升.在Dolphins网络中,当back超过0.1时,NMI出现了下降.这是因为此时检测到的社区数由2变成了3,原来的两个社区中较大的一个出现了分裂,而在其他情况下,算法准确度对back的变化并不敏感,边缘修剪步骤很好地提升了初始社区的质量.

图12是各种算法的实验结果对比.Karate和Dolphins是两个典型的基准社区结构对应较低质量指标的例子.Karate网络和Dolphins网络的基准社区数量均为2,且当它们的模块度达到最大值时,都会被划分为4个社区,对应的NMI较低,因此,基于优化社区质量指标的社区发现算法在这样的真实网络上表现不佳.并且在Karate数据集中还存在着“双峰结构”[35],当模块度第1次到达极大值时,对应的社区划分质量非常低,这也导致了一些基于社区质量指标的社区发现算法无法适应这类网络.ISCD+在Karate网络上的NMI虽然也达到了1,但需要通过大量的准备实验和专家知识来设定社区数量,实用性较弱.而CDATP是参考事件传播规律设计的,对真实网络的适应性更强,因此表现较好.

在PolBooks数据集中,由于“中立派”书籍总是和其他类型书籍被一起购买,所以“中立派”社区内部边的数目明显小于与其他社区之间边的数目,社区结构非常松散.CDATP在该数据集上划分正确的节点数目最多,但由于没有将“中立派”单独划分为一个社区,所以NMI略低于ROCONA.PolBlogs数据集描述的网络是具有方向性的,但基于无向网络的社区发现算法直接将其作为无向网络处理,所以各算法在该数据集上的表现均不是太好.这说明对于有向网络,当忽略掉边的方向性后,将丢失掉网络中一些重要的信息.

Fig.10 PolBlogs network and community division result of CDATP图10 PolBlogs网络及CDATP的社区划分

Fig.11 Relation of NMI and back index图11 NMI与back 的关系

Fig.12 NMI comparison on real world undirected datasets图12 社区划分结果NMI对比

3.3 基于有向网络的CDATP有效性验证

有向版本的PolBlogs描述了边的方向.与文献[27]一样,首先将网络中的266个孤立节点除去.图13展示了各算法实验结果对比.算法ConClus,OSLOM和LP的NMI分别为0.678 9,0.572 1和0.385 3,均低于CDATP的NMI.

Fig.13 Comparison of NMI on PolBlogs network图13 PolBlogs网络社区划分NMI对比

在源数据中,每个博客都是从博客检索网站得到的.这些博客检索网站包括Blogarama,LeftyDirectory等,一共有6个.如图14所示:若将每个博客的检索源作为属性构造属性增强图,其聚类结果的NMI比未使用属性时提高了9.8%,说明了属性增强网络在提高社区划分准确度上的有效性,但同时也应注意到,准确度的提升并不是非常大.

Fig.14 Influence of attribute enhancement network on results图14 属性增强网络对结果的影响

这种现象的发生有两个原因.

· 一是大多数博客的检索源都是Blogarama,而Blogarama并没有明显的政治倾向,其中包含的两种政治倾向的博客数量基本持平,所以不会对结果造成什么影响;

· 二是因为某一些检索源虽然有非常明确的政治倾向,如LeftyDirectory中基本全是“左派”博客,但对应这些检索源的博客数量又相对较少,所以只能使结果的NMI有小幅度的上升.

图15介绍了在不同参数的人工网络中各算法的表现.如图所示,ConClus,OSLOM和LP的准确度对数据集规模比较敏感.当数据集规模增大时,上述算法划分社区的准确度会有小幅提升.而CDATP的准确度几乎不受数据集规模的影响,在各种条件下都有较好的表现.由此可以看出,CDATP在人工构造的网络中同样有很好的表现且适应性较强.