复杂网络交叠团模糊分析与信息挖掘.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的求解方法非常类似。非负矩阵分解将数据分解为两个非负矩阵的乘积,得到对原数据的简化描述,被广泛应用于各种数据分析领域。类似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=-Aijij ?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的团内密