检索结果-南通市图书馆

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

时态图最短路径查询方法

计算机研究与发展 2022年第2期59卷 362-375页

作者：张天明徐一恒蔡鑫伟范菁浙江工业大学计算机科学与技术学院杭州310023 浙江大学计算机科学与技术学院杭州310013

最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径... 详细信息

最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为普通图,提出了一种无损压缩方法将转化图压缩以减小图规模,采用层次划分技术将压缩有向图分解为若干个子图,并基于子图建立CTG-tree索引.CTG-tree中的节点保存相应子图内部分顶点之间的最短路径、孩子节点对应子图的边界点之间的最短路径、孩子节点对应子图的边界点与当前节点相应子图的边界点之间的最短路径信息.在线查询阶段基于构建的CTG-tree索引,提出了一种高效的最短路径查询方法.基于4个真实的时态图数据集实验结果表明,与现有方法相比,提出的方法具有更优的查询性能.

关键词：最短路径时态图压缩有向图树索引查询方法

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

面向大规模时态图的紧密子图维护算法

南京大学学报（自然科学版） 2022年第3期58卷 398-412页

作者：车鑫恺陈雅迪胡淼吴迪中山大学计算机学院广州510006 广东省大数据分析与处理重点实验室广州510006

大规模图数据中的重要顶点与层级结构对于挖掘复杂网络(如社交网络、交通网络等)中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法,对时态图中紧密度最高的前n层(k,h)-核,或满足自定义k,h值约束条件的核进行维... 详细信息

大规模图数据中的重要顶点与层级结构对于挖掘复杂网络(如社交网络、交通网络等)中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法,对时态图中紧密度最高的前n层(k,h)-核,或满足自定义k,h值约束条件的核进行维护.首先提出识别(k,h)-最大层的方法 .当时态图中出现新的边时,为了定位当前时刻可能因新加入边导致核值需要更新的顶点的范围,提出候选插入子图与部分(k,h)-核的概念及相应的识别算法.针对加边情况,提出自顶向下的时态图(k,h)-核维护加边算法,根据部分(k,h)-核识别核值受加边影响的顶点并对其核值进行更新.针对当前时刻有已经存在的边被删除的情况,提出自顶向下的时态图(k,h)-核维护删边算法,对上一时刻的(k,h)-核做最小调整以得到当前时刻的核值.从理论上证明了算法的正确性,还在真实的时态图上设计了一系列对比实验.实验结果表明,在维护层数较少时下添加边,提出的核维护算法与其他对比算法相比,加速比可达几十倍;删边时,加速比也在1~2倍.提出的算法有良好的扩展性,对于增删不同数量的边和不同的(k,h)设置,都能保持较高的效率.

关键词：大规模图核值维护紧密子图时态图

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

时态图上的密集子图查询

时态图上的密集子图查询

作者：王春花东华大学

学位级别：硕士

时态图常用于刻画现实世界中实体之间随时间变化的复杂关系。实际应用中,通常需要查询时态图中位于特定时间段内实体之间的密切交互关系。k-core和k-truss是简单图中刻画实体之间密切交互关系的主要模型,在近年得到了广泛研究。然而对... 详细信息

时态图常用于刻画现实世界中实体之间随时间变化的复杂关系。实际应用中,通常需要查询时态图中位于特定时间段内实体之间的密切交互关系。k-core和k-truss是简单图中刻画实体之间密切交互关系的主要模型,在近年得到了广泛研究。然而对时态图而言,现有研究仅限于k-core模型,且存在低效性的问题。本文针对时态图上密集子图挖掘问题进行研究,具体研究内容如下。首先,针对时态图上的k-core子图挖掘问题,提出基于最短区间历史核索引(SIHC)的查询算法,设计了高效构建SIHC索引的算法。其中,SIHC索引维护最短区间到顶点的倒排表。基于SIHC索引进行查询时,首先找到查询区间包含的最短区间,其次通过被包含的最短区间对应的顶点获取结果集。此方法避免了对顶点的无效检测,从而提高了算法效率。我们在理论上证明了基于SIHC索引进行查询的正确性。其次,针对时态图上的k-truss子图挖掘问题,提出一个基于PHT索引的基础查询算法和一个基于SIHT索引的优化查询算法,设计了高效构建索引的算法。其中,PHT索引维护边到区间的倒排表,SIHT索引维护区间到边的倒排表。基于PHT索引的查询算法,对最大k-truss子图中每条边进行检测,判断其是否满足条件。为了进一步提高算法效率,基于SIHT索引的算法可以通过查询区间得到一组最短区间,进而从SIHT索引中得到这些最短区间对应的边,避免了对边的无效检索。我们在理论上证明了基于两种索引进行查询的正确性。最后,在8个真实世界的时态图上进行了实验。对时态图上的k-core子图挖掘问题,实验结果表明基于SIHC索引的查询算法可以显著提高查询效率,最好情况下比现有最好方法快4个数量级。对时态图上的k-truss子图挖掘问题,实验结果表明基于SIHT索引的查询算法比基于PHT索引的查询算法更高效性,且SIHT索引规模更小。

