社会网络顶点间相似性度量及其应用*

陈 晓，郭景峰，张春英

1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004

2.华北理工大学 迁安学院，河北 迁安 064400

3.河北省计算机虚拟技术与系统集成重点实验室，河北 秦皇岛 066004

4.华北理工大学 理学院，河北 唐山 063009

社会网络顶点间相似性度量及其应用*

陈 晓1,2,3，郭景峰1,3+，张春英4

1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004

2.华北理工大学 迁安学院，河北 迁安 064400

3.河北省计算机虚拟技术与系统集成重点实验室，河北 秦皇岛 066004

4.华北理工大学 理学院，河北 唐山 063009

Abstract:Set pair analysis as the mathematical theory of dealing with the interaction system of certainty and uncertainty,can be used to deal with the complexity social network of uncertain relationship.Firstly,based on the application of set pair analysis theory,this paper takes social network as an identical-different-contrary system(certain and uncertain system).Based on set pair connection degree to descript the identical,different and contrary relations between vertices,considering the contribution of local features and the topological structure to the vertex similarity,this paper defines the similarity between vertices based on the relation connection degree taking into account weightand clustering coefficient.The measurement can better describe network structure characteristics,overcome the underestimating for some similarity between vertices based on traditional local structures,and reduce the computational complexity of global similarity indices.Secondly,in order to utilize the similarity indices to community discovering,combined with agglomerative hierarchical clustering algorithm,it is applicable to detect community structures in complex networks with any object that has similarity measurement.Finally,through the experiment of community mining on the social network,and compared with the typical algorithms of community discovering,the experimental results verify the correctness and effectiveness of the similarity measurement.

Key words:social network;similarity;set pair;identical-different-contrary relations;community discovering

集对分析作为处理系统确定性与不确定性相互作用的数学理论，可用来处理存在不确定关系的复杂社会网络。首先，应用集对分析理论，将社会网络作为一个同异反系统（确定不确定系统），采用集对联系度刻画顶点间的同异反关系，综合考虑顶点的局部特征和拓扑结构对顶点相似性的贡献，提出加权聚集系数联系度的顶点间相似性度量方法。该度量方法可以更好地刻画网络结构特征，克服传统局部相似性度量指标对某些顶点间相似性值的低估，降低全局相似性度量指标的计算复杂度。其次，为了将该相似性度量指标应用于社区发现，与凝聚型层次聚类算法相结合，使其适用于具有相似性度量对象的复杂网络社区发现问题。最后，在社会网络上进行社区挖掘实验，并与经典社区发现算法进行比较，实验结果表明了该相似性度量指标的正确性及有效性。

社会网络；相似性；集对；同异反关系；社区发现

1 引言

随着社会网络分析在各领域的广泛应用，社会网络分析技术[1]受到国内外学者的广泛关注，已成为当前的研究热点。社会网络分析技术以图论为基础，通常将社会网络表示为一个二元组G=(V,E)，其中顶点集V代表网络中的个体，边集E代表网络中个体间的联系。顶点间相似性的度量方法作为社会网络分析的基础，对社区发现、社区演化和链接预测具有重要的理论意义实用价值。

现有顶点间相似性[2]的计算方法主要分为3类：（1）基于网络全局信息的相似性度量指标，如Katz指标[3]、LHN（Leicht-Holme-Newman）指标[4]、ACT（average commute time）指标[5-6]、RWR（random walk with restart）指标[7]等；（2）基于顶点公共邻居的局部相似性度量指标，如 CN（common neighbor）指标[8]、Salton（又称为Cosine）指标[9]、Sφrensen指标[9]、Jaccard指标[10]等；（3）介于全局和局部之间的半局部相似性度量指标，如LP（local path）指标[11]、LRW（local random walk）指标[12]、RALP（resource allocation along local path）[13]等。其中，全局相似性度量指标需要考虑网络的整体结构关系，通常利用网络的邻接矩阵计算逆矩阵和矩阵的特征根，或通过遍历顶点间路径度量相似性等。全局性方法虽然拥有相对较高的精度，但却具有较高的时间和空间复杂度，不适宜较大规模的网络。文献[14]的研究表明，当路径长度从2增加到5时，可以增大相似性的精度，而当路径长度大于5时，相似性精度变化很小。局部相似性度量指标由于仅考虑顶点的最近邻，具有较低的时间复杂度，却低估了直接连接顶点间和通过关联路径连接的顶点间的相似性。因此，仅利用网络个体间相同的确定性评估顶点间的相似性，不能全面体现网络中个体间的关系。如何基于网络中的确定与不确定关系，更准确地定义顶点间的相似性是本文的研究重点。

