-
题名基于树分解的时序最短路径计数查询算法
- 1
-
-
作者
李源
林秋兰
陈安之
杨国利
宋威
王国仁
-
机构
北方工业大学信息学院
北京大数据先进技术研究院
北京理工大学计算机学院
-
出处
《计算机应用》
CSCD
北大核心
2024年第8期2446-2454,共9页
-
基金
国家自然科学基金资助项目(61902004,72201275,61977001)。
-
文摘
最短路径计数是图计算中的一个重要研究问题,旨在查询顶点间的最短路径数,在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图,但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比,时序图增加了时间信息,结构更复杂,在查询顶点间的路径数时必须考虑边的激活时间,因此静态图中最短路径计数方法不再适用于时序图,并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题,提出一种基于树分解构建TG-TL(Temporal Graph-Tree Label)索引的方法。该方法包含构建索引和在线查询两个阶段,构建索引阶段根据时序图的属性设计时序树分解算法,将时序图转化为树结构;然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法;在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明,与基于TG-base(Temporal Graph-base)索引的查询算法相比,所提算法在查询效率上至少提升了61%,因此所提算法在时序图最短路径计数问题上具有高效性和有效性。
-
关键词
时序图
树分解
索引
最短路径
最短路径计数
-
Keywords
temporal graph
tree decomposition
index
shortest path
shortest path counting
-
分类号
TP311.1
[自动化与计算机技术—计算机软件与理论]
-
-
题名路状网络的最优连接及最优定位问题
- 2
-
-
作者
于紫薇
刘彦佩
-
机构
北方交通大学理学院
-
出处
《北方交通大学学报》
CSCD
北大核心
2001年第6期103-108,共6页
-
文摘
数最短路问题在社会生活中有着广泛的应用 .在讨论了相同形状网络的连接及中位与中心问题的基础上 ,进一步研究基于不同长度的路状网络的连接及连接后新网络的中位与中心问题 .
-
关键词
数最短路
路状网络
最优连接
最优定位
中位
中心
道路结构
-
Keywords
shortest path counting problem
optimization
location
-
分类号
O157.5
[理学—数学]
-
-
题名格子状网络的最优连接及最优定位问题
- 3
-
-
作者
于紫薇
刘彦佩
-
机构
北方交通大学数学系
-
出处
《曲阜师范大学学报（自然科学版）》
CAS
2002年第2期25-28,共4页
-
文摘
数最短路问题 (SPCP)在社会生活中有着广泛的应用 .OyamaT和TaguchiA(1991)讨论了相同形状的格子网络的连接及中位与中心问题 .该文进一步研究基于不同形状的格子网络的连接及连接后新网络的中位与中心问题 .从而 ,OyamaT和TaguchiA(1991)所讨论的作为该文的特殊情形 .
-
关键词
格子状网络
最优连接
最优定位问题
数最短路问题
SPCP
-
Keywords
shortest path counting problem
optimalization
location
-
分类号
O157.5
[理学—数学]
-
