1、复杂网络交叠团模糊分析与信息挖掘摘 要:针对复杂网络交叠团的聚类与模糊分析方法设计问题,给出一种新的模糊度量及相应的模糊聚类方法,并以新度量为基础,设计出两种挖掘网络模糊拓扑特征的新指标:团间连接紧密程度和模糊点对交叠团的连接贡献度,并将其用于网络交叠模块拓扑结构宏观分析和团间关键点提取。实验结果表明,使用该聚类与分析方法不仅可以获得模糊团结构,而且能够揭示出新的网络特征。该方法为复杂网络聚类后分析提供了新的视角。 针对复杂网络交叠团的聚类与模糊剖析办法设计 Issue(问题),给出一种新的模糊度量及对应的模糊聚类办法,并以新度量为根底,设计出两种发掘网络模糊拓扑特征的新目标:团间衔接严密水平
2、和模糊点对交叠团的衔接奉献度,并将其用于网络交叠模块拓扑构造微观剖析和团间关键点提取。实验后果标明,运用该聚类与剖析办法不只能够取得模糊勾结构,并且可以提醒出新的网络特征。该办法为复杂网络聚类后剖析提供了新的视角。关键词:网络模糊聚类;团点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑 Fuzzy clustering and information mining in complex networks ZHAO Kun,ZHANG Shao-wu,PAN Quan (School of Automation, Northwestern Polytechnical Un
3、iversity, Xian 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 topolog
4、ical 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 af
5、ter 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); netw
6、ork topology macrostructure 团结构是复杂网络普遍而又重要的拓扑属性之一,具有团内连接紧密、团间连接稀疏的特点。网络团结构提取是复杂网络分析中的一个基本步骤。揭示网络团结构的复杂网络聚类方法15对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都具有十分重要的理论意义和广泛的应用前景。目前,大多数提取方法不考虑重叠网络团结构,但在多数网络应用中,重叠团结构更为普遍,也更具有实际意义。 现有的网络重叠团结构提取方法610多数只对团间模糊点进行初步分析,如 Nepusz 等人9,10的模糊点提取。针对网络交叠团结构的深入拓扑分析,本文介绍一种新的团点相似度
7、模糊度量。由于含有确定的物理含意和更为丰富的拓扑信息,用这种模糊度量可进一步导出团与团的连接紧密程度,以及模糊节点对两团联系的贡献程度,并设计出新指标和定量关系来深度分析网络宏观拓扑连接模式和提取关键连接节点。本文在三个实际网络上作了实验分析,其结果表明,本方法所挖掘出的网络拓扑特征信息为网络的模糊聚类后分析提供了新的视角。 1 新模糊度量和最优化逼近方法 设 A=Aijnn(Aij0)为 n 点权重无向网络 G(V,E)的邻接矩阵,Y是由 A 产生的特征矩阵,表征点点距离,Yij0。假设图 G 的 n 个节点划分到 r 个交叠团中,用非负 rn 维矩阵 W=Wkirn 来表示团点关系,Wki
8、 为节点 i 与第 k 个团的关系紧密程度或相似度。W 称为团点相似度矩阵。令 Mij=?rk=1WkiWkj(1) 若 Wki 能精确反映点 i 与团 k 的紧密度,则 Mij 可视为对点 i、j 间相似度 Yij 的一个近似。所以可用矩阵 W 来重构 Y,视为用团点相似度W 对点点相似度 Y 的估计: W ?TWY(2) 用欧式距离构造如下目标函数: minW0 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 的实现问题转换为一个最优化问
9、题,即寻找合适的 W 使式(3)定义的目标函数达到最小值。 式(3)本质上是一种矩阵分解,被称为对称非负矩阵分解,或 s-NMF (symmetrical non-negative matrix factorization)。?s-NMF 的求解与非负矩阵分解 NMF11,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 的
10、Hadamard 矩阵除法。 由于在 NMF 中引入了限制条件,s-NMF 的解集是 NMF 的子集,即式(4)的迭代结果必落入 NMF 的稳定点集合中符合附加条件(H=W)的部分,由此决定 s-NMF 的收敛性。 在求解 W 之前还需要确定特征矩阵。本文选扩散核13为被逼近的特征矩阵。扩散核有明确的物理含义,它通过计算节点间的路径数给出任意两节点间的相似度,能描述网络节点间的大尺度范围关系,当两点间路径数增加时,其相似度也增大。扩散核矩阵被定义为 K=exp(-L)(5) 其中:参数 用于控制相似度的扩散程度,本文取 =0.1;L 是网络G 的拉普拉斯矩阵: Lij=-Aijij ?kAik
11、i=j(6) 作为相似度的特征矩阵应该是扩散核矩阵 K 的归一化?形式: Yij=Kij/(KiiKjj)?1/2(7) 基于扩散核的物理含义,团点相似度 W 也具有了物理含义:团到点的路径数。实际上,W 就是聚类结果,对其列归一化即可得模糊隶属度,需要硬聚类结果时,则选取某点所对应列中相似度值最大的团为最终所属团。2 团团关系度量 团点相似度 W 使得定量刻画网络中的其他拓扑关系成为可能。正如 W ?TW 可被用来作为点与点的相似度的一个估计,同样可用 W 来估计团团关系: Z=WW ?T(8) 其物理含义是团与团间的路径条数。很明显,Z 的非对角元 ZJK 刻画团 J 与团 K 之间的紧密
12、程度,或团间重叠度,对角元 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
13、的团间连接贡献度为B?i=(WJiWKi)/(?na=1WJaWKa)100%(10) 显然,那些团间连接贡献大的点应处于网络中连接各团的关键位置,它们对团间连接的稳定性负主要责任。将这种在团与团间起关键连接作用的点称为关键连接点。为了设定合适的阈值来提取团间关键连接点,本文一律取 B10%的点为关键连接点。 4 实验与结果分析 下面将在三个实际网络上展开实验,首先根据指定分团个数计算出团点相似度 W,然后用 W 计算团团关系和 B 值,并提取关键连接点。 4.1 海豚社会网 由 Lusseau 等人14给出的瓶鼻海豚社会网来自对一个 62 个成员的瓶鼻海豚社会网络长达七年的观测,节点表示海豚
14、,连线为对某两只海豚非偶然同时出现的记录。图 2(a)中名为 SN100 (点 36)的海豚在一段时间内消失,导致这个海豚网络分裂为两部分。 使用 s-NMF 算法聚类,海豚网络分为两团时,除 30 和 39 两点外,其他点的分团结果与实际观测相同,如图 2(a)所示。计算 B 值并根据阈值提取出的五个关键连接点:1、7、28、36、40(虚线圈内),它们对两团连接起到至关重要的作用。图 2(b)为这五点的 B 值柱状图。该图显示,节点36(SN100)是五个关键连接点中 B 值最大者,对连接两团贡献最大。某种程度上,这个结果可以解释为什么海豚 SN100 的消失导致了整个网络最终分裂的影响。
15、本例说明,s-NMF 算法及团间连接贡献程度指标在分析、预测社会网络演化方面有着独具特色的作用。 4.2 Santa Fe 科学合作网 用本算法对 Newman 等人提供的 Santa Fe 科学合作网络15加以测试。271 个节点表示涵盖四个学术领域的学者,学者合作发表文章产生网络连接,构成了一个加权合作网络。将本算法用于网络中一个包含 118 个节点的最大孤立团,如图 3(a)所示。 图 3(a)中,四个学科所对应的主要组成部分都被正确地分离出来,mathematical ecology(灰菱形)和 agent-based models(白方块)与文献15的结果一致,中间的大模块 stat
16、istical 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 年杂志索引网络上进行测试。网络节点代表杂
17、志,分为物理学(方形)、化学(方形)、生物学(菱形)、生态学(三角形)四个学科领域,每个学科中各选 10 份影响因子最高的刊物,共 40个节点,若某刊物文章引用了另一刊物文章,则两刊间有一条连线,形成189 条连接。使用 s-NMF 对该网 4 分团时,聚类结果与实际分团情况完全一致,如图 4(a)所示。 由本算法得出的团点相似度 W 在网络宏观拓扑结构的挖掘方面有非常有趣的应用,如第 2 章所述,用 W 计算团团相似度矩阵 Z=WW?T,其对角元是团内连接密度,非对角元表征团与团的连接紧密程度,故 Z 可被视为对原网络的一种“压缩表示” 。如果将团换成“点”,将团与团之间的连接换成“边”,利
18、用 Z 的非对角元,就能构造出原网络的一个压缩投影网络,如图 4(b)所示。这是原网络的一个降维示意图,也是团与团之间关系定量刻画的形象表述,定量地反映了原网络在特定分团数下的“宏观(全局)拓扑轮廓”,图上团间连线色深和粗细表示连接紧密程度。由图4(b)可以看到,physics 和 chemistry 连接最紧密,而 chemistry 与biology 和 biology 与?ecology 次之。由此推测,如果减少分团数,将相邻两团合并,连接最紧密的两团必首先合并为一个团。实际情况正是如此:分团数为 3 时,biology 和 ecology 各自独立成团,physics 和?chemis
19、try合并为一个大团,这与文献11结果一致。 5 讨论 网络模糊聚类能帮助研究者进一步对团间的一些特殊点进行定量分析,如 Nepusz 等人9用一种桥值公式来刻画节点在多个团间的共享程度,即节点从属度的模糊程度。而本文的团间连接贡献度 B 反映出节点在团间连接中所起的作用大小。本质上它们是完全不同的两种概念,同时它们也都是网络模糊分析中所特有的。团间连接贡献度指标的提出,将研究引向对节点在网络宏观拓扑模式中的影响力的关注,是本方法的一个独特贡献。无疑,关键连接点对团间连接的稳定性起到很大作用,如果要迅速切断团间联系,改变网络的宏观拓扑格局,首先攻击关键连接点(如海豚网中的SD100)是最有效的
20、方法。团间连接贡献度这一定义的基础来自于对团与团连接关系(Z)的定量刻画,这个定量关系用以往的模糊隶属度概念无法得到。由于 W 有明确的物理含义,使得由 W 导出的团团关系 Z 也具有了物理含义,这对网络的宏观拓扑分析非常?有利。 6 结束语 针对复杂网络交叠团现象,本文给出了一个新的聚类后模糊分析框架。它不仅能对网络进行模糊聚类,而且支持对交叠结构的模糊分析,如关键点的识别和网络宏观拓扑图的提取。使用这些新方法、新指标能够深入挖掘潜藏于网络的拓扑信息。从本文的聚类后分析不难看出,网络模糊聚类的作用不仅在于聚类本身,还在于模糊聚类结果能够为网络拓扑深入分析和信息挖掘提供支持,而硬聚类则不能。今
21、后将致力于对团间连接贡献度指标进行更为深入的统计研究。参考文献: 1 赵凤霞,谢福鼎.基于 K-means 聚类算法的复杂网络社团发现新方法J.计算机应用研究,2009,26(6):2041-2043,2049. 2汪小帆,刘亚冰.复杂网络中的社团结构算法综述J.电子科技大学学报,2009,38(5):537-543. 3NEWMAN M E J.Modularity and community structure in networksJ.Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.4WHITE S,SMYTH P.A spectral clustering approach to finding communities in graphsC/Proc of SIAM International Conference on Data Mining.2005. 5ENRIGHT A J,DONGEN S V,OUZOUNIS C A.An efficient