关键词：时态图密集子图 k-core k-truss

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

时态图可达性处理方法研究

时态图可达性处理方法研究

作者：游宇杰华中科技大学

学位级别：硕士

近年来,互联网的高速发展导致了数据量的急速上升。不同行业的数据通过个人或者企业交织在一起产生了庞大的数据网,例如社交网络、飞机航线和生物科技之间的信息交流等,忽略一些不必要因素,这些常见的应用交互场景可以被抽象成数据结构... 详细信息

近年来,互联网的高速发展导致了数据量的急速上升。不同行业的数据通过个人或者企业交织在一起产生了庞大的数据网,例如社交网络、飞机航线和生物科技之间的信息交流等,忽略一些不必要因素,这些常见的应用交互场景可以被抽象成数据结构:图。根据图的时态属性,图可达性查询研究可以被分为两个方向。一种是静态图可达性查询,近几十年的研究主要集中在静态图上;另一种是时态图可达性查询,在这方面上相关的研究才刚刚起步。时态图可达性处理方法研究,给出了一种时态图可达性查询的解决方案。该研究将时态图可达性查询分解成两个方向:一种是结构可达性查询,忽略时态图的时间属性,主要关注结构上的可达性查询;另一种是时态可达性查询,着重于时态图的四种基本路径,即最早抵达路径、最近出发路径、最短路径和最快路径。在结构可达性查询上,时态图可达性处理方法研究分析了现有研究的不足,并且在现有算法的基础提出了优化方案;在时态可达性查询上,本研究提出了最优树模型,在该模型的基础上给出了解决时态图四种基本路径的算法,称为OPTree。在给定的时间范围内,OPTree算法从起始点出发遍历时态图,然后将时态图转换为最优树,最后回答时态图时态可达性问题。在结构可达性查询上,通过对14个真实数据集的测试,时态图可达性处理方法研究提出的优化方案比原有算法更加的高效;在时态可达性查询问题上,时态图可达性处理方法研究给出的算法比已有相关的算法能够更快的回答时态可达性。

关键词：时态图图可达性可达性查询

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

时态图中具有时间约束的图匹配问题研究

时态图中具有时间约束的图匹配问题研究

作者：绪艳霞苏州大学

学位级别：硕士

图匹配作为图计算中一种基本操作,是图数据处理领域中一项重要的研究内容,在生物学、信息学、社会学等重点领域均得到广泛的研究与应用。近年来,许多国内外学者对图匹配方法进行了广泛的研究。这些研究主要可以分为三类问题:(1)在静态... 详细信息

