浅析复杂网络交叠团模糊分析与信息挖掘
摘 要:针对复杂网络交叠团的聚类与模糊分析方法设计问题,给出一种新的模糊度量及相应
的模糊聚类方法,并以新度量为基础,设计出两种挖掘网络模糊拓扑特征的新指标:团间连接
紧密程度和模糊点对交叠团的连接贡献度,并将其用于网络交叠模块拓扑结构宏观分析和
团间关键点提取。实验结果表明,使用该聚类与分析方法不仅可以获得模糊团结构,而且能
够揭示出新的网络特征。该方法为复杂网络聚类后分析提供了新的•视角。
关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵
分解;网络宏观拓扑
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)
其中:参数 β 用于控制相似度的扩散程度,本文取 β=;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= 3
6
由于图 1 中的网络是对称网络,两团具有同样的拓扑连接模式,它们有相同的团内密度
6,而团间重叠度为• 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 值,并提取关键连接点。
海豚社会网
由 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 算法及团间连接贡献程度指标在分析、预测社会网络演化方面有着独具特
色的作用。
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)下方灰色背景缩小图,可见关键连接点的确起到重要的
沟通各模块的作用。
杂志索引网络
在 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 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 spectral clustering approach to finding communities in
graphs[C]//Proc of SIAM International Conference on Data .
[5]ENRIGHT A J,DONGEN S V,OUZOUNIS C efficient algorithm for large-scale
detection of protEin families[J].NuclEIc Acids Research,2002,30(7):1575-1584.
[6]BEZDEK J recognition with fuzzy objective function algorithms[M].New
York:Plenum Press,1981.
[7]PALLA G,DERENYI I,FARKAS I,et the overlapping community
structures of complex networks in nature and society[J].Nature,2005,435(7043):814-
818.
•[8]REICHARDT J,BORNHOLDT 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 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 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 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 identification of bulk wet
deposition in Finland by positive matrix factorization[J].Atmospheric
Environment,1995,29(14):1705-1718.
[13]KONDOR R I,LAFFERTY kernels on graphs and other discrete
structures[C]//Proc of the 19th International Conference on Machine
Francisco:Morgan Kaufmann,2002.
[14]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et 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 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 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.
