一种基于2-Hop Labeling的进化图上可达性的快速查询方法
2025-02-28 08:25
No.1344948521278906368
技术概要
PDF全文
本技术涉及一种基于2‑Hop Labeling的进化图上可达性的快速查询方法,该方法包括以下步骤:1)对原始图进行预处理,采用Tarjan算法对每个时间片上的图中节点进行强连通分量划分,将原始图转化为由强连通分量表示的简化图结构;2)构建包含强连通分量时效表和2‑Hop Labeling可达性标签的索引;设计并构建强连通分量时效表的数据结构,用于存储强连通分量与原始图节点的对应关系,同时记录强连通分量内部节点的可达性信息;结合强连通分量时效表设计2‑Hop Labeling可达性标签的数据结构,构建完整的索引结构,用以存储和查询图中节点之间的可达性关系;3)设计基于索引的可达性快速查询方法,利用强连通分量时效表和2‑Hop Labeling可达性标签,至多合并两跳信息,实现快速可达性查询。
背景技术
进化图作为描述拓扑结构随时间动态变化的一种图模型,其本质特征在于其边和节点的频繁更新,这种动态性导致了图结构的持续演化。这种演化不仅反映了网络中元素间关系的时变性,也深刻影响了同一组节点在不同时间片下的可达性。可达性,作为图论中的一个基本概念,指的是一个节点是否能够通过某条路径到达另一个节点,它在进化图的分析中显得尤为重要。因为在实际应用中,很多关键问题都可以归结为可达性的判断,比如信息传播的范围、资源的可获取性,以及系统状态的演变等。 在生物学领域,进化图的应用尤为突出,特别是在蛋白质相互作用网络的研究中。蛋白质作为生命活动的基本执行者,它们之间的相互作用构成了复杂的网络,这些网络随着时间、环境条件以及生物体的发育阶段而发生变化。利用进化图模型,研究人员可以追踪两种蛋白质在一段时间内是否属于同一生物组织或持续参与相同的生物过程,这对于理解生命机制、疾病发生发展以及药物研发具有重要意义。例如,在疾病研究中,如果两种蛋白质在进化图上长时间保持可达,可能意味着它们共同参与了一个关键的生物途径,这个途径的异常可能与某种疾病的发生密切相关。 尽管现有的方法如HR-Index已经在处理进化图可达性查询方面取得了一定的进展,通过构建强连通分量时效表来减少空间开销并保留图的完整可达性信息,但其局限性也较为明显。当查询的节点对不在强连通分量时效表的覆盖范围内时,方法仍需回退到传统的图搜索算法,如广度优先搜索(BFS)或深度优先搜索(DFS)。这些方法在处理大规模进化图时,由于需要遍历图的拓扑结构,时间复杂度较高,导致查询效率低下,尤其是在面对大批量查询需求时,响应速度成为瓶颈。 2-Hop Labeling技术的引入,为解决大规模图上的可达性查询提供了新的思路。该技术通过在预处理阶段为每个节点生成前向和后向标签,这些标签包含了足够的信息来快速判断任意两个节点之间是否存在可达路径,而无需实际遍历图的拓扑结构。这种方法的优势在于其高效性和高可扩展性,特别是在处理静态大规模图时,能够显著提升查询速度。然而,将2-Hop Labeling直接应用于进化图仍面临挑战,主要是因为它需要有效地处理图上点和边的动态变化,以保证查询结果的准确性。 综上所述,虽然现有技术在处理进化图可达性查询方面取得了一定成就,但在应对大规模图和大批量查询时,仍存在查询时间长、处理效率低的问题。因此,探索新的方法或优化现有技术以实现大规模进化图上可达性的快速查询,是当前研究的重要方向。
实现思路
阅读余下40%
技术概要为部分技术内容,查看PDF获取完整资料
该技术已申请专利,如用于商业用途,请联系技术所有人!
技术研发人员:
窦明月  陈雪峰  冯亮
技术所属: 重庆大学
相关技术
一种服务开发方法、装置、设备及存储介质 一种服务开发方法、装置、设备及存储介质
一种高精度双层优化方法的神经网络搜索架构构建方法 一种高精度双层优化方法的神经网络搜索架构构建方法
跨总线域的设备对宿主机空间DMA访问方法及相关设备 跨总线域的设备对宿主机空间DMA访问方法及相关设备
一种客户信息定期维护方法及系统 一种客户信息定期维护方法及系统
代码发布方法、装置、计算机设备和可读存储介质 代码发布方法、装置、计算机设备和可读存储介质
一种基于统一管理平台的子应用数据获取方法及装置 一种基于统一管理平台的子应用数据获取方法及装置
利用深度学习的BIM模型错误自动检测系统 利用深度学习的BIM模型错误自动检测系统
一种基于智能反射面的室内T型走廊场景路径损耗的分析方法 一种基于智能反射面的室内T型走廊场景路径损耗的分析方法
模型评估任务处理方法及装置 模型评估任务处理方法及装置
基于大数据的异常信号智能识别方法 基于大数据的异常信号智能识别方法
技术分类
电信、广播电视和卫星传输服务 电信、广播电视和卫星传输服务
互联网软件服务 互联网软件服务
集成电路设计 集成电路设计
信息集成数字服务 信息集成数字服务
电气机械制造 电气机械制造
计算机、通信、电子设备制造 计算机、通信、电子设备制造
医药制造、生物基材料 医药制造、生物基材料
石油煤矿化学用品加工 石油煤矿化学用品加工
化学原料制品加工 化学原料制品加工
非金属矿物加工 非金属矿物加工
金属制品加工 金属制品加工
专用设备制造 专用设备制造
通用设备制造 通用设备制造
通用零部件制造 通用零部件制造
汽车制造业 汽车制造业
铁路、船舶、航天设备制造 铁路、船舶、航天设备制造
电力、热力生产和供应 电力、热力生产和供应
燃气生产和供应 燃气生产和供应
水生产和供应 水生产和供应
房屋建筑、土木工程 房屋建筑、土木工程
交通运输、仓储和邮政 交通运输、仓储和邮政
农、林、牧、渔业 农、林、牧、渔业
采矿业 采矿业
农副、食品加工 农副、食品加工
烟草、酒水加工 烟草、酒水加工
纺织皮具居家制品 纺织皮具居家制品
文教体娱加工 文教体娱加工
苏ICP备18062519号-5 © 2018-2025 【123技术园】 版权所有,并保留所有权利