集对分析[15]（set pair analysis，SPA）理论是我国学者赵克勤于l989年提出的理论方法，是一种用联系度统一处理模糊、随机和信息不完全所致不确定性系统的理论和方法，在科学技术和社会经济的许多领域得到了广泛应用。2011年，文献[16]首先将集对理论应用到社会网络分析中，提出了集对社交网络分析模型及其性质，为基于集对理论的社会网络分析研究拉开了序幕。2013年，文献[17-18]基于集对理论和共同邻居提出了一种新的顶点间相似性度量方法，并根据社会网络特性分别实现了静态和动态α关系社区的挖掘算法，证明了α关系社区的挖掘更能体现社区存在的动态性。2014年，文献[19]基于属性图提出了集对社交网络实体相似性的计算方法，并基于集对态势实现了社区发现。然而，现有基于集对的顶点间相似性度量方法，仅考虑了网络中不确定的共同邻居属性数量对社区形成及网络分析的影响，忽略了顶点间的拓扑结构、顶点的度等对顶点间相似性的影响。

本文将无向无权无符号的社会网络作为研究对象，基于集对分析理论的思想，将社会网络作为一个同异反系统（确定不确定系统），在考虑顶点度和顶点间拓扑结构两个因素对顶点相似度的影响前提下，提出了一种新的顶点间相似性度量指标——加权聚集系数联系度。为了更深入地验证本文提出的顶点间相似性度量方法，将该相似性指标应用到社会网络社区发现中，通过实验结果进一步验证顶点间相似性度量指标的正确性及有效性。

本文主要贡献如下：

（1）提出加权聚集系数联系度的顶点间相似性度量方法。综合考虑网络局部关系（共同邻居等）和网络拓扑结构属性（聚集系数和顶点间路径等），采用联系度刻画影响顶点间相似性的顶点集合的同异反关系，提出加权聚集系数联系度的顶点间相似性度量方法。该方法根据宏观异（不确定）关系F和微观异（不确定）关系i转化为同关系S时对顶点间相似性的贡献，考虑顶点间连接密度影响，采用顶点的聚集系数作为i的取值方法；根据顶点度和顶点间路径对相似性贡献的影响，为同异反关系进行加权。该方法既避免了从单一数量上考虑顶点间同异反关系的不全面性，又避免了计算顶点间路径的复杂性，不仅更好地体现网络拓扑结构特点，而且可以提高相似性指标的精确性。

（2）提出顶点间相似性优先凝聚和社区间均值凝聚相结合的层次聚类算法VSFCM（vertices similarity first and communities mean）。传统基于平均距离的凝聚型层次聚类算法有大量更新平均距离的操作并且有社区聚类不合理现象。为了确保相似性大的顶点在同一社区中，相似性小的顶点在不同社区中，提出VSFCM算法，即将相似性大的顶点对优先合并为小社区，然后再进行社区间的合并，有效避免了频繁更新操作，提高了算法效率。

本文组织结构如下：第2章介绍顶点间相似性度量指标的研究现状；第3章讨论基于联系度的顶点间相似性模型及定理；第4章对社区发现算法进行描述；第5章通过实验验证顶点间相似性度量指标的正确性和合理性；最后总结全文，并对下一步工作进行展望。

2 相关工作及问题定义

现有多种计算顶点间相似性的方法，其中基于邻接点（局部）的相似性方法具有较低的时间复杂度，文献[2]研究结果表明，指标RA（resource allocation）的计算精度最佳，CN次之；基于路径（全局）的相似性方法具有较高的时间复杂度，但具有较好的计算精度，如Katz；基于联系度的方法是一种介于局部和全局之间的半全局方法，是借鉴同异反关系定义相似性的新方法。因此，主要介绍CN、RA、Katz和现有两种基于联系度的顶点间相似性定义方法。

2.1 基于邻接点（局部）的相似性方法

公共邻居CN指标[8]如式（1）所示：

资源配置RA指标[11]如式（2）所示：

2.2 基于路径（全局）的相似性方法

Katz指标[3]如式（3）所示：

通过实验证明β=0.000 5的实验效果较好[20]，并保证指标收敛于(I-βA)-1-I。

2.3 基于联系度的相似性方法

集对理论的基本定义和性质可以见文献[15]。

文献[17-18]首先将联系度应用于社会网络分析领域，以网络结构为基础，令顶点vk和vs为两个研究对象，将顶点间的邻接关系作为顶点属性，两个顶点的共有属性记为N，则顶点间相似性度量指标定义如下。

注：N(v)1表示顶点v的1级邻居；N(v)2表示顶点v的2级邻居，具体定义详见下节。

Fig.1 Instance networkA图1 实例网络A