图匹配作为图计算中一种基本操作,是图数据处理领域中一项重要的研究内容,在生物学、信息学、社会学等重点领域均得到广泛的研究与应用。近年来,许多国内外学者对图匹配方法进行了广泛的研究。这些研究主要可以分为三类问题:(1)在静态图中查询静态子图;(2)在动态图中查询静态子图;(3)在动态图中查询动态子图。本文的研究内容属于第三类问题。在现有的研究动态图中查询动态子图的工作中,存在两点主要问题:(1)很多方法都是用一组快照来表示一个动态图,从而丢失了事件的时间关联信息。(2)返回过多的匹配结果,使用户难以在结果图中快速找到真正需要的内容。本文将动态图的定义改进为时态图并给出了时态图中具有时间约束的图匹配问题的定义。在时态图中,每一条边在特定的时间段内存在,比快照图显示出更多的关联信息。同时,本文改进了动态图匹配的形式化定义,增加了两种时间约束来过滤匹配的结果。基于上述改进,本文给出了两个解决方案。(1)基于点映射的图匹配方案TCGPM-V。该方案包含四个步骤:点映射、构建图、穷举时态图、验证时态图。(2)为提高查询效率,给出了基于边映射的图匹配方案TCGPM-E。该方案包含六个步骤:选择中心边、计算查询图半径、计算映射边集、分解数据图、边映射、穷举和验证时态图。本文在Contact、Social Pattern、SEQ、Patents等多个真实数据集上对上述方法进行了评测,同时与Ullman、VF2、Graph QL等现有方法进行了比较。实验结果表明时态图中具有时间约束的图匹配方法所得到结果的有效性明显提高。使用剪枝策略后的方法具有较高的查询效率。

关键词：图匹配时态图时间约束

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于时态图的软件变更影响分析方法研究

基于时态图的软件变更影响分析方法研究

作者：王毅恒大连海事大学

学位级别：硕士

软件开发过程包括需求分析、系统设计、编码和测试等多个阶段,而软件变更可以出现在软件开发的各个阶段中,当某一实体发生变更时,会直接或间接影响其他实体也发生变更。一个优秀的软件变更影响分析方法可以极大地降低软件开发成本,对于... 详细信息

软件开发过程包括需求分析、系统设计、编码和测试等多个阶段,而软件变更可以出现在软件开发的各个阶段中,当某一实体发生变更时,会直接或间接影响其他实体也发生变更。一个优秀的软件变更影响分析方法可以极大地降低软件开发成本,对于整个软件系统开发是非常重要的。本文通过分析当前软件变更影响分析方面的研究,总结出它们普遍存在的四大局限性,即范围局限、实体局限、联系局限以及时态局限,而后通过多种手段解决这些局限性,提出了一种基于时态图的软件变更影响分析方法。本文提出的方法是在联合范围上的分析方法,它涵盖了软件开发的全过程,它是基于数据库记录的过程级别的细粒度的动态变更影响分析。该方法站在基于规则的方法视角,建立了实体依赖图,可以很好的解决范围、实体以及联系局限;而后为了解决时态局限,将静态的实体依赖图升级为时态实体依赖图;在基本解决四大局限的情况下,本文又考虑到变更影响分析应该可以标识出实体受影响的程度,因此又在时态实体依赖图的基础之上,用权值标识程度,提出加权时态实体依赖图;最后为了模型和分析技术的持久性,为了能使得变更影响分析效率随着历史记录增加而越来越快速,引入多层网络的思想,提出拥有三层结构的变更影响分析模型。我们的模型不仅具备诸多便利条件,还可以对技术增加扩展内容,比如本文增加的影响程度计算。本文设计出相应的算法来实现变更影响分析模型,并以此为基础又设计出基于规则的影响传播追踪算法和影响程度计算算法。最后通过实验验证出算法的效果,以及时态图的优越性。

关键词：软件开发过程变更影响分析传播规则时态图多层图模型

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向时态图的频繁社区搜索算法研究

面向时态图的频繁社区搜索算法研究

作者：张培涵深圳大学

学位级别：硕士

社区挖掘是图数据挖掘的一项基本任务。在现有的图数据中,图中的边上通常都包含时间信息,例如科学家合作网络,电信话务网络,微信社交网络等等。绝大多数现有的社区挖掘算法主要针对传统的不包含时态边信息的图数据,因此无法适用于时态... 详细信息

