种子节点非重叠社团挖掘算法研究

张晓芬，　封　筠，　贾宁宁

(石家庄铁道大学 信息科学与技术学院，河北 石家庄　050043)



种子节点非重叠社团挖掘算法研究

张晓芬，封筠，贾宁宁

(石家庄铁道大学 信息科学与技术学院，河北 石家庄050043)

提出一种新型的种子节点社团挖掘算法，首先，利用主成分分析技术由单一性节点重要性评价指标提取出综合性评价指标，挑选评价指标值最大的节点作为种子节点，对其进行广度优先搜索，指标值大的节点不断地影响指标值小的节点，得到种子节点所在的社团结构。然后，从已知社团结构外选取综合性评价指标值最大的节点重复上述过程，得到初始社团结构集合。对于社团结构间存在重叠节点情况，根据重叠节点与两个社团间的连边数解决重叠节点的归属问题，得到最终网络的社团结构。基准网络的实验结果表明，所提出的综合评价指标能更好地表征节点的重要性，与谱方法社团挖掘实验结果相比，所提出的种子节点社团挖掘算法具有较高性能。

社团挖掘；种子节点；节点重要性综合评价指标；复杂网络；非重叠社团

现实世界中许多规模较大且复杂的网络，如社会关系网络、生物分子网络等被看作复杂网络，社团结构是复杂网络的一个重要拓扑特征。社团结构是指社团内部结构紧密，社团间结构稀疏，对社团结构的分析与挖掘具有重要的学术研究价值和实际意义[1]。当前复杂网络社团结构挖掘大多基于聚类算法研究，复杂网络的聚类算法大致可归结为3类算法：(1)优化聚类算法。该类算法又可分为谱方法和局部搜索。(2)启发类算法。(3)其它类算法。该类算法又可分为相似度算法和混合搜索。然而，基于聚类的社团挖掘算法需事先确定社团的个数，但随着网络规模的不断扩大，获得全网的信息十分困难且时间复杂度较高。近年来，局部社团挖掘算法得到关注，其降低了计算的复杂度，但限于起始节点降低了挖掘的社团质量。本文给出了基于主成分分析技术由单一性节点重要性评价指标提取出的一种综合性评价指标寻找社团的种子节点，利用种子节点进行广度优先搜索策略进行社团挖掘，提高了社团质量，同时通过对这些种子节点的重点保护以提高整个网络的可靠性。

1　相关知识

目前，学者们主要从3个方面进行节点重要度的研究：(1)社会网络分析方法，通过分析网络中某些有用的信息，评估不同节点的重要性，例如节点的度中心性、介数、接近度及权重等属性[2]；(2)系统科学分析方法，利用网络的连通性来反映系统某种功能的完整性，通过度量节点删除对网络连通的破坏程度来反映网络节点的重要性，即“破坏性等价于重要性”，基于该思想学者们提出了系统的“核和核度”理论[3]，并通过对核度计算方法的定义实现了节点重要度的评价；(3)信息搜索领域分析方法，主要是通过分析网页之间的链接关系计算网页节点的重要性，例如著名的Pagerank算法[4]和HITS算法[5]等。现主要应用社会网络分析方法中的4种指标，分别为节点的点度中心性、接近度、介数和特征向量。

1.1度中心性(Degree centrality)

度中心性强调节点对网络的直接影响，节点自身的连接总数体现了个体对网络的影响。节点的度中心性越大，该节点可能就越重要。度中心性CD(v)的定义为

(1)

式中，deg(v)代表节点v的度；n代表网络中节点的个数。

1.2接近度(Closeness)

接近度是利用信息在网络传播速度的快慢来决定节点重要性的，跟节点最短路径或最小距离概念关系密切。它是比较网络中每一节点到达其它所有节点最短路径之和的差异来确定信息在网络中传播速度的快慢的。节点的接近度为节点到其它所有节点距离之和的倒数。节点i的接近度越大，表明节点越居于网络的中心，它在网络中就越重要。

(2)

式中，d(pi,pk)表示以pi为起点pk为终点的路径所包含的边的数量。

1.3介数(Betweenness)

节点的介数为经过该节点的最短路径数量，节点i的介数越大，说明该节点在网络中越重要。

(3)

1.4特征向量(Eigenvector centrality)

特征向量阐述了一个节点的重要性不仅与自己的度有关，而且与邻居节点的重要性有关，公式为

(4)