3 基于联系度的顶点间相似性模型

基于联系度刻画顶点间相似性度量工作的重点是，如何定义影响顶点间相似度的顶点集合的同异反关系。为了更好地表达邻居顶点对顶点间相似性的影响，介绍相关定义如下。

3.1 相关定义

定义1（顶点邻居集）给定社会网络G=(V,E),∀vk∈V，vk的1级邻居集记为N(vk)1，如式（6）所示。

vk的2级邻居集记为N(vk)2，如式（7）所示。

定义2（顶点的共同邻居集）给定社会网络G=(V,E)，∀vk,vs,vq∈V，若vq∈N(vk)1⋂N(vs)1，则vq为vk和vs的共同1级邻居。vk和vs的共同1级邻居集记为CN(vk,vs)1，如式（8）所示。

同理vk和vs的共同2级邻居集记为CN(vk,vs)2,如式（9）所示。

同理vk和vs的共同1⋂2级邻居集记为CN(vk,vs)1⋂2,如式（10）所示。

同理vk和vs的共同2⋂1级邻居集记为CN(vk,vs)2⋂1,如式（11）所示。

vk和vs的邻居集关系如图2所示。其中，代表CN(vk,vs)1，代表CN(vk,vs)1⋂2或CN(vk,vs)2⋂1，代表CN(vk,vs)2。

Fig.2 Neighbors set relation betweenvkandvs图2 顶点vk和vs的邻居集关系

3.2 顶点间相似性模型

在基于网络拓扑结构的顶点间相似性度量方法中，如果两个顶点间共同邻居和短路径越多，可能使得两个顶点的相似性越强。基于这一思想，将两个顶点的共同1级邻居作为相同属性，将1⋂2、2⋂1和2级邻居作为宏观层次上的不确定属性，可以更好地刻画不确定属性对相同的确定属性的影响。具体顶点间同异反关系定义如下。

定义3（顶点间同异反关系）给定社会网络G=(V,E),∀vk,vs∈V，相同属性为vk和vs的共同1级邻居，即S=|CN(vk,vs)1|；相异属性为vk和vs的共同1⋂2、2⋂1和2级邻居，即F=|CN(vk,vs)1⋂2|+|CN(vk,vs)2⋂1|+|CN(vk,vs)2|;其余为vk和vs的相反属性，即P=N-S-F，其中，N=|V|。

然而，如果仅从顶点间同异反关系的个数方面刻画顶点间的相似性，将存在明显的局限性和不合理性。因此，为了更准确地刻画顶点间的相似性，本文综合考虑网络密度和顶点度等特征，对各属性关系进行加权，提出基于加权聚集系数的顶点间联系度，具体定义如下。

定义4（相似性指标WCCD（weighted clustering coefficient connection degree））给定社会网络G=(V,E),∀vk,vs∈V，基于加权聚集系数的顶点间联系度SWCCDks如式（12）所示。

其中，N、S、F、P的含义如定义3所示，(1)1×S、(1)1×F和(1)1×P分别代表相同、相异和相反属性的行向量，向量值均为1；w(vi)为顶点对应的权值；(i(vi))F×1向量值为相异属性顶点vi对应的差异i值，j表示相反属性的标记作用。

式（12）中存在3个参数(i(vi))F×1、w(vi)和j，这3个参数如何取值对计算顶点间联系度起着至关重要的影响，下面主要介绍这3个参数的取值方法。

3.2.1i的取值方法

基于集对理论思想，i作为微观层次上的差异标记，如何取值对不确定属性如何向确定属性转换有着至关重要的影响。现有基于灰度[21]等的取值方法不能直接应用于社会网络中顶点间相似性的计算中，需要重新定义差异标记i的取值方法。

在图2所示的网络中，v2∈CN(v1,v7)1⋂2，v5∈CN(v1,v7)2⋂1,由于顶点v2和v5的不同，使得它们转化为CN(v1,v7)1的可能性也是不同的。考虑到不同的不确定属性向确定属性转换的不同可能性，针对不同属性将i的取值转化为一个向量组；考虑到网络的密度结构特性，采用顶点的聚集系数[22]值来量化该不确定属性的i值。由于不确定属性包括顶点对的共同1⋂2、2⋂1和2级邻居，分别考虑上述3种情况转换为共同1级邻居的可能性来量化i值，具体计算方法如下。

3.2.2w的取值方法

