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 新模糊度量和最优化逼近方法
使用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)所示。
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 Yorklenum 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.