基于互联网拓扑特征的多粒度社团发现算法及其可视化_硕士学位毕业论文(编辑修改稿)

基于互联网拓扑特征的多粒度社团发现算法及其可视化_硕士学位毕业论文(编辑修改稿)内容摘要：

....................................... 35 合而聚之 ............................................................................................................................ 36 模块度 ..................................................................................................................... 36 小社团合并算法 ...................................................................................................... 37 社团划分比较 ................................................................................................................... 40 东北大学硕士学位论文 目 录 VII 对于全球 IPV6 拓扑的划分比较 ................................................................................... 41 105 算法在其它网络上的测试 ......................................................................................... 43 Karate 俱乐部 ....................................................................................................... 43 东北大学嵌入式实验室 聊天网络 — 网络的共产主义 .................................. 45 东大嵌入式实验室日常人际交流网络 — 地理位置隔离的社团结构 ............... 46 新的衡量社团划分质量方法的探讨 ............................................................................... 48 新的社团发现思路 ............................................................................................... 48 新的求解最短路径的算法 ...................................................................................... 49 本章小结 .................................................................................................................... 49 第 4 章 一种新的面向社团的网络拓扑可视化算法 ................................................................................... 51 可视化算法综述 ............................................................................................................... 51 面向社团结构特征的可视化 ........................................................................................... 53 所用开发工具 .......................................................................................................... 53 算法思想 ................................................................................................................. 54 算法设计与实现 ...................................................................................................... 54 本章小结 ........................................................................................................................... 59 第 5 章 总结与展望 ................................................................................................................................................ 60 本文所做的工作 ............................................................................................................... 60 不足及展望 ....................................................................................................................... 61 参考文献 .................................................................................................................................................................... 62 致 谢 ......................................................................................................................................................................... 66 攻读硕士期间发表的论文 .................................................................................................................................... 68 东北大学硕士学位论文 第 1章 绪 论 1 第 1 章 绪 论 课题研究的背景与意义 互联网的社 团结构研究现状 近年来 ,随着信息系统（如 WWW、 电信网、 广播电视网 、移动网络等 ）的迅猛发展，网络拓扑数据的规模快速增大 ，以致人们不能通过传统技术和方式来管理和运作这些复杂网络。 人们通过对生物网络、 社会关系网、 Web 网等的研究 ,发现这些网络都具有某些共同特点，包括：整体相对稀疏 ，局部比较密集；顶点度值服从幂率分布，也被称为无标度特性 [1]；整体分布具有高聚集度、 低平均最短路径 (平均最短路径为 O (loglog N) ) 的小世界特性 [2]。 具有以上性质（无标度性、小世界性）的网络被称为复杂网络。 互联网具有典型的复杂网络结构，本文后续的研究手段都是以复杂网络理论为基础。 在现实世界中，存在大量复杂系统，可把这些复杂系统看作各种网络来研究。 一个典型的网络是由若干节点 iv ( ivV )以及连接任意两个在实际拓扑中有连接关系的节点jv 和 kv ( ,jkv v V )的边 jke ( jk Ee  .)组成。 网络的研究最早可追溯到 18 世纪，数学家欧拉在对“ Konigsberg 七桥问题”的研究时提出的一个数学分支 —— 图论，图论在较长的时间内一直未能有突破性进展。 上世纪 60 年代， Erdős 和 R233。 nyi 建立了随机图理论[3](Random Graph Theory)，开创了复杂网路理论系统性研究。 自此以后的很长时间内随机图理论一直是复杂网络结构研究的基本理论 [4]。 随机图理论有明显的缺点，它不能很好的描述 很多实际网络，因为大部分实际网络并不是完全随机的。 例如 Inter 上的两个站点之间是否有超文本链接， Inter 中的两个 AS 域之间是否有直接联系，两个作者之间是否有合作，这些都不能由随机选择来决定。 从 20 世纪末开始，复杂网络理论的研究已经拓展到了从物理学到社会学等众多学科中，其中 Watts 和 Strogatz 在 Nature 杂志上发表的文献 [5]探讨了复杂网络中存在“小世界” 错误 !未指定书签。 现象， Barab225。 si 和 Albert 在 Science 杂志上发表的文献 [6]探讨了随机网络中“无标度”现象，这两篇文献被认为是复杂网络研究新纪元的标志。 目前对于复杂网络的研究主要包括网络结构发现、网络拓扑建模、网络特性分析及控制 (稳定性、数据流通等 )等几个方面。 在利用复杂网络理论对实际网络拓扑结构进行研究时，用来刻画其宏观拓扑结构的网络特征量主要有度分布，平均路径长度、聚类系数、介数等等。 随着对网络性质的物理意义及数学特性的研究分析，人们发现包括 Inter 在内的许多网络有一个共同的性质，即社团特性或者称为群聚现象。 也就是说网络是由若干东北大学硕士学位论文 第 1章 绪 论 2 个“群 (group)” 或“模块 (module)“， 在群内部节点的连接非常紧密，而相对的在各个群组之间的连接则较为稀疏。 如图 所示为一个具有明显社团结构的网络，虚线圆中包含的部分就代表了网络的三个子团。 图 社团结构划分示意图 the illustration of munity structure 一般而言，社团包含 模块、类、群、组等各种含义。 例如 由大量网站社团社团组成，同一社团的各站点涉及的都是一些共同话题（见文献 [7~9]）。 在电信网络或生物网络中，也可以根据不同的性质将各节点化为不同的社团（见文献 [10~12]）。 提出网络中的社团结构，对于分析网络结构和特性至关重要。 社团结构发现在很多领域都有广泛应用，比如生物学、物理学、计算机图形学、社会学（见文献 [13~14]）等。 社团特性作为复杂网络的一个普遍现象已经在很多实际网络中得到了证实：文献[15]根据爵士乐音乐家是否曾在一个乐队演奏作为二者有联系的边，构造了一个由 jazz音乐家组成的网络，并发现在此网络中存在着明显的社团现象；文献 [16]揭示了 Inter AS 级拓扑中的社团结构与 AS 地理分布之间的关系。 目前对于复杂网络中的社团特性的研究主要集中在社团划分算法、社团结构研究及基于社团结构的建模：例如文献 [17]提出了一种基于信息编码为标准的社团划分算法，扩展了之前通常是基于模块度 [18,19]或是特征向量 [20]的社团划分算法；文献 [21]则将社团划分算法又扩展到了加权网络中。 文献 [22]发现了在很多实际网络中的社团 结构存在着叠加性和层次性；文献 [23]提出了一种基于社团的网络演化模型。 目前对于复杂网络社团结构的研究在国际上已经相对成熟，可是针对以互联网拓扑特征为基础的社团结构研究还相对不足，传统社团发现算法并不能很好的反应互联网特有的拓扑特征。 本文将根据这些不足展开对互联网特有的社团结构特征的研究。 互联网可视化研究现状 互联网的结构非常复杂，如果仅用数据表格或文字的形式来表示网络，理解起来非东北大学硕士学位论文 第 1章 绪 论 3 常 困难 ， 导致网络所包含的信息无从体现。 将复杂网络方便、直观地表示出来的最好方法是将其进行可视化。 科学计算可视化的思想是上个世纪 八十 年代美国科学基金会 （ 1CV） 提出的。 当时在科学计算中产生了大量数据，人们很难清楚知道这些数据所表示的含义以及数据之间的关系，于是提出了将它们以图形化的方式显示出来的。