在图1所示的网络中，v2,v4∈CN(v1,v3)1，由于v2和v4度的值不同，可见它们对v1和v3联系度的贡献也不尽相同。基于“顶点度越小对联系度的贡献越大，顶点度越大对联系度的贡献越小”的启发式思想，以及路径的可达性以及转移概率来描述顶点对联系度的贡献。本文中顶点类型主要分为直接相连，共同1、1⋂2、2⋂1和2级邻居顶点等，下面分别介绍以上5种类型的顶点权值w(vi)的定义方法，其中d(vi)表示顶点vi的度。

3.2.3j的取值方法

在社区发现算法中，由于期望将相似性大的顶点划分到同一社区，则更希望考虑顶点间相同属性，以及不确定性属性转向相同属性的程度，对顶点间相似性的贡献值。因此，令式（12）中j=0，忽略对立属性的影响，认为不确定属性全部转向相同属性。

4 社会网络的社区发现算法

社区发现的主要目的是将社会网络G=(V,E)划分为K个互不相交的子社区，使得，且Gki⋂Gkj=∅(i≠j)，保证同一社区内顶点间的关系紧密，不同社区关系稀疏。因此，基于相似性的社区发现问题就可以转化为基于相似性的凝聚层次聚类问题。为了实现社区发现，首先给出社区间相似性的计算方法。

定义5（社区间相似性）设CK=(VK,EK)和CS=(VS,ES)为社会网络中的两个社区，则社区CK和CS间的相似性表示社区间顶点对相似性的均值，记为Sim(CK,CS)，如式（13）所示。

经典凝聚层次聚类AGNES（agglomerative nesting）算法[23]在进行社区合并时，首先计算顶点间的相似性值Sim(vk,vs)，其次选取max{Sim(vk,vs)}，然后将顶点vk和vs合并，记为Cnew。该方法在每次合并后，均需要重新计算Cnew与其他顶点或社区的相似性值，因此有大量Sim(Cnew,vi)值的更新操作。Sim(Cnew,vi)实质上是计算社区间顶点对的相似性均值，由于大社区中某顶点与独立社区中顶点相似性较大，容易导致Sim(Cnew,vi)≥Sim(vj,vi)，即均值降低vi对大社区中相对距离较远顶点（即相似性较低的顶点）的敏感性，导致vi不断聚合到大社区中的现象，而不是优先合并相似性大的vi与vj。为了保证两两相似性大的顶点优先聚合，另一种方法实质上是比较每个顶点对的相似性度量是否均为最大值。即∀vk∈V，当且仅当Sim(vj,vi)≥Sim(vj,vk), 且Sim(vj,vi)≥Sim(vi,vk)，将vi与vj合并，否则不合并。由于聚合条件严格，很难形成大规模社区。基于上述两个方法的优缺点，考虑将两种方法相结合。即将相似性值比较法融入到AGNES算法中，以减少社区间相似性值的计算次数，并避免顶点不断聚合到大社区的现象；然后再将初步合并的社区按照AGNES算法进行聚合，以避免比较法中无法形成大规模社区的现象。因此，基于加权聚集系数联系度，提出一种新的层次聚类算法VSFCM。具体算法描述如下。

算法1 VSFCM

输入：社会网络G=(V,E)的邻接矩阵A

输出：层次聚类树

算法VSFCM主要分为三步：计算顶点间相似性，初始社区合并，非独立社区合并。第一步：计算vk和vs间的相似性值SWCCDks。设社会网络中顶点数N=|V|，基于联系度思想的计算路径长度为1至4步，路径长度为5的顶点间相似性值为0。因此，仅需计算和存储任意顶点vk与其4步内邻居的相似性值。令任意顶点vk的4步内邻居集个数为L，则空间复杂度为O(NL)。对于大部分实际网络中，顶点的4级内邻居集个数L的取值远小于N，且L值不会随着网络规模的增长而快速增长，因此，适用于大规模网络顶点间相似性的存储。第二步：初始独立社区合并，如代码第3～13行。此步选取最大值的顶点对进行合并，因此，时间复杂度为O(NL)。第三步：非独立社区合并，如代码第14～18行。设有K个社区，K远小于N，时间复杂度为O(K2)。社区发现算法VSFCM最终的时间复杂度为O(NL+K2)。

VSFCM算法是对经典层次聚类算法的改进，主要区别是，在聚类初期，仅通过判断顶点间相似度先生成小规模的初始社区，并不进行新社区与原有社区间值的更新操作；在聚类期间，对初始社区进行合并，最终生成层次聚类树。尽管合并顺序不同，但VSFCM算法保证了其产生的结果和经典方法是相同的。

5 实验结果与分析

实验的硬件环境是Intel®CoreTMDuo E7500双核的CPU，内存4 GB；软件环境是Windows 7系统，Matlab R2012a。

