时序图中多约束下的路径及k个最近邻节点对问题研究

论文摘要

现实生活中的很多应用可以抽象为图里面的问题,比如基因网络中的疾病进展跟踪,可以抽象为图里面的路径查询问题;城市建设的规划,可以抽象为图里面的k个最近邻节点对查询问题;蛋白质交互网络的分析比较,可以抽象为图匹配问题等等。本文的研究主要涉及前两个问题,即路径查询和k个最近邻节点对的查询。现有的路径查询和k个最近邻节点对查询的工作中,主要存在以下两个问题:(1)现有的研究大多数是基于静态图,也有一些研究涉及到动态图上的路径查询问题,但是目前还没有动态图上的k个最近邻节点对的相关研究;(2)现有的研究没有考虑图的边上可能会有属性信息,也没有考虑用户在进行查询的时候会对时间以及边上的属性有特定的需求。本文主要考虑了以上这两点,从而提出了模型来贴切地描述现实生活中的网络,也提出了查询方法来更好地满足用户的查询需求。本文的主要贡献如下:(1)提出了属性时序图的概念,并在属性时序图上提出了多约束下的最早到达路径、最晚出发路径以及多约束下的k个最近邻节点对的查询问题;(2)提出了一组近似算法,称为两次扫描算法。第一次扫描中定义了一个时序目标函数,它由多个约束和不断变化的属性值组成,指示时序路径是否可行。第二次扫描对时序图进行搜索以找到满足用户所提约束的的路径;(3)提出了网格分解技术,与分治法相结合,加速了时序图中k个最近邻节点对的查询。其中,任意两个节点之间的多约束下的最短路径的查询算法是对两次扫描算法进行修改得到的;(4)本文在Enron、Openflights和Arxiv等多个真实数据集上对上述方法进行了评测,同时与目前最新的方法进行了比较。实验证明了本文提出的时序图中多约束下的时序路径查询方法和k个最近邻节点对查询方法的高效性和有效性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景
•   1.2 研究内容
•   1.3 研究意义
•   1.4 文章组织结构
• 第二章 相关工作
•   2.1 动态图的应用
•   2.2 动态图上的路径研究
•     2.2.1 基于结构变化的动态图上的路径研究
•     2.2.2 基于内容变化的动态图上的路径研究
•   2.3 静态图中的k个最近邻节点对
•     2.3.1 相似性连接
•     2.3.2 k个最近邻节点对
• 第三章 多约束下的时序路径
•   3.1 图建模
•     3.1.1 动态图
•     3.1.2 属性时序图
•   3.2 路径建模
•     3.2.1 时序路径
•     3.2.2 多约束下的时序路径
•     3.2.3 目标路径
•   3.3 两次扫描算法
•     3.3.1 目标函数
•     3.3.2 多约束下最早到达路径的两次扫描算法
•     3.3.3 多约束下最晚出发路径的两次扫描算法
•   3.4 实验
•     3.4.1 实验设置
•     3.4.2 实验结果和分析
•   3.5 本章小结
• 第四章 时序图上多约束下的k个最近邻节点对
•   4.1 静态图上的k个最近邻节点对建模
•   4.2 时序图上多约束下的k个最近邻节点对建模
•     4.2.1 时序图上多约束下的k个最近邻节点对
•     4.2.2 目标集合
•   4.3 网格分解法
•     4.3.1 基于分治的网格分解法
•     4.3.2 多约束下的最短路径
•     4.3.3 时间复杂度
•   4.4 实验
•     4.4.1 实验设置
•     4.4.2 实验结果和分析
•   4.5 本章小结
• 第五章 总结与展望
•   5.1 全文总结
•   5.2 工作展望
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢

文章来源

类型: 硕士论文

作者: 赵安琪

导师: 刘冠峰

关键词: 多属性,时序图,多约束

来源: 苏州大学

年度: 2019

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

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

单位: 苏州大学

分类号: O157.5;TP301.6

DOI: 10.27351/d.cnki.gszhu.2019.000769

总页数: 62

文件大小: 4245K

下载量: 14