复杂网络的可视化显示

发布时间：2017-10-26 18:34

  本文关键词：复杂网络的可视化显示

  更多相关文章： 复杂网络可视化 压缩算法 PageRank 社区挖掘 GraphLab

【摘要】：实际社会中的复杂系统要么以复杂网络的形式存在,要么可以通过某种形式的转换而变为复杂网络。而传统的利用数字和表格的形式来组织数据的方式,使得人们很难对复杂网络有整体上的认识。复杂网络可视化技术可以有效地展现网络的结构,使得人们可以从中及时获取有用的信息来加以利用。而由于信息社会的高速发展,所产生的数据也越来越多,复杂网络的规模在急剧增长,严格按照布局算法来对网络进行可视化变得越来越困难。一方面由于计算机性能的限制,导致其在应对大量的数据时不能有效地对节点进行布局,导致大量节点的重叠和边的交叉;另一方面,在结果展示的图上节点太多,会严重影响人们的观察,也就无法从其中获取任何有用信息了。因此,诞生了可视化压缩算法。可视化压缩算法的目标就是对网络的节点和边进行删除操作,这样做的目的是为了更好地展示网络的拓扑结构,便于人们更好地去理解它,以挖掘网络所包含的有用信息。众所周知,实际社会中的复杂网络的度分布都比较好地满足幂律分布,即大部分节点的度比较小,只有极少部分节点的度比较大。而这些具有较较小度的节点中,大部分的节点都属于不那么重要的节点,其存在与否对网络的整体拓扑结构影响不大。可视化压缩算法的做法就是删除重要程度不高的节点。本文设计了一个复杂网络压缩算法,该压缩算法的主要操作有节点的合并和节点的删除。节点的删除操作所依据的是节点的重要性程度,本文采用PageRank值来表示节点的重要性程度。复杂网络普遍存在社区结构的特性,所以节点的重要性程度也具有相对性。因此算法先利用基于标签传播的RAK社区挖掘算法对网络进行社区划分,然后以社区为单位来对节点进行删除。节点删除时,考虑到原网络的连通性,还要适当地进行边的添加。由于复杂网络的节点规模巨大,为了满足快速和准确的要求,采用了GraphLab并行框架。本文实现了上述的复杂网络压缩算法,且其中的PageRank值的计算及社区划分都是基于GraphLab框架的实现。通过在实际数据集上进行测试,来验证在GraphLab框架下的PageRank算法和RAK算法的准确性及高效性,同时测试本文的压缩算法。通过检验压缩后的网络的度分布,发现其仍满足幂律的特性,说明了压缩算法的有效性。最后展示了压缩效果。
【关键词】：复杂网络可视化 压缩算法 PageRank 社区挖掘 GraphLab
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 绪论10-19
• 1.1 研究背景与意义10-11
• 1.2 国内外研究现状11-17
• 1.3 本文的主要研究内容及结构安排17-19
• 第二章 复杂网络分析研究19-34
• 2.1 复杂网络简介19-22
• 2.2 复杂网络的统计特征22-24
• 2.3 复杂网络社区挖掘方法24-26
• 2.4 复杂网络中的节点重要性程度26-30
• 2.5 GraphLab并行框架30-32
• 2.5.1 GraphLab的数据模型31-32
• 2.5.2 GraphLab的执行模型32
• 2.6 本章小结32-34
• 第三章 基于GraphLab的PageRank算法及RAK算法实现34-53
• 3.1 问题提出34
• 3.2 基于GraphLab的PageRank算法的实现34-41
• 3.2.1 基本思路34-35
• 3.2.2 具体实现35-39
• 3.2.3 实验结果及分析39-41
• 3.3 基于GraphLab的RAK社区挖掘算法的实现41-51
• 3.3.1 基本思路41-43
• 3.3.2 具体实现43-48
• 3.3.3 实验结果及分析48-51
• 3.4 本章小结51-53
• 第四章 基于PageRank和RAK社区划分的可视化压缩算法53-68
• 4.1 问题描述及目标53
• 4.2 算法设计53-59
• 4.3 实验结果及分析59-66
• 4.5 本章总结66-68
• 第五章 总结与展望68-70
• 5.1 本文总结68-69
• 5.2 后续工作展望69-70
• 致谢70-71
• 参考文献71-74
• 攻读硕士学位期间取得的成果74-75

【共引文献】

中国期刊全文数据库 前10条

1 蒋宗礼;李宪雷;徐学可;;基于主题Hub值的元搜索[J];北京工业大学学报;2009年03期

2 叶琳莉;林嵩凯;;基于Web结构挖掘算法的网站构建[J];电脑知识与技术;2008年34期

3 王梅;;搜索引擎中的web链接算法研究与改进[J];电脑知识与技术;2009年24期

4 谭涛;;高效的动态脚本网页关联性挖掘算法研究[J];电脑知识与技术;2012年13期

5 李江;殷之明;;链接分析研究综述[J];大学图书馆学报;2008年02期

6 王艳辉,吴斌,王柏;电信社群网络静态几何性质分析研究[J];复杂系统与复杂性科学;2005年02期

7 段晓东;王存睿;刘向东;张庆灵;;基于网络权重的多社团网络结构划分算法[J];复杂系统与复杂性科学;2009年03期

8 谭丽华;董毅明;李林红;;互联网群体智能的涌现[J];管理学报;2010年12期

9 邱均平,张洋;网络信息计量学综述[J];高校图书馆工作;2005年01期

10 肖国强;张芳;;一个元搜索引擎的设计与实现[J];微处理机;2008年04期

，

本文编号：1099948