主要从两方面进行实验验证：（1）与现有顶点间相似性度量指标进行比较，验证WCCD度量指标的合理性和正确性；（2）通过与经典社区发现方法进行比较，验证WCCD度量指标在解决社区发现问题时的正确性和有效性。其中，利用模块度函数评价社区结构的优劣。

模块度函数（Q函数）是Newman[24]提出的衡量网络划分质量的标准。Q函数定义如下：

其中，K表示社区个数；m表示网络连接总数；ms表示社区s中的连接总数；ds表示社区s中顶点度之和。Q函数的取值范围是0～1之间。通常认为最大Q函数值对应的社区划分为网络社区的最佳划分；Q函数值越接近于1，说明网络的社区结构越明显。在实际的网络中，Q函数值通常在0.3～0.7之间。文献[25]指出模块度Q函数存在分辨率极限问题[26]，但当前未见其他更合适的评价指标，模块度Q函数仍作为研究者们广泛应用于评价社区质量的标准之一[27-28]。

5.1 相似性度量指标的实验分析

为了验证采用联系度综合刻画网络局部关系和网络拓扑结构的顶点间相似性度量指标WCCD，比单一考虑局部关系、路径及同异反数量的相似性度量指标具有更高的准确性，本文选取了经典的最具代表性的CN、RA和Katz相似性度量指标，选取了现有基于联系度的SPCD1和SPCD2相似性度量指标，与本文提出的WCCD相似性度量指标进行比较。在模拟网络[29]、空手道俱乐部Karate网络[30]和Dolphin网络[30]3种网络中，如图3所示，应用VSFCM算法进行社区挖掘，通过社区的划分效果对6种顶点间相似性指标定义的合理性和正确性进行验证。应用6种顶点间相似性度量指标，利用VSFCM算法进行层次聚类，选取模块度最大的层作为社区划分结果，各度量指标的网络最大模块度值、社区个数对比情况如表1所示。

Table 1 Experimental results of 6 indicators表1 6种指标的实验结果

Fig.3 Social network图3 社会网络图

在模拟网络中，不同社区个数对应的模块度值的大小变化曲线如图4所示。因为各度量指标在VSFCM算法中形成的初始社区个数不同，所以各度量指标的模块度曲线在图6中的长短不同。在模拟网络中，采用CN指标的网络最大模块度为0.624，划分为6个社区，分别为（16，18，10，11，17，22）、（26，27，28，32，36，35，33）、（12，23，19，20，24）、（25，34，30，29，31）、（1，3，4，2，6，7，5）和（8，9，21，13，14，15）；采用RA指标的网络最大模块度为0.589，划分为 6 个社区，分别为（3，1，4）、（18，16，11，10，17）、（34，25，30，31，29）、（20，19，24，23，12）、（33，32，36，35，27，22，28，26）和（6，2，14，5，7，13，15，21，8，9）；采用Katz指标的网络最大模块度为0.637，划分为6个社区，分别为（1，2，3，4，6，7，5）、（8，13，14，21，9，15）、（16，18，10，11，17）、（20，23，19，24，12）、（30，31，34，29，25）和（35，36，32，33，26，27，22，28）；采用SPCD1指标的网络最大模块度为0.603，划分为7个社区，分别为（16，18，17，10，11）、（35，36，32，33，26，27，22，28）、（30，31，29，34，25）、（1，3，4，2，6，7，5）、（8，13，14，21）、（9，15）和（12，20，23，24，19）；采用SPCD2指标的网络最大模块度为0.596，划分为5个社区，分别为（5，7，4，2，6，1，3）、（8，9，21，13，14，15）、（16，18，10，11，17，19，20，12，23）、（22，27，33，26，28，32，35，36）和（24，25，34，29，31，30）；采用WCCD指标的网络最大模块度为0.637，划分为6个社区，分别为（1，2，3，4，6，7，5）、（8，13，14，21，9，15）、（16，18，10，11，17）、（20，23，19，24，12）、（30，31，34，29，25）和（35，36，32，33，26，27，22，28）。由此可见，本文WCCD指标与全局性Katz指标具有最大的网络模块度值，优于其他4种局部度量指标；在不同社区划分层次中，都取得了较大的模块度值，并实现了社区的正确划分。

Fig.4 Experimental results of 6 indicators in simulation network图4 6种指标在模拟网络中的实验结果

同样，采用6种相似性度量指标，在Karate网络和Dolphin网络中进行社区划分，不同社区个数对应的模块度值的大小变化曲线如图5、图6所示；各度量指标的网络最大模块度值、社区个数对比情况如表1所示。通过对模块度值大小的比较，采用本文WCCD度量指标进行社区划分，均可得到最大的模块度值；在不同的社区划分层次中，也取得了较大的模块度值，较好地体现了社区划分结果。由此可见，WCCD指标接近甚至优于全局性Katz度量指标，明显优于其他局部相似性度量指标，合理地刻画了网络中顶点间的关系值。

