论文标题：Labeling-based centrality approaches for identifying critical edges on temporal graphs

期刊：Frontiers of Computer Science

作者：Tianming ZHANG, Jie ZHAO, Cibo YU, Lu CHEN, Yunjun GAO, Bin CAO, Jing FAN, Ge YU

发表时间：19 Oct 2023

DOI：10.1007/s11704-023-3424-y

微信链接：点击此处阅读微信文章

引用格式：

Tianming ZHANG, Jie ZHAO, Cibo YU, Lu CHEN, Yunjun GAO, Bin CAO, Jing FAN, Ge YU. Labeling-based centrality approaches for identifying critical edges on temporal graphs. Front. Comput. Sci., 2025, 19(2): 192601

阅读原文：

文章摘要

关键边识别是分析复杂网络结构、功能和行为的基石。在过去的几十年里，它引起了较大的关注。图上衡量边的重要性的中心性度量方式较多，其中边接近中心性（ECC）和边介数中心性（EBC）研究较为广泛。ECC 和 EBC 基于最短路径的概念，并且与信息流相关。这两种中心性度量方式可以应用在许多领域中，如传感器和通信网络、社交网络、工程力学和配水网络等。 已有一些工作将时态图表示为一系列图静态快照，然后分别计算每个快照的中心性。然而在这种计算方式下，快照之间的时态图路径并没有被考虑在内，高估了信息在网络中的传播。图上的时间特性对高效计算 ECC 和 EBC 提出了新的挑战。（i）时态图引入了多种最优路径，如最短时态路径、最早时态路径和最快时态路径。（ii）时态 ECC 和 EBC 计算代价高，因为它需要考虑顶点的所有时间实例之间的时态路径。

为了解决上述挑战，面向三种类型的最优时态路径，文中提出了基于标签的方法来计算 ECC 和 EBC 的值。对于 ECC 计算，我们发现来自一些时态边的最优时态路径集是相等的，因此我们提出了一种时间分割策略和两个观察结论来聚合这些边并统一计算等价边的 ECC 值。对于 EBC 计算，我们提出了时态边依赖公式和基于标签的前向-后向扫描策略。为了减少内存消耗，提高计算效率，文中提出了一种时态边压缩规则来压缩并进一步联合计算 EBC 值强相关的边。此外，考虑到每条边的 ECC 和 EBC 的计算过程相对独立，因此我们基于OpenMP 框架设计了多线程方法，以实现并行计算。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn