复杂网络特征结构的挖掘方法研究

《复杂网络特征结构的挖掘方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、博士学位论文复杂网络特征结构的挖掘方法研究作者：李伟指导教师：杨静宇教授南京理工大学2010年10月Ph．D．DissertationStudyonStructuralPatternsMiningonComplexNetworksByLi舭iSupervisedbyProf．YangJingYuNanjingUniversityofScience&TechnologyOctober,2010声明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一

2、同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。研究生签名：叫。年『D刖日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，按保密的有关规定和程序处理。研究生签名：砂7o年Io,9纠日博J’论文复杂嘲络特缸结构的挖掘疗i三研究摘要在过去的十年中，信息技术的迅速发展大大地提高了人类的计算能力，同时也积累了大量的观测数据有待研究者们分析，这些都鼓励着科技工作者对身边的世界作进一步的探索。将复杂的现实系统看作是互相关联的复杂网络

3、，正是最近时期所兴起的一种通用的研究模式，这种研究模式为多个领域的研究者提供了一个系统层次的观察视角。复杂网络，也被称为“网络新科学”研究学派，认为世界是由多种多样的系统组成，而现实世界中的复杂系统又是由成千上万个个体单元互相交互关联而组成，如果将个体单元抽象为网络中的顶点，单元间的交互关系抽象为网络的边，那么我们就可以通过研究抽象生成的网络结构来分析原系统的功能和性质。面对错综复杂的现实网络结构，研究者使用统计的方法分析网络拓扑。对网络的整体属性提出了许多新的网络拓扑度量方法，并建立新的网络模型来模拟现实网络数据，希望能够进一步预测网络上的传播动力学现象。近十年来，复杂网络研究者在这些方向

4、上取得了重大的进展。复杂网络研究是在建立在图论和社会网络分析的基础上，并以新近获得的实证网络数据为研究对象，为解决实际问题而发展起来。伴随着研究的深入，人们需要对网络作更深层的分析，想了解网络更多的细节信息，而传统的网络分析理论工具往往难以处理近期获得的大数据集。面对这样的困难，网络分析中的方法论研究就显得十分迫切。针对该问题，本文尝试从一个新的角度思考网络分析问题。考虑到网络中的特征结构，如社团、层次等，通常是由具有某种相似性的网络顶点所构成，而统计数据分析领域的理论工具恰恰町以分析数据分布中数据点1'8j的相似关系，抽取数据分布中的结构。如果能够将网络问题转化成数据分析问题，那么就可以利

5、用数据分析工具来处理网络问题。本文主要工作即是首先通过一定的测量方法将网络投影到高维测量空间，再应用信号处理和统计模式识别领域中的数学工具来深层挖掘由网络生成的点分布，进而依据挖掘得到的点分布结构特征来反推原网络的结构特征。读者将从文章中的实验看到，运用该思路分析处理实际网络时，可以便利地解决许多困难的网络结构分析问题。本文将上述思路应用在三个网络分析问题上，分别为“网络拓扑分析”、“网络社团发现”和“网络结构比较”。第一，网络拓扑分析。我们将待研究的网络依据一定的准则投影到测量空间，并且将网络中相似的节点投影在相近的位置，这样原网络的拓扑特征就可以从投影的数据点集中涌现出来。我们用该网络投

6、影方法分析了随机图、规则图、小世摘要博卜论文界网和无标度网，四个网络模型的各自结构特征可以很好地被显示出来。我们进一步使用网络投影方法分析了现实的Intemet自治域数据，Intemet的层次结构和水母模型也得到了验证。继而我们借用数据分布的度鼍作为网络的结构度量，并依据该度量作实际网络的相似性分析，结果表明同类网络的呈现出相似的度量值。实验表明了“网络投影"方法的有效性。第二，网络社团发现。社团结构足现实网络中普遍存在的一种基本结构，与网络的功能和性质关系紧密。分析网络的社团结构具有重要的理论实践意义。本文提出将网络的社团结构对应为信号处理领域的独立成分，基于顶点的相似性，从而从信号数据分

7、析的角度来探讨网络的社团发现问题。首先将网络投影成测量空间的点分布，再使用经典的聚类方法寻找相似的点组成的点群，最后将根据在测量宅间中找到的点群结构来确定网络中的社团结构。通过分析Zachary柔道俱乐部网络和南方女士网络，我们验证了本方法叮以有效地发现社团结构。第三，网络结构比较。对网络进行适当的测量，生成的点分布可以反映网络许多基本结构特征，根据该点，我们用的数据分析方法从生成的点分布中挖掘E要结构度鼍，