Fig.5 Experimental results of 6 indicators in Karate network图5 6种指标在Karate网络中的实验结果

Fig.6 Experimental results of 6 indicators in Dolphin network图6 6种指标在Dolphin网络中的实验结果

5.2 社区发现实验分析

现有多种社区发现算法，主要分为基于分裂的方法，如GN算法[31]；基于模块度的方法，如CNM算法[32]；基于标签传播的方法，如LP（label propagation）算法[33]；基于谱聚类的方法，如SC（spectral clustering）[34]等经典社区发现算法[35]。为了验证基于WCCD相似性度量指标在VSFCM算法下社区划分结构的优劣，在10种具有代表性的真实网络中，与上述4种算法进行比较实验。真实网络包括：空手道俱乐部Karate网络[30]、海豚Dolphin网络[30]、美国大学足球联赛FB网络[30]、爵士音乐家合作Jazz网络[36]、线虫神经Neural网络[30]、美国航空 USAir网络[36]、电子邮件 Email网络[30]、科学家合作NS网络[30]、美国大选政治博客PB网络[30]、美国电力PG网络[30]。本文将全部数据集视为无向无权的二元网络。研究表明，很多真实网络中的顶点具有模块性特征[37]，且真实网络的社区发现比模拟网络更具挑战，不能事先预知其社区结构，因此只能采用模块度进行比较。实验结果如表2所示。

在表2中，第1列为真实网络列表，第2列和第3列为网络的基本统计数据（顶点数和边数），第4至13列为5种社区发现算法，对每种算法统计了社区发现的最大模块度值和社区数目。例如，在Karate网络中，采用GN算法得出的最大模块度值为0.401，划分的社区数为5。考虑到具有较高复杂度的GN算法具有较好的社区划分结果，因此在表2中取每个网络模块度值的前两位，其中加粗数据表示最大值，加粗加下划线表示次大值。由表2可见，从模块度值角度比较，采用WCCD度量指标的VSFCM算法取得了7次领先，而采用全局性度量指标的GN算法取得了6次领先，尤其是在USAir网络的社区发现中，GN算法和LP算法给出了接近0的模块度值，而VSFCM算法仍取得了较好的社区结构效果；考虑模块度增量作为社区划分标准的CNM算法取得了5次领先，相对较好，而LP算法与SC算法表现较差，LP算法仅取得了1次领先，SC算法一次领先也没有。从社区划分数目角度比较，GN算法倾向于给出较多的社区划分数目，例如PB网络分为205个社区，显著高于其他算法；此外LP和VSFCM为3个社区，较为接近真实的社区数目，其余方法给出的社区数均为10个以上，显然相应的方法有过于拟合的倾向。

5种算法在数据集中的运行时间如图7所示。在图7中，横坐标表示顶点数及真实网络，纵坐标表示算法的运行时间。由图7可知，随着网络中顶点数和边数的增加，各个算法的运行时间显著增长。总体来看，贪婪的CNM算法和LP算法运行速度较快，比较适合处理大型网络。SC算法由于采用了ARPACK加速特征根的计算方法，随着网络规模的增加，运行时间增加缓慢。但LP算法和SC算法获得的模块度值偏低，其速度的增加是以社区划分效果为代价的。消耗时间最多的是GN算法，该算法需要从全局角度计算边界数。VSFCM算法的运行效率明显优于GN算法，虽然逊于SC算法和LP算法，但社区划分效果明显优于SC算法和LP算法。

综上，与其他4种算法相比，采用WCCD度量指标的社区发现算法VSFCM均取得了较大社区模块度值，表明本文提出的WCCD相似性度量指标可以实现较好的社区划分结果。

Table 2 Experimental results of 5 community discovering algorithms表2 5个算法社区划分结果的比较

6 结束语

本文将社会网络定义为一个同异反系统，针对网络拓扑结构，基于联系度刻画分析了顶点间相似性，给出了基于加权聚集系数联系度的顶点间相似性模型的表示及计算方法；进一步给出了网络社区间相似性模型。为了进一步考察上述相似性度量指标的实际性能，将其应用于现有社会网络数据集中实现社区发现，实验结果显示，基于本文提出的顶点间相似性度量指标可以正确和有效地实现社区发现。如何刻画有向有权等更复杂网络中顶点间的相似性，以及如何研究网络动态演化是下一步的研究目标。

Fig.7 Comparison of vertices number and running time图7 顶点数与运行时间对比图