式中，xi为节点i的重要性度量值；aij为邻接矩阵中的元素；c为常数。

2　综合性评价指标的建立

节点的度中心性、接近度、介数和特征向量都为单一性评价指标，每一种指标都有其局限性。度中心性排序算法的结果比较粗糙，接近度排序算法在很大程度上都依赖于网络的拓扑结构，介数排序算法的时间复杂度很高且对于多数处于边缘的节点无法判断其重要性。因此，首先提出了一种结合节点的度中心性、接近度、介数和特征向量的综合性评价指标。

2.1综合性评价指标的建立过程

步骤一：构造指标矩阵。

假设有n个样本，对于4种单一性的评价指标，先构成一个n×4的数据指标矩阵

(5)

步骤二：单一评价指标的主成分分析。

主成分分析(Principal Component Analysis，PCA)是一种常用的基于变量协方差矩阵对信息进行处理、压缩和抽取的有效方法。

基本步骤如下：

(1)对原始指标数据做标准化处理，采集p维随机向量x=(x1,x2,…,xp)T(文中p取为4)，n个样本xi=(xi1，xi2，…，xip)T,i=1,2,…,n,n>p,构造样本阵，对样本阵元进行如下标准化变换，获得标准化矩阵Z

(6)

(2)由标准化矩阵Z求相关系数矩阵

(7)

(3)计算特征值与特征向量。

(4)计算主成分贡献率及累计贡献率。

一般取累计贡献率达85%～95%的特征值，λ1,λ2,…λm所对应的第1、第2、…第m(m

(5)计算主成分载荷

(8)

(6)计算主成分得分

(9)

3　算法描述与分析

算法的主要思想：根据综合性评价指标寻找种子节点，根据种子节点进行广度优先搜索策略进行社团挖掘[6]，最后，解决重叠节点的归属问题。算法分为两个阶段：(1) 根据综合性评价指标确定种子节点，然后挖掘种子节点所在社团的结构，描述如算法1；(2)解决重叠节点的归属问题，描述如算法2。

算法1：以种子节点为社团中心的社团挖掘算法。

输入：无权无向网络G(V,E)；

输出：社团结构集合S；

初始化：社团、集合S初始化为空集。

Step 1:根据综合性评价指标寻找种子节点。

根据综合性评价指标计算网络G中每个节点x的指标值Z(x)，将Z(x)最大的节点vi作为种子节点，将种子节点加入社团C中。

Step 2:根据种子节点进行广度优先搜索策略进行社团挖掘。

(1) 计算新加入社团C内节点的邻居节点集X。

If(X=null)

将社团C加入集合S中，在网络G中删除社团C内的节点，goto4)

Else

将vi的邻居节点集X加入社团C中

(2)计算X的邻居节点集。

If (X=null)

将社团C加入集合S中同时在网络G中删除社团C内的节点，goto4)

Else

IfZ(X)>Z(T)

计算T的邻居节点集W

IfZ(X)>max(Z(W))

将T加入X所在的社团C内

(3)对新加入社团C内的节点goto 2，直至新加入的节点的指标值小于其任何一邻居节点的指标值，将社团C加入集合S中，同时在网络G中删除社团C内的节点。

(4)判断网络G中是否还有剩余节点。若没有，完成社团划分。否则，goto Step1。

算法2：解决重叠节点的归属问题。

输入：从算法1得到的社团结构集合S；

输出：社团结构集合U；

初始化：社团结构集合U初始化为null。

Step 1: 从集合S(C1,C2，…，Ck)中依次选取集合S的社团Ci(i=1,2,…，k)；

Step2:If(集合S中只有一个社团Ci)。

将Ci加入集合U中，在集合S中删除社团Ci，goto 输出

Else

Ci与其它社团依次比较是否有重叠节点

If (无重叠节点)

将Ci加入集合U中，在集合S中删除社团Ci，goto Step 1

Else

按序找出与Ci有重叠节点的社团，比较重叠节点集T与社团Ci、Cj的连边数E(T,Ci)，E(T,Cj)

