试论复杂网络交叠团模糊分析与信息挖掘.doc

试论复杂网络交叠团模糊分析与信息挖掘 摘要：针对复杂网络交叠团的聚类与模糊分析方法设计问题,给出一种新的模糊度量及相应的模糊聚类方法,并以新度量为基础,设计出两种挖掘网络模糊拓扑特征的新指标:团间连接紧密程度和模糊点对交叠团的连接贡献度,并将其用于网络交叠模块拓扑结构宏观分析和团间关键点提取。实验结果表明,使用该聚类与分析方法不仅可以获得模糊团结构,而且能够揭示出新的网络特征。该方法为复杂网络聚类后分析提供了新的视角。 针对复杂网络交叠团的聚类与模糊剖析办法设计Issue(问题),给出一种新的模糊度量及对应的模糊聚类办法,并以新度量为根底,设计出两种发掘网络模糊拓扑特征的新目标:团间衔接严密水平和模糊点对交叠团的衔接奉献度,并将其用于网络交叠模块拓扑构造微观剖析和团间关键点提取。实验后果标明,运用该聚类与剖析办法不只能够取得模糊勾结构,并且可以提醒出新的网络特征。该办法为复杂网络聚类后剖析提供了新的视角。 关键词：网络模糊聚类;团点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑 团结构是复杂网络普遍而又重要的拓扑属性之一,具有团内连接紧密、团间连接稀疏的特点。网络团结构提取是复杂网络分析中的一个基本步骤。揭示网络团结构的复杂网络聚类方法15对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都具有十分重要的理论意义和广泛的应用前景。目前,大多数提取方法不考虑重叠网络团结构,但在多数网络应用中,重叠团结构更为普遍,也更具有实际意义。 现有的网络重叠团结构提取方法610多数只对团间模糊点进行初步分析,如Nepusz等人9,10的模糊点提取。针对网络交叠团结构的深入拓扑分析,本文介绍一种新的团点相似度模糊度量。由于含有确定的物理含意和更为丰富的拓扑信息,用这种模糊度量可进一步导出团与团的连接紧密程度,以及模糊节点对两团联系的贡献程度,并设计出新指标和定量关系来深度分析网络宏观拓扑连接模式和提取关键连接节点。本文在三个实际网络上作了实验分析,其结果表明,本方法所挖掘出的网络拓扑特征信息为网络的模糊聚类后分析提供了新的视角。 1新模糊度量和最优化逼近方法 设A=Aijnn(Aij0)为n点权重无向网络G(V,E)的邻接矩阵,Y是由A产生的特征矩阵,表征点点距离,Yij0。假设图G的n个节点划分到r个交叠团中,用非负rn维矩阵W=Wkirn来表示团点关系,Wki为节点i与第k个团的关系紧密程度或相似度。W称为团点相似度矩阵。令 Mij=?rk=1WkiWkj(1) 若Wki能精确反映点i与团k的紧密度,则Mij可视为对点i、j间相似度Yij的一个近似。所以可用矩阵W来重构Y,视为用团点相似度W对点点相似度Y的估计: W?TWY(2) 用欧式距离构造如下目标函数: minW0F?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(symmetricalnon-negativematrixfactorization)。?s-NMF的求解与非负矩阵分解NMF11,12的求解方法非常类似。非负矩阵分解将数据分解为两个非负矩阵的乘积,得到对原数据的简化描述,被广泛应用于各种数据分析领域。类