Efficient Approximation Algorithms for Spanning Centrality

Shiqi Zhang1,2; Renchi Yang3; Jing Tang4,5; Xiaokui Xiao1; Bo Tang2

10.1145/3580305.3599323

2023

29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

PROCEEDINGS OF THE 29TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, KDD 2023

AUG 06-10, 2023

null,Long Beach,CA

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

Given a graph G, the spanning centrality (SC) of an edge.. measures the importance of e for G to be connected. In practice, SC has seen extensive applications in computational biology, electrical networks, and combinatorial optimization. However, it is highly challenging to compute the SC of all edges (AESC) on large graphs. Existing techniques fail to deal with such graphs, as they either suffer from expensive matrix operations or require sampling numerous long random walks. To circumvent these issues, this paper proposes TGT and its enhanced version TGT+, two algorithms for AESC computation that offers rigorous theoretical approximation guarantees. In particular, TGT remedies the deficiencies of previous solutions by conducting deterministic graph traversals with carefully-crafted truncated lengths. TGT+ further advances TGT in terms of both empirical efficiency and asymptotic performance while retaining result quality, based on the combination of TGT with random walks and several additional heuristic optimizations. We experimentally evaluate TGT+ against recent competitors for AESC using a variety of real datasets. The experimental outcomes authenticate that TGT+ outperforms state of the arts often by over one order of magnitude speedup without degrading the accuracy.

spanning centrality graph traversal random walk eigenvector

通讯

英语

EI ; CPCI-S

National Natural Science Foundation of China[U22B2060]

Computer Science

Computer Science, Information Systems ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods

WOS:001118896303039

Web of Science

1.National University of Singapore, Singapore
2.Southern University of Science and Technology, Hong Kong
3.Hong Kong Baptist University, Hong Kong
4.The Hong Kong University of Science and Technology (Guangzhou), China
5.The Hong Kong University of Science and Technology, Hong Kong

Shiqi Zhang,Renchi Yang,Jing Tang,et al. Efficient Approximation Algorithms for Spanning Centrality[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023.