{

If (E(T,Ci)>E(T,Cj))

T属于社团Ci

If(E(T,Ci)

T属于社团Cj

If(E(T,Ci)=E(T,Cj))

T属于对它有较强影响力的社团

}

将Ci加入集合U中，在集合S中删除社团Ci，gotoStep1。

3.1算法的时间复杂度分析

综合性评价指标中构造矩阵使用介数和接近度，需计算任意两节点间的最短路径，使用Floyd算法求解最短路径，因此复杂度为O(n3)，使用主成分分析时间复杂度为O(n3)，因此，构造综合性评价指标所需的时间复杂度为O(n3)。在算法1中反复地比较节点间的综合性评价指标值，时间复杂度为，在算法2中解决重叠节点的归属问题，时间复杂度小于O(n)。所以本文算法的时间复杂度为O(n3)。

4　实验结果与分析

4.1综合性评价指标的验证

采用ARPT网络验证度中心性、接近度、介数、特征向量和综合性评价指标的有效性，结果如图1、图2所示。

图1　ARPT网络拓扑图

图2　节点的评价指标得分比较

采用上述5种指标分别得到ARPT网节点重要程度排序，删除前4个重要节点后看连通的子图数来判断该评价指标的优劣。连通子图的数量越多说明删除的节点越重要。

度中心性评价指标删除前4个重要节点(2,3,14,6)后，ARPT网分为5个连通子图。如图3所示。

接近度评价指标删除前4个重要节点(3,19,12,18)后，ARPT网分为2个连通子图。如图4所示。

图3　度中心性评价指标的连通子图

图4　接近度评价指标的连通子图

介数评价指标删除前4个重要节点(3,12,6,4)后，ARPT网分为4个连通子图。如图5所示。

特征向量评价指标删除前4个重要节点(2,15,14,3)后，ARPT网分为4个连通子图。如图6所示。

图5　介数评价指标的连通子图

图6　特征向量评价指标的连通子图

综合性评价指标删除前4个重要节点(3,2,14,12)后，ARPT网分为5个连通子图。如图7所示。

由分析得出度中心性评价指标和综合性评价指标删除重要节点后得到的连通子图数较多，在度中心性评价指标中2，3，14节点的得分都为0.2，因此不能判断哪个节点更重要，而在综合性评价指标中2，3，14节点的得分分别为0.234 5，0.273 9，0.223 2。所以提出的综合性评价指标找出的重要节点准确性较高。

4.2社团划分结果

4.2.1Zachary网络

Zachary网络[7]是社会学家Zachary在1970—1972年间对其观察和研究的空手道俱乐部中成员的社会关系构建的一个社会网络，如图8所示。网络含有34个节点和78条边，它们分别代表俱乐部成员和成员之间的社会关系。在观察期间，俱乐部主管和校长对是否需要提高收费标准的问题意见不一致，俱乐部分成了两个小俱乐部，主管和校长分别是这两个小俱乐部的核心人物。图8为Zachary基准网络，圆圈节点表示以主管为核心的俱乐部，方形表示以校长为核心的俱乐部网络。

图7　综合性评价指标的连通子图

图8　Zachary网络实际社团结构

将本文算法用于Zachary空手道俱乐部网络，得到的社团结构与实际完全一致。

4.2.2Football网络

该网络表示的是美国大学生足球联赛[3]2000年第一季度的比赛日程。网络中有115个节点613 条边，其中节点代表由学校名字命名的足球队，连边表示它们之间的规则季度赛。这些足球队被分成12个联盟，每个联盟包含5到13个足球队，同一个联盟中的球队比赛比不同联盟的球队比赛更频繁。实际联盟划分如图9所示，从上到下从左到右社团编号依次为：1，2，3，…，12。

将本文算法对Football网络进行分析，得到的社团结构如图10。

图9　Football网络实际社团结构

图10　本文算法对Football网络的实验结果

由划分结果可知社团1完全包含实际联盟1。社团2完全包含实际联盟2。社团3和4完全包含实际联盟3。社团5和6完全包含实际联盟4。除节点79外，社团7完全包含实际联盟5。社团9和10完全包含实际联盟7。社团11和12完全包含实际联盟8。社团13完全包含实际联盟9。除节点29和59外，社团14完全包含实际联盟10。除111和113节点外，社团17完全包含实际联盟12。将较小节点数记为错误节点数，统计错误节点数为11。

4.3与谱方法比较

为了表征社团划分效果的好坏主要用到3个性能指标[7]：

(1) 正确率(Correct rate,CR)，定义为

(10)

式中，n表示为正确划分的社团个数；N是整个网络中包含的节点总数。

(2)聚类准确率(ClusteringAccuracy,CA是指被正确划分的节点数占总节点数的比例)，定义为

(11)

式中，nt表示被正确划分到第t个社团的节点数；N是整个网络中包含的节点总数。

(3)RandIndex指标(RI，用于衡量划分结果所得社团中节点与实际社团中节点的一致性)。定义为

(12)

式中，n00表示节点对中，属于不同实际社团，同时被划分到不同社团中的节点对个数；n11表示节点对中，属于同一社团，同时被划分到相同社团的节点对个数；N是整个网络的节点总数。

将提出的算法与基于Laplace矩阵的谱方法和基于Normal矩阵的谱方法[8]作性能比较，如表1、表2所示。

表1　在Zachary’s karate network网络上3种算法的性能对比

表2　在American college football network网络上3种算法的性能对比

由表1、表2可知，所提出的算法比基于Laplace、Normal矩阵的谱方法在CR，CA和RI性能指标上都有所提高。对于性能指标CR：在Zachary网络上，本文算法比基于Laplace、Normal矩阵的谱方法提高了3.03%,在Football网络上，本文算法与基于Laplace矩阵的谱方法相等，比基于Normal矩阵的谱方法提高了6.11%。对于性能指标CA：在Zachary网络上，本文算法比基于Laplace、Normal矩阵的谱方法提高了3.03%,在Football网络上，本文算法比基于Laplace、Normal矩阵的谱方法分别提高了235.97%、147.41%。对于性能指标RI：在Zachary网络上，本文算法比基于Laplace、Normal矩阵的谱方法提高了6.23%,在Football网络上，本文算法比基于Laplace、Normal矩阵的谱方法分别提高了64.67%、4 142.20%。

5　结语

本文提出一种基于种子节点的社团挖掘算法，该算法首先给出了一种综合性评价指标寻找社团的种子节点，对种子节点进行广度优先搜索策略挖掘社团结构，算法思想简单同时提高了挖掘出的社团质量。从实验仿真分析可以看出，该算法与基于Laplace、Normal矩阵的谱方法相比具有较高的性能。进一步的工作：将该算法用于生物网络中的蛋白质相互作用网络(PPI)。

[1]范超翔,范磊.基于用户节点相似度的局部社团挖掘[D].上海：上海交通大学，2014.

[2]晋建志.复杂网络基于节点重要性的社团探测及社团演化模型研究[D].武汉：华中师范大学，2014.

[3]Murray S,Mark W Knotty.Centrality finding the connective core of a complex network[J].PLoS ONE,2012,7(5):e36579.

[4]Brin S,Page L.The anatomy of a large-scale hyper textual web search engine[J].Computer Networks and ISDN Systems,1998,30(1-7):107-117.

[5]Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632.

[6]易秀双,韩也挺,王兴伟.一种基于节点影响力的局部社团发现算法[J].小型微型计算机系统,2013, 34(9):975-980.

[7]贾宁宁,封筠.复杂网络中社团发现算法研究及应用[D].石家庄：石家庄铁道大学，2014.

[8]丁连红,时鹏.网络社区发现[M].北京:化学工业出版社,2008.

Study on Community Mining Algorithm Based on Seed Node for Non Overlapping

Zhang Xiaofen,Feng Jun,Jia Ningning

(School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China)

A novel algorithm based on seed node for community mining is proposed in this paper. Firstly, a comprehensive evaluating index for node importance is extracted from single indicators by using principal component analysis. Node with the maximum index value is selected as a seed node and breadth-first search operation for seed node is executed. Nodes with greater index value affect smaller nodes gradually and the community structure where seed node is located is gotten.Then, node is chosen with the largest index value from the outside known community structure.The above process is repeated and the initial community set is gotten.For the overlapping nodes between communities, Overlapping nodes and the number of edges between two communities is used to solve the attribution problem. Finally, the ultimate community structure of the entire network is established.The experimental results for benchmark networks show that comprehensive evaluating index is more suitable for node importance than single ones. Compared with spectral method, the performance of the presented algorithm based on seed node is higher.

community mining;seed node;comprehensive evaluating index for node importance;complex networks; non overlapping community

2015-09-28责任编辑:车轩玉DOI:10.13319/j.cnki.sjztddxxbzrb.2016.03.17

河北省自然科学基金(F2013210109)

张晓芬(1989-), 女,硕士研究生,主要从事复杂网络的研究。E-mail: 1270291637@qq.com

TP393

A

2095-0373(2016)03-0093-08

张晓芬，封筠，贾宁宁.种子节点非重叠社团挖掘算法研究[J].石家庄铁道大学学报:自然科学版,2016,29(3):93-100.