Labeling-based centrality approaches for identifying critical edges on temporal graphs  

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

机构地区：[1]School of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China [2]School of Computer Science and Technology,Zhejiang University,Hangzhou 310013,China [3]Department of Computer Science,Northeastern University,Shenyang 110819,China

出　　处：《Frontiers of Computer Science》2025年第2期89-104,共16页计算机科学前沿(英文版)

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.62302451 and 62276233);the Natural Science Foundation of Zhejiang Province of China(No.LQ22F020018);the Key Research Project of Zhejiang Province of China(No.2023C01048).

摘　　要：Edge closeness and betweenness centralities are widely used path-based metrics for characterizing the importance of edges in networks.In general graphs,edge closeness centrality indicates the importance of edges by the shortest distances from the edge to all the other vertices.Edge betweenness centrality ranks which edges are significant based on the fraction of all-pairs shortest paths that pass through the edge.Nowadays,extensive research efforts go into centrality computation over general graphs that omit time dimension.However,numerous real-world networks are modeled as temporal graphs,where the nodes are related to each other at different time instances.The temporal property is important and should not be neglected because it guides the flow of information in the network.This state of affairs motivates the paper’s study of edge centrality computation methods on temporal graphs.We introduce the concepts of the label,and label dominance relation,and then propose multi-thread parallel labeling-based methods on OpenMP to efficiently compute edge closeness and betweenness centralities w.r.t.three types of optimal temporal paths.For edge closeness centrality computation,a time segmentation strategy and two observations are presented to aggregate some related temporal edges for uniform processing.For edge betweenness centrality computation,to improve efficiency,temporal edge dependency formulas,a labeling-based forward-backward scanning strategy,and a compression-based optimization method are further proposed to iteratively accumulate centrality values.Extensive experiments using 13 real temporal graphs are conducted to provide detailed insights into the efficiency and effectiveness of the proposed methods.Compared with state-ofthe-art methods,labeling-based methods are capable of up to two orders of magnitude speedup.

关 键 词：temporal graph closeness centrality between-ness centrality temporal path 

分 类 号：O15[理学—数学]