摘 要:针对复杂网络交叠团的聚类与模糊分析方法设计问题,给出一种新的模糊度量及相应的模糊聚类方法,并以新度量为基础,设计出两种挖掘网络模糊拓扑特征的新指标:团间连接紧密程度和模糊点对交叠团的连接贡献度,并将其用于网络交叠模块拓扑结构宏观分析和团间关键点提取。实验结果表明,使用该聚类与分析方法不仅可以获得模糊团结构,而且能够揭示出新的网络特征。该方法为复杂网络聚类后分析提供了新的视角。
针对复杂网络交叠团的聚类与模糊剖析办法设计Issue(问题),给出一种新的模糊度量及对应的模糊聚类办法,并以新度量为根底,设计出两种发掘网络模糊拓扑特征的新目标:团间衔接严密水平和模糊点对交叠团的衔接奉献度,并将其用于网络交叠模块拓扑构造微观剖析和团间关键点提取。实验后果标明,运用该聚类与剖析办法不只能够取得模糊勾结构,并且可以提醒出新的网络特征。该办法为复杂网络聚类后剖析提供了新的视角。
关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑
Fuzzy clustering and information mining in complex networks
ZHAO Kun,ZHANG Shao-wu,PAN Quan
(School of Automation, Northwestern Polytechnical University, Xi’an 710072, China)
Abstract:There is seldom a method which is capable of both clustering the network and analyzing the resulted overlapping communities. To solve this problem, this paper presented a novel fuzzy metric and a soft clustering algorithm. Based on the novel metric, two topological fuzzy metric, which include clique-clique closeness degree and inter-clique connecting contribution degree, were devised and applied in the topological macro analysis and the extraction of key nodes in the overlapping communities. Experimental results indicate that, as an attempt of analysis after clustering, the new indicators and mechanics can uncover new topology features hidden in the network.
Key words:network fuzzy clustering; clique-node similarity; clique-clique closeness degree; inter-clique connection contribution degree; symmetrical nonnegative matrix factorization(s-NMF); network topology macrostructure
团结构是复杂网络普遍而又重要的拓扑属性之一,具有团内连接紧密、团间连接稀疏的特点。网络团结构提取是复杂网络分析中的一个基本步骤。揭示网络团结构的复杂网络聚类方法[1~5]对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都具有十分重要的理论意义和广泛的应用前景。目前,大多数提取方法不考虑重叠网络团结构,但在多数网络应用中,重叠团结构更为普遍,也更具有实际意义。
现有的网络重叠团结构提取方法[6~10]多数只对团间模糊点进行初步分析,如Nepusz等人[9,10]的模糊点提取。针对网络交叠团结构的深入拓扑分析,本文介绍一种新的团—点相似度模糊度量。由于含有确定的物理含意和更为丰富的拓扑信息,用这种模糊度量可进一步导出团与团的连接紧密程度,以及模糊节点对两团联系的贡献程度,并设计出新指标和定量关系来深度分析网络宏观拓扑连接模式和提取关键连接节点。本文在三个实际网络上作了实验分析,其结果表明,本方法所挖掘出的网络拓扑特征信息为网络的模糊聚类后分析提供了新的视角。
1 新模糊度量和最优化逼近方法
设A=[Aij]n×n(Aij≥0)为n点权重无向网络G(V,E)的邻接矩阵,Y是由A产生的特征矩阵,表征点—点距离,Yij>0。假设图G的n个节点划分到r个交叠团中,用非负r×n维矩阵W=[Wki]r×n来表示团—点关系,Wki为节点i与第k个团的关系紧密程度或相似度。W称为团—点相似度矩阵。令
Mij=?rk=1WkiWkj(1)
若Wki能精确反映点i与团k的紧密度,则Mij可视为对点i、j间相似度Yij的一个近似。所以可用矩阵W来重构Y,视为用团—点相似度W对点—点相似度Y的估计:
W ?TW→Y(2)
用欧式距离构造如下目标函数:
minW≥0 F?G(Y,W)=‖Y-W ?TW‖?F=?12?ij[(Y-W ?TW)。(Y-W ?TW)]ij(3)
其中:‖•‖?F为欧氏距离;A。B表示矩阵A、B的Hadamard 矩阵乘法。由此,模糊度量W的实现问题转换为一个最优化问题,即寻找合适的W使式(3)定义的目标函数达到最小值。
式(3)本质上是一种矩阵分解,被称为对称非负矩阵分解,或s-NMF (symmetrical non-negative matrix factorization)。?s-NMF的求解与非负矩阵分解NMF[11,12]的求解方法非常类似。非负矩阵分解将数据分解为两个非负矩阵的乘积,得到对原数据的简化描述,被广泛应用于各种数据分析领域。类似NMF的求解,s-NMF可视为加入限制条件(H=W)下的NMF。给出s-NMF的迭代式如下:
Wk+1=W?k。[W?kY]/[W?kW ?T?kW?k](4)
其中:[A]/[B]为矩阵A和B的Hadamard矩阵除法。
由于在NMF中引入了限制条件,s-NMF的解集是NMF的子集,即式(4)的迭代结果必落入NMF的稳定点集合中符合附加条件(H=W)的部分,由此决定s-NMF的收敛性。
在求解W之前还需要确定特征矩阵。本文选扩散核[13]为被逼近的特征矩阵。扩散核有明确的物理含义,它通过计算节点间的路径数给出任意两节点间的相似度,能描述网络节点间的大尺度范围关系,当两点间路径数增加时,其相似度也增大。扩散核矩阵被定义为
K=exp(-βL)(5)
其中:参数β用于控制相似度的扩散程度,本文取β=0.1;L是网络G的拉普拉斯矩阵:
Lij=-Aiji≠j
?kAiki=j(6)
作为相似度的特征矩阵应该是扩散核矩阵K的归一化?形式:
Yij=Kij/(KiiKjj)??1/2(7)
基于扩散核的物理含义,团—点相似度W也具有了物理含义:团到点的路径数。实际上,W就是聚类结果,对其列归一化即可得模糊隶属度,需要硬聚类结果时,则选取某点所对应列中相似度值最大的团为最终所属团。
2 团—团关系度量
团—点相似度W使得定量刻画网络中的其他拓扑关系成为可能。正如W ?TW可被用来作为点与点的相似度的一个估计,同样可用W来估计团—团关系:
Z=WW ?T(8)
其物理含义是团与团间的路径条数。很明显,Z的非对角元ZJK刻画团J与团K之间的紧密程度,或团间重叠度,对角元ZJJ则刻画团J的团内密度。?
以图1中的对称网络为例,二分团时算得
Z=WW ?T=1.337 60.035 3
0.035 31.337 6
由于图1中的网络是对称网络,两团具有同样的拓扑连接模式,它们有相同的团内密度1.337 6,而团间重叠度为?0.035 3。3 团间连接贡献度
ZJK度量了团J与团K间的重叠程度:
ZJK=?na=1WJaWKa(9)
其中:WJaWKa是这个总量来自于点a的分量。下面定义一个新指标来量化给定点对团间连接的贡献。假设点i是同时连接J、K两团的团间某点,定义点i对团J和团K的团间连接贡献度为
B?i=[(WJiWKi)/(?na=1WJaWKa)]×100%(10)
显然,那些团间连接贡献大的点应处于网络中连接各团的关键位置,它们对团间连接的稳定性负主要责任。将这种在团与团间起关键连接作用的点称为关键连接点。为了设定合适的阈值来提取团间关键连接点,本文一律取B>10%的点为关键连接点。
4 实验与结果分析
下面将在三个实际网络上展开实验,首先根据指定分团个数计算出团—点相似度W,然后用W计算团—团关系和B值,并提取关键连接点。
4.1 海豚社会网
由Lusseau等人[14]给出的瓶鼻海豚社会网来自对一个62个成员的瓶鼻海豚社会网络长达七年的观测,节点表示海豚,连线为对某两只海豚非偶然同时出现的记录。图2(a)中名为SN100 (点36)的海豚在一段时间内消失,导致这个海豚网络分裂为两部分。
使用s-NMF算法聚类,海豚网络分为两团时,除30和39两点外,其他点的分团结果与实际观测相同,如图2(a)所示。计算B值并根据阈值提取出的五个关键连接点:1、7、28、36、40(虚线圈内),它们对两团连接起到至关重要的作用。图2(b)为这五点的B值柱状图。该图显示,节点36(SN100)是五个关键连接点中B值最大者,对连接两团贡献最大。某种程度上,这个结果可以解释为什么海豚SN100的消失导致了整个网络最终分裂的影响。本例说明,s-NMF算法及团间连接贡献程度指标在分析、预测社会网络演化方面有着独具特色的作用。
4.2 Santa Fe 科学合作网
用本算法对Newman等人提供的Santa Fe科学合作网络[15]加以测试。271个节点表示涵盖四个学术领域的学者,学者合作发表文章产生网络连接,构成了一个加权合作网络。将本算法用于网络中一个包含118个节点的最大孤立团,如图3(a)所示。
图3(a)中,四个学科所对应的主要组成部分都被正确地分离出来,mathematical ecology(灰菱形)和agent-based models(白方块)与文献[15]的结果一致,中间的大模块statistical physics又被细分为四个小块,以不同灰度区分。计算了24个点的团间连接度贡献值B,从中分离出11个B值大于10%的点作为关键连接点:1、2、4、6、11、12、20、47、50、56、57,其标号在横轴下方标出,见图3(b),并在图3(a)中用黑色圆圈标记,这些连接点对应那些具有多种学科兴趣、积极参与交叉研究的学者。除去这11个点时,整个网络的连接布局被完全破坏,见图3(a)下方灰色背景缩小图,可见关键连接点的确起到重要的沟通各模块的作用。
4.3 杂志索引网络
在Rosvall等人[16]建立的2004年杂志索引网络上进行测试。网络节点代表杂志,分为物理学(方形)、化学(方形)、生物学(菱形)、生态学(三角形)四个学科领域,每个学科中各选10份影响因子最高的刊物,共40个节点,若某刊物文章引用了另一刊物文章,则两刊间有一条连线,形成189条连接。使用s-NMF对该网4分团时,聚类结果与实际分团情况完全一致,如图4(a)所示。
由本算法得出的团—点相似度W在网络宏观拓扑结构的挖掘方面有非常有趣的应用,如第2章所述,用W计算团—团相似度矩阵Z=WW?T,其对角元是团内连接密度,非对角元表征团与团的连接紧密程度,故Z可被视为对原网络的一种“压缩表示”。如果将团换成“点”,将团与团之间的连接换成“边”,利用Z的非对角元,就能构造出原网络的一个压缩投影网络,如图4(b)所示。这是原网络的一个降维示意图,也是团与团之间关系定量刻画的形象表述,定量地反映了原网络在特定分团数下的“宏观(全局)拓扑轮廓”,图上团间连线色深和粗细表示连接紧密程度。由图4(b)可以看到,physics和chemistry连接最紧密,而chemistry与biology和biology与?ecology次之。由此推测,如果减少分团数,将相邻两团合并,连接最紧密的两团必首先合并为一个团。实际情况正是如此:分团数为3时,biology和ecology各自独立成团,physics 和?chemistry合并为一个大团,这与文献[11]结果一致。
5 讨论
网络模糊聚类能帮助研究者进一步对团间的一些特殊点进行定量分析,如Nepusz等人[9]用一种桥值公式来刻画节点在多个团间的共享程度,即节点从属度的模糊程度。而本文的团间连接贡献度B反映出节点在团间连接中所起的作用大小。本质上它们是完全不同的两种概念,同时它们也都是网络模糊分析中所特有的。团间连接贡献度指标的提出,将研究引向对节点在网络宏观拓扑模式中的影响力的关注,是本方法的一个独特贡献。无疑,关键连接点对团间连接的稳定性起到很大作用,如果要迅速切断团间联系,改变网络的宏观拓扑格局,首先攻击关键连接点(如海豚网中的SD100)是最有效的方法。团间连接贡献度这一定义的基础来自于对团与团连接关系(Z)的定量刻画,这个定量关系用以往的模糊隶属度概念无法得到。由于W有明确的物理含义,使得由W导出的团—团关系Z也具有了物理含义,这对网络的宏观拓扑分析非常?有利。
6 结束语
针对复杂网络交叠团现象,本文给出了一个新的聚类后模糊分析框架。它不仅能对网络进行模糊聚类,而且支持对交叠结构的模糊分析,如关键点的识别和网络宏观拓扑图的提取。使用这些新方法、新指标能够深入挖掘潜藏于网络的拓扑信息。从本文的聚类后分析不难看出,网络模糊聚类的作用不仅在于聚类本身,还在于模糊聚类结果能够为网络拓扑深入分析和信息挖掘提供支持,而硬聚类则不能。今后将致力于对团间连接贡献度指标进行更为深入的统计研究。
参考文献:
[1]
赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法[J].计算机应用研究,2009,26(6):2041-2043,2049.
[2]汪小帆,刘亚冰.复杂网络中的社团结构算法综述[J].电子科技大学学报,2009,38(5):537-543.
[3]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[4]WHITE S,SMYTH P.A spectral clustering approach to finding communities in graphs[C]//Proc of SIAM International Conference on Data Mining.2005.
[5]ENRIGHT A J,DONGEN S V,OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research,2002,30(7):1575-1584.
[6]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.
[7]PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
?[8]REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in complex networks with a potts model[J].Physical Review Letters,2004,93(21):218701.
?[9]NEPUSZ T,PETROCZI A,N?GYESSY L,et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E,2008,77(1):016107.
[10]ZHANG Shi-hua,WANG Rui-sheng,ZHANG Xiang-sun.Identification of overlapping community structure in complex networks using fuzzy C-means clustering[J].Physical Review A:Statistical Mechanics and Its Applications,2007,374(1):483-490.
[11]PAATERO P,TAPPER U.Positive matrix factorization:a non-negative factor model with optimal utilization of error estimates of data values[J].Environmetrics,1994,5(2):111-126.
[12]ANTTILA P,PAATERO P,TAPPER U,et al.Source identification of bulk wet deposition in Finland by positive matrix factorization[J].Atmospheric Environment,1995,29(14):1705-1718.
[13]KONDOR R I,LAFFERTY J.Diffusion kernels on graphs and other discrete structures[C]//Proc of the 19th International Conference on Machine Learning.San Francisco:Morgan Kaufmann,2002.
[14]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations:can geographic isolation explain this unique trait?[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[15]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.
[16]ROSVALL M,BERGSTROM C T.An information-theoretic framework for resolving community structure in complex networks [J].Proceedings of the National Academy of Sciences of the United States of ?America,2007,104(18):7327-7331.
