图聚集算法与聚集图质量评价算法研究

论文摘要

现实世界中存在大量用图建模并表示的数据,如道路网络、社会网络、生物网络、Web图等,其中顶点表示实体,边表示实体之间的关系。随着图模型的广泛应用,图数据规模也越来越大,往往一个图中就包含有上百万个顶点和上千万条边。在这些大规模的图数据中,隐含了大量有用的信息。但是,图数据规模的增大,也使用户无法通过视觉观察或者简单的手工操作了解其内部有用的信息。因此把大型图数据集总结成精简的形式是迫切需要的。近年来,人们开始研究如何将一个大规模图的顶点聚集成若干组,并以这些顶点子集为新的顶点,构造一个简洁并能有效反映原始图的结构和属性信息的小规模图,叫做“聚集图”,从而帮助用户理解和分析原始图中的有用信息,这个过程就叫做“图聚集”。图聚集在图数据管理、分析和可视化中发挥着重要作用。图聚集方面现有研究结果还很少,也很不系统。其主要不足之处在于:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强;4)算法忽略聚集图中顶点之间的关系。针对现有图聚集技术存在的问题,本文提出一种有向图上时间复杂性为O（|V|log|V| + |E|）的新型图聚集算法,其中|V|和|E|分别为输入图的顶点数和边数。该算法使用局部敏感哈希（Locality Sensitive Hashing简称LSH）技术和基于熵的顶点划分技术,不仅有效保证了算法时间复杂性,也保证了聚集图的质量。为了衡量聚集图的质量,本文进一步定义了新的聚集图质量评价标准,全面地刻画了聚集图的多样性、覆盖性、简洁性和实用性。对比已有的聚集图质量评价标准,本文提出的聚集图质量评价算法更关注聚集图在实际应用中的意义。本文在真实数据集上进行实验,证实了算法的有效性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景及研究的目的和意义
• 1.2 国内外研究现状
• 1.2.1 图聚集算法研究现状
• 1.2.2 与图聚集相关的其它图问题研究现状
• 1.2.3 质量评价算法研究现状
• 1.3 本文的主要研究工作
• 1.4 本文的结构
• 第2章 问题描述
• 2.1 本文所研究的图聚集问题
• 2.2 本文所研究的图聚集问题形式化定义
• 2.2.1 聚集图的形式化定义
• 2.2.2 最优化目标
• 2.2.3 本文所研究的图聚集问题的形式化定义
• 2.3 本文所采用的数据模型
• 2.3.1 哈希表
• 2.3.2 用于细分顶点分组的数据结构
• 2.4 本章小结
• 第3章 图聚集算法
• 3.1 引言
• 3.2 算法思想及框架
• 3.3 基于顶点属性相似性聚集
• 3.3.1 算法思想及理论基础
• 3.3.2 算法描述
• 3.4 基于顶点邻居相似性聚集
• 3.4.1 选择哪一个组进行分裂
• 3.4.2 如何对选定组进行分裂
• 3.4.3 算法描述
• 3.5 算法复杂性分析
• 3.6 实验结果及分析
• 3.6.1 实验设计
• 3.6.2 实验结果及分析
• 3.7 本章小结
• 第4章 聚集图质量评价算法
• 4.1 引言
• 4.2 研究动机
• 4.3 聚集图质量评价
• 4.3.1 聚集图的多样性
• 4.3.2 聚集图的覆盖性
• 4.3.3 聚集图的简洁性
• 4.3.4 聚集图的实用性
• 4.3.5 聚集图质量函数
• 4.4 算法描述
• 4.5 实验设计与分析
• 4.5.1 实验设计
• 4.5.2 实验结果及分析
• 4.6 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文及其它成果
• 致谢