HierX:用于网络上距离衰减势场的高效层次化稀疏加修正算子

《PNAS Nexus》:HierX: Fast multi-scale distance-decay interaction on million-node networks

【字体: 大 中 小 】 时间:2026年09月18日 来源:PNAS Nexus 4.8

编辑推荐:

   摘要 许多跨科学领域的模型都需要在大型稀疏网络上进行全局距离衰减交互。引力模型、可达性度量、空间经济模型和网络影响过程都需要计算距离加权势场:每个位置会累积来自所有其他位置的贡献,加权因子是两个位置之间最短路径旅行成本的一个衰减函数

  

摘要

许多跨科学领域的模型都需要在大型稀疏网络上进行全局距离衰减交互。引力模型、可达性度量、空间经济模型和网络影响过程都需要计算距离加权势场:每个位置会累积来自所有其他位置的贡献,加权因子是两个位置之间最短路径旅行成本的一个衰减函数。直接计算此类聚合场需要所有成对网络成本的密集矩阵,这在时间和内存上呈二次方增长。常见的近似方法要么丢弃长距离贡献,要么在交互由网络距离而非几何邻近性主导时失效。我们提出了HierX,一种用于网络上距离衰减势场的层次化稀疏加修正算子。HierX构建了多尺度代表层,并通过显式的修正项确保每个位置对在最优分辨率下恰好贡献一次。在空间嵌入网络中常见的有界增长假设下,应用HierX的复杂度为O(n log n)。系统性基准测试确认了直到100,000个节点的准线性扩展能力。在25,000区域网络上与距离截断方法和Nystr?m低秩近似进行对比,HierX以少得多的计算量实现了5-9%的均方根误差(RMSE);Nystr?m方法在陡峭衰减核上性能严重下降。案例研究在258万节点的英国驾驶网络和177万节点的伦敦步行网络上计算了人口加权可达性:一次性层次结构构建(约1小时)产生了一个紧凑的可重用算子,随后在不到一秒内评估每个全国规模的可达性场(英国约700毫秒,伦敦约150毫秒)。提供了开源代码和工作示例。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号