面向大规模复杂网络的图布局算法

论文摘要

图布局是信息可视化领域中重要的问题之一,有效的图布局可以辅助用户更直观清晰地认识网络数据的结构,同时也有助于帮助用户发现问题,使得用户可以通过进一步的交互挖掘出其中潜在的信息。图布局算法被广泛应用于社交网络、知识图谱、深度学习等领域。目前用于网络数据的布局算法主要分为两类,基于传统力引导的算法和基于数据降维方法的算法。基于力引导的布局算法是最早被用于图布局的算法,也是目前应用最广泛的布局算法。它们通过建立物理模型来实现布局,简单且易实现,强调减少布局中的边交叉,并使得节点均匀分布;基于数据降维的算法通过将图空间的分布嵌入到低维空间来实现布局,更关注网络数据的邻域特征,力求保持图空间中节点的相对位置信息完整。随着数据规模和结构复杂性的增长,现有的图布局算法受限于其时间复杂或空间复杂度,越来越难以生成令人满意的布局。为了快速有效地构建大规模图数据的布局,本文以基于数据降维的布局算法为主要研究对象,结合可视化评估标准,针对大规模图数据如何高效布局等关键问题展开了研究,并提出了一个新的布局算法。我们在现有的基于降维方法的布局算法基础上,结合稀疏距离矩阵、负采样技术和多层次布局策略,实现了在时间复杂度与空间复杂度上均达到线性并可以扩展到大规模数据集的布局算法。本文通过在1 1种真实数据集上与7种经典有效的布局算法的对比实验,验证了我们的算法在运行时间与内存使用方面优于其他算法,并且在不同类型的数据集上均能生成有效的布局。在包含1564794个节点和56300条边的数据集上,本文算法的速度是FM3算法的1.8倍。同时本文算法仅占用3GB内存,而FM3使用了近56GB内存。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 课题背景和意义
•   1.2 国内外研究发展现状
•   1.3 本文工作
•   1.4 本文组织结构
•   1.5 本章小结
• 第2章 相关工作
•   2.1 图布局算法
•     2.1.1 基于力引导的布局算法
•     2.1.2 基于降维的布局算法
•   2.2 降维算法
•     2.2.1 线性降维算法
•     2.2.2 非线性降维算法
•   2.3 本章小结
• 第3章 基于降维技术的大规模复杂网络布局算法
•   3.1 方法框架
•     3.1.1 相关定义
•     3.1.2 基本思想
•     3.1.3 算法整体流程图
•   3.2 稀疏距离矩阵
•   3.3 负采样
•   3.4 多层次布局策略
•   3.5 复杂度分析
•   3.6 本章小结
• 第4章 实验设计与实验结果
•   4.1 数据集与对比算法
•     4.1.1 数据集
•     4.1.2 对比算法
•   4.2 评价指标
•   4.3 参数设置说明
•   4.4 实验结果
•     4.4.1 性能对比
•     4.4.2 邻域相似性对比
•     4.4.3 可视化比较
•   4.5 分析与讨论
•   4.6 本章小结
• 第5章 总结与展望
•   5.1 总结
•   5.2 展望
•   5.3 本章小结
• 参考文献
• 攻读硕士学位期间的主要研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 刘良军

导师: 陈为

关键词: 可视化,可视分析,图可视化,图布局,降维,力引导布局

来源: 浙江大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 浙江大学

分类号: O157.5;TP301.6

总页数: 64

文件大小: 4222K

下载量: 211