社区挖掘是图数据挖掘的一项基本任务。在现有的图数据中,图中的边上通常都包含时间信息,例如科学家合作网络,电信话务网络,微信社交网络等等。绝大多数现有的社区挖掘算法主要针对传统的不包含时态边信息的图数据,因此无法适用于时态图数据的社区挖掘。本文主要研究时态图数据的频繁社区挖掘问题。我们的目标是找出时态图上所有的频繁社区结构。在传统图数据上已有多种社区模型,譬如k-core、clique、k-truss,k-edge connectedcomponent等。但是这些社区模型都是基于传统图数据上的模型,并不能在时态图上有效的搜索出频繁社区,为了能够在时态图上进行频繁社区搜索,我们提出了全新的频繁社区模型k-star。现实世界的时态图数据通常是极为庞大的,直接在原始的时态图上进行社区搜索是十分耗时的,为了能够高效的在时态图上搜索频繁社区,我们提出了时态图削减算法。该削减算法是通过一种弱核子图的概念来进行剪枝的。实验中该算法存在两方面的技术挑战:(1)频繁节点度的计算和(2)邻居节点的动态更新。我们提出度区间分解算法实现了对频繁节点度的快速计算和邻居节点的动态更新操作。在经过削减后的时态图中,为了进一步提升搜索算法的效率,我们又提出了强邻居剪枝算法和虚度剪枝算法。最后,我们在真实世界的时态图数据集上进行了大量的测试和对比实验。通过引入时态图削减技术和两种剪枝算法实现了在大型时态图上的高效频繁社区搜索。通过比较不同模型下的社区搜索结果,我们发现本文所提出的社区模型在搜索连接紧密的频繁社区方面有着非常好的现实效果。此外,实验结果还验证了我们所提出算法的有效性和可扩展性。

关键词：时态图社区搜索社区模型频繁社区时态图削减

SIHC: 一种高效的时态图上 k-core 查询算法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

计算机学报 2024年

作者：周军锋王春花杜明陈子阳上海立信会计金融学院信息管理学院东华大学计算机科学与技术学院

许多实体之间的关系可以建模为时态图，其中每条边都与表示其发生的时间相关联.k-core是捕获密集子图的基本模型，在近些年得到了广泛研究.给定时间区间I=[s，e]和k值，时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-c... 详细信息

许多实体之间的关系可以建模为时态图，其中每条边都与表示其发生的时间相关联.k-core是捕获密集子图的基本模型，在近些年得到了广泛研究.给定时间区间I=[s，e]和k值，时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题，现有方法是基于PHC索引(PrunedHistoricalCore-Index)的算法.对任意可能的k值，PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk，且为集合中每个顶点存储了一组时间区间，用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时，需要访问Sk集合中的所有顶点，并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点，且实际中用户查询区间对应的快照图往往比最大区间快照图小得多，基于PHC索引的查询算法存在许多无效判断，需要对大量不在结果集中的顶点进行检测，且无效检测次数随着查询区间的缩短而增多，从而导致算法效率较低. 针对该问题，本文提出一种新的索引，即最短区间历史核索引SIHC (ShortestIntervalHistoricalCoreIndex).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表，查询处理时，可基于用户给定的时间区间定位到SIHC索引中满足条件的区间，进而直接得到满足条件的k-core子图中的顶点，从而避免了基于PHC索引进行查询时所需的大量无效判断. 我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性，并设计了高效的索引构建算法. 最后，基于真实世界的时态图进行了实验，实验结果表明本文提出的算法比现有算法快1-2个数量级.

关键词：图数据管理时态图密集子图 k-core 最短k核区间

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

TFP:高效的最快路径查询处理方法

清华大学学报（自然科学版） 2020年第8期60卷 656-663页

作者：杜明郑凯文陈子阳周军锋东华大学计算机科学与技术学院上海201620 上海立信会计金融学院信息管理学院上海201620

给定时态图,最快路径查询可以得到两点之间用时最短的路径对应的时间跨度。高效回答最快路径查询可有效提升系统的易用性,增强用户黏度。然而,现有方法在处理时态图上的最快路径查询时,因其处理策略造成大量冗余操作,查询处理效率不高... 详细信息

给定时态图,最快路径查询可以得到两点之间用时最短的路径对应的时间跨度。高效回答最快路径查询可有效提升系统的易用性,增强用户黏度。然而,现有方法在处理时态图上的最快路径查询时,因其处理策略造成大量冗余操作,查询处理效率不高。该文提出3个启发式规则用于减少冗余计算,并给出了合理性证明。基于3个启发式规则,提出了一种高效的最快路径通用查询算法。该方法在多个数据集上比原有方法减少了5~8倍的可达性查询调用,显著减少了冗余计算,具有更高的查询处理效率。

关键词：时态图可达性查询最快路径查询启发式规则

维普期刊数据库