时序图中多约束下的路径及k个最近邻节点对问题研究
发布时间：2021-12-01 17:33
现实生活中的很多应用可以抽象为图里面的问题,比如基因网络中的疾病进展跟踪,可以抽象为图里面的路径查询问题;城市建设的规划,可以抽象为图里面的k个最近邻节点对查询问题;蛋白质交互网络的分析比较,可以抽象为图匹配问题等等。本文的研究主要涉及前两个问题,即路径查询和k个最近邻节点对的查询。现有的路径查询和k个最近邻节点对查询的工作中,主要存在以下两个问题:（1）现有的研究大多数是基于静态图,也有一些研究涉及到动态图上的路径查询问题,但是目前还没有动态图上的k个最近邻节点对的相关研究;（2）现有的研究没有考虑图的边上可能会有属性信息,也没有考虑用户在进行查询的时候会对时间以及边上的属性有特定的需求。本文主要考虑了以上这两点,从而提出了模型来贴切地描述现实生活中的网络,也提出了查询方法来更好地满足用户的查询需求。本文的主要贡献如下:（1）提出了属性时序图的概念,并在属性时序图上提出了多约束下的最早到达路径、最晚出发路径以及多约束下的k个最近邻节点对的查询问题;（2）提出了一组近似算法,称为两次扫描算法。第一次扫描中定义了一个时序目标函数,它由多个约束和不断变化的属性值组成,指示时序路径是否可行。...
【文章来源】：苏州大学江苏省 211工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
图１－１多属性时序图??
路径及々个最近邻节点对问题研究?第三章多约朿下的时序路径??少。??１????１??２０「－■?＿＿■?＇?—??????■Ｉｑｌａ－ｅａ?■Ｉｑｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??一?０．８?Ｉ?ＩｂＬＡ－ＬＤ?１５?？?Ｉ?ＩｂＬＡ－ＬＤ??念?Ｉ?Ｉｔｓａ－ｌｄ?象?１?Ｉｔｓａ－ｌｄ??ｉ?ｌｏ?ｌ?｜??＂：？ＬｅｓＪ?ｌＵ＼ｍｉ??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??数据集?数据集??图３－２平均执行时间??分析：实验结果说明，两次扫描算法首先在第一次扫描过程中采用时序目标函??数来研究属性时序图中是否存在可行的时序路径，对于多约束下的最早到达路径??（多约束下的最晚出发路径）而言，如果起点（终点）的最小目标函数值大于１，那??么表明该属性时序图中从起点到终点＋存在一条可行的时序路径，因此就不需要再??进行第二次的扫描；如果起点（终点）的最小目标函数值小于等于１，则表明图中存??在可行的时序路径，因此接下来进行第二次扫描，并且利用一次扫描得到的目标函??数值以及时刻信息进行预判，从而加速第二次扫描搜索的速度。对于基础算法而言，??需要依次搜索满足单个属性上约束的时序路径，如果在所有属性的约束下查找到的??路径都－致，那么才能返回一条路径，否则，就找不到满足多个约束的路径。因此，??基础算法的查询速度相对较慢。此外，数据集Ｅｌｅｃ和Ｏｐｅｎｆｌｉｇｈｔｓ的节点数，时序边数??远小于数据集Ｅｎｒｏｎ和Ａｒｘｉｖ的节点数和时序边数，即前两个数据集的网络结构较为简??单，包含的时序边数较少，因此，算法扫描完全部的时序边花费的时间较
果。??８?丨１????１?１?８?－?－?－?■???????■Ｈｂｌａ－ｅａ?＾Ｈｂｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??＿?６?■?１?Ｉｂｌａ－ｌｄ?Ｊ?＿?６?■?Ｉ?Ｉｂｌａ－ｌｄ??毅?１?Ｉｔｓａ－ｌｄ?ｂｓ?——＇?＾?Ｉ?Ｉｔｓａ－ｌｄ??Ｓ?４?■?■?＿?运?４?？??〇?￣＾￣—?＾Ｊ—￣?〇?￣＾￣—?＾——￣??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??数据集?数据集??图３－３平均路径数量??分析：实验结果说明，两次扫描算法能比基础算法找到更多的时序路径。主要??原因在于，两次扫描算法把多个属性以及这些属性上的约束做聚合，首先进行一次??扫描来对时序图中是否存在可行路径进行判断，然后接着第二次扫描来查找满足约??束的目标路径。基础算法分别研究每个属性上的约束，对于每个属性，基础算法都??要对时序图进行一次扫描，只有当找到的多条路径一致时，才能返回结果；否则，??基础算法就找到不到路径。然而，如果存在可行路径，那么两次扫描算法总是可以??返回可行的时序路径。??３．５?本章小结??本小节在属性时序图中提出了一种新型的具有多约束的时序路径的查找模型，??它是许多基于动态图的应用的基矗然后，本小节提出了一种新颖的时序目标函数??来动态地研究时序路径是否满足相应的约束。最后，本小节提出一组两次扫描算法，??采用两次扫描来寻找ＴＰＭＣ。此外，在４个真实动态数据集上进行的实验证明了本章??提出的两次扫描算法的有效性和高效性。??２６??
【参考文献】：
期刊论文
[1]动态图数据上查询与挖掘算法的研究综述[J]. 杨雅君,高宏,李建中. 智能计算机与应用. 2013(04)
本文编号：3526766
【文章来源】：苏州大学江苏省 211工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
图１－１多属性时序图??
路径及々个最近邻节点对问题研究?第三章多约朿下的时序路径??少。??１????１??２０「－■?＿＿■?＇?—??????■Ｉｑｌａ－ｅａ?■Ｉｑｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??一?０．８?Ｉ?ＩｂＬＡ－ＬＤ?１５?？?Ｉ?ＩｂＬＡ－ＬＤ??念?Ｉ?Ｉｔｓａ－ｌｄ?象?１?Ｉｔｓａ－ｌｄ??ｉ?ｌｏ?ｌ?｜??＂：？ＬｅｓＪ?ｌＵ＼ｍｉ??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??数据集?数据集??图３－２平均执行时间??分析：实验结果说明，两次扫描算法首先在第一次扫描过程中采用时序目标函??数来研究属性时序图中是否存在可行的时序路径，对于多约束下的最早到达路径??（多约束下的最晚出发路径）而言，如果起点（终点）的最小目标函数值大于１，那??么表明该属性时序图中从起点到终点＋存在一条可行的时序路径，因此就不需要再??进行第二次的扫描；如果起点（终点）的最小目标函数值小于等于１，则表明图中存??在可行的时序路径，因此接下来进行第二次扫描，并且利用一次扫描得到的目标函??数值以及时刻信息进行预判，从而加速第二次扫描搜索的速度。对于基础算法而言，??需要依次搜索满足单个属性上约束的时序路径，如果在所有属性的约束下查找到的??路径都－致，那么才能返回一条路径，否则，就找不到满足多个约束的路径。因此，??基础算法的查询速度相对较慢。此外，数据集Ｅｌｅｃ和Ｏｐｅｎｆｌｉｇｈｔｓ的节点数，时序边数??远小于数据集Ｅｎｒｏｎ和Ａｒｘｉｖ的节点数和时序边数，即前两个数据集的网络结构较为简??单，包含的时序边数较少，因此，算法扫描完全部的时序边花费的时间较
果。??８?丨１????１?１?８?－?－?－?■???????■Ｈｂｌａ－ｅａ?＾Ｈｂｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??＿?６?■?１?Ｉｂｌａ－ｌｄ?Ｊ?＿?６?■?Ｉ?Ｉｂｌａ－ｌｄ??毅?１?Ｉｔｓａ－ｌｄ?ｂｓ?——＇?＾?Ｉ?Ｉｔｓａ－ｌｄ??Ｓ?４?■?■?＿?运?４?？??〇?￣＾￣—?＾Ｊ—￣?〇?￣＾￣—?＾——￣??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??数据集?数据集??图３－３平均路径数量??分析：实验结果说明，两次扫描算法能比基础算法找到更多的时序路径。主要??原因在于，两次扫描算法把多个属性以及这些属性上的约束做聚合，首先进行一次??扫描来对时序图中是否存在可行路径进行判断，然后接着第二次扫描来查找满足约??束的目标路径。基础算法分别研究每个属性上的约束，对于每个属性，基础算法都??要对时序图进行一次扫描，只有当找到的多条路径一致时，才能返回结果；否则，??基础算法就找到不到路径。然而，如果存在可行路径，那么两次扫描算法总是可以??返回可行的时序路径。??３．５?本章小结??本小节在属性时序图中提出了一种新型的具有多约束的时序路径的查找模型，??它是许多基于动态图的应用的基矗然后，本小节提出了一种新颖的时序目标函数??来动态地研究时序路径是否满足相应的约束。最后，本小节提出一组两次扫描算法，??采用两次扫描来寻找ＴＰＭＣ。此外，在４个真实动态数据集上进行的实验证明了本章??提出的两次扫描算法的有效性和高效性。??２６??
【参考文献】：
期刊论文
[1]动态图数据上查询与挖掘算法的研究综述[J]. 杨雅君,高宏,李建中. 智能计算机与应用. 2013(04)
本文编号：3526766
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3526766.html