[1]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[2]Lv Linyuan,Zhou Tao.Link prediction in complex networks:a survey[J].Physica A Statistical Mechanics&Its Applications,2011,390(6):1150-1170.

[3]Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[4]Leicht E A,Holme P,Newman M E J.Vertex similarity in networks[J].Physical Review E,2006,73(2):026120.

[5]Fouss F,Pirotte A,Renders J,et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].IEEE Transactions on Knowledge&Data Engineering,2007,19(3):355-369.

[6]Göbel F,Jagers A A.Random walks on graphs[J].Stochastic Processes&TheirApplications,1974,2:311-336.

[7]Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks&ISDN Systems,1998:107-117.

[8]Lorrain F,White H C.Structural equivalence of individuals in social networks[J].Journal of Mathematical Sociology,1971,1(1):49-80.

[9]Salton G,McGill M J.Introduction to modern information retrieval[M].New York:McGraw-Hill,1983.

[10]Hamers L,Hemeryck Y,Herweyers G,et al.Similarity measures in scientometric research:the Jaccard index versus Salton's cosine formula[J].Information Processing&Management,1989,25(89):315-318.

[11]Zhou Tao,Lv Linyuan,Zhan Yicheng.Predicting missing links via local information[J].The European Physical Journal B:Condensed Matter and Complex Systems,2009,71(4):623-630.

[12]Liu Weiping,Lv Linyuan.Link prediction based on local random walk[J].Europhysics Letters,2010,89(5):58007-58012.

[13]Bai Meng.Link prediction of complex network:the algorithm based on structure similarity[D].Xiangtan:Xiangtan University,2011.

[14]Chiang K Y,Natarajan N,Tewari A,et al.Exploiting longer cycles for link prediction in signed networks[C]//Proceedings of the 20th Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28,2011.New York:ACM,2011:1157-1162.

[15]Zhao Keqin.Set pair analysis and its preliminary application[M].Hangzhou:Zhejiang Science and Technology Press,2000.

[16]Zhang Chunying,Liang Ruitao,Liu Lu.Set pair social network analysis is model and its application[J].Journal of Hebei Polytechnic University:Natural Science Edition,2011,33(3):99-103.

[17]Zhang Chunying,Guo Jingfeng.The α relation communities of set pair social networks and its dynamic mining algorithms[J].Chinese Journal of Computers,2013,36(8):1682-1692.

[18]Zhang Chunying.Research on modeling and situation analysis theory of social network based on attribute graph[D].Qinhuangdao:Yanshan University,2013.

[19]Zhang Chunying,Guo Jingfeng.The attribute graph model of social networks and its application[M].Beijing:Beijing University of Posts and Telecommunications Press,2014:186-198.

[20]Zhao Chanyuan.The research on link prediction method in social network[D].Harbin:Harbin Engineering University,2012.

[21]Li Tao,Fu Qiang,Ding Hong.Research for variation coefficient in set pair analysis based on correlation degree of grey theory[J].Journal of Heilongjiang Hydraulic Engineering,2010,37(1):97-99.

[22]Esley D,Kleinberg J.Networks,crowds,and markets[M].Cambridge:Cambridge University Press,2010:49-50.

[23]Han Jiawei,Kamber M.Data mining:concepts and techniques[M].San Francisco,USA:Morgan Kaufmann Publishers Inc,2011:457-470.

[24]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):292-313.

[25]Fortunato S,Barthélemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States ofAmerica,2007,104(1):36-41.

[26]Zhang Jiali.The problem of modularity and its algorithm research in community detection[D].Shanghai:East China Normal University,2015.

[27]Jiang Shengyi,Yang Bohong,Wang Lianxi.An adaptive dynamic community detection algorithm based on incremental spectral clustering[J].Acta Automatica Sinica,2015,41(12):2017-2025.

[28]Li Huijia,Li Huiying,Li Aihua.Analysis of multi-scale stability in community structure[J].Chinese Journal of Computers,2015,38(2):301-311.

[29]Bhatia M P S,Gaur P.Statistical approach for community mining in social networks[C]//Proceedings of the 2008 International Conference on Service Operations&Logistics,&Informatics,Beijing,Oct 12-15,2008.Piscataway,USA:IEEE,2008:207-211.

[30]Newman M.Network datasets[EB/OL].[2016-05-21].http://www-personal.umich.edu/～mejn/netdata/.

[31]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[32]Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.

[33]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.

[34]Newman M E J.Finding community structure using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.

[35]Jiang Shengyi,Yang Bohong,Li Minmin,et al.Overlapping community detection algorithm based on two-stage clustering[J].Pattern Recognition and Artificial Intelligence,2015,28(11):983-991.

[36]Batageli,Mrvar A.Pajek datasets[EB/OL].[2016-05-21].http://vlado.fmf.unilj.si/pub/networks/data/default.htm.

[37]Li Yafang,Jia Caiyan,Yu Jian.Survey on community detection algorithms using nonnegative matrix factorization model[J].Journal of Frontiers of Computer Science and Technology,2016,10(1):1-13.

附中文参考文献:

[13]白萌.复杂网络的链路预测:基于结构相似性的算法研究[D].湘潭:湘潭大学,2011.

[15]赵克勤.集对分析及其初步应用[M].杭州:浙江科学技术出版社,2000.

[16]张春英,梁瑞涛,刘璐.集对社会网络图分析模型及其应用[J].河北理工大学学报:自然科学版,2011,33(3):99-103.

[17]张春英,郭景峰.集对社会网络α关系社区及动态挖掘算法[J].计算机学报,2013,36(8):1682-1692.

[18]张春英.基于属性图的社交网络建模与态势分析理论研究[D].秦皇岛:燕山大学,2013.

[19]张春英,郭景峰.社交网络属性图模型与应用[M].北京:北京邮电大学出版社,2014:186-198.

[20]赵婵媛.一种社会网络链接预测算法研究[D].哈尔滨:哈尔滨工程大学,2012.

[21]李陶,付强,丁红.基于灰色关联度的集对分析差异系数研究[J].黑龙江水专学报,2010,37(1):97-99.

[26]张家利.社区发现的模块度问题及其算法研究[D].上海:华东师范大学,2015.

[27]蒋盛益,杨博泓,王连喜.一种基于增量式谱聚类的动态社区自适应发现算法[J].自动化学报,2015,41(12):2017-2025.

[28]李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-311.

[35]蒋盛益,杨博泓,李敏敏,等.基于二阶段聚类的重叠社区发现算法[J].模式识别与人工智能,2015,28(11):983-991.

[37]李亚芳,贾彩燕,于剑.应用非负矩阵分解模型的社区发现方法综述[J].计算机科学与探索,2016,10(1):1-13.

Measuring Similarity Between Vertices and ItsApplication in Social Network*

CHEN Xiao1,2,3,GUO Jingfeng1,3+,ZHANG Chunying4
1.College of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China
2.College of Qian'an,North China University of Science and Technology,Qian’an,Hebei 064400,China
3.The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province,Qinhuangdao,Hebei 066004,China
4.College of Science,North China University of Science and Technology,Tangshan,Hebei 063009,China

A

TP391

+Corresponding author:E-mail:jfguo@ysu.edu.cn

CHEN Xiao,GUO Jingfeng,ZHANG Chunying.Measuring similarity between vertices and its application in social network.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1629-1641.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1629-13

10.3778/j.issn.1673-9418.1607025

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant No.61472340(国家自然科学基金);the National Youth Science Foundation of China under Grant No.61602401(国家青年科学基金项目);the Natural Science Foundation of Hebei Province under Grant Nos.F2017209070,F2016209344(河北省自然科学基金).

Received 2016-07,Accepted 2016-12.

CNKI网络优先出版:2016-12-06,http://www.cnki.net/kcms/detail/11.5602.TP.20161206.1712.002.html

CHEN Xiao was born in 1983.She is a Ph.D.candidate at Yanshan University,a lecturer at North China University of Science and Technology,and the member of CCF.Her research interests include graph mining and social network analysis,etc.

陈晓（1983—），女，河北秦皇岛人，燕山大学博士研究生，华北理工大学讲师，CCF会员，主要研究领域为图挖掘，社会网络分析等。发表学术论文20余篇。

GUO Jingfeng was born in 1962.He received the Ph.D.degree from Yanshan University in 2002.Now he is a professor and Ph.D.supervisor at Yanshan University,and the senior member of CCF.His research interests include database theory and application,data mining and social network analysis,etc.

郭景峰（1962—），男，黑龙江哈尔滨人，2002年于燕山大学获得博士学位，现为燕山大学教授，CCF高级会员，主要研究领域为数据理论应用，数据挖掘，社会网络分析等。发表学术论文100余篇，主持国家自然科学基金项目2项，省级科研项目3项。

ZHANG Chunying was born in 1968.She received the Ph.D.degree from Yanshan University in 2013.Now she is a professor at North China University of Science and Technology,and the senior member of CCF.Her research interests include data mining and social network analysis,etc.

张春英（1968—），女，河北唐山人，2013年于燕山大学获得博士学位，现为华北理工大学教授，CCF高级会员，主要研究领域为数据挖掘，社会网络分析等。发表学术论文30余篇，主持省级科研项目1项。