Efficient Approximation Algorithms for Spanning Centrality

Shiqi Zhang, Renchi Yang, Jing Tang, Xiaokui Xiao*, Bo Tang*

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


Given a graph G, the spanning centrality (SC) of an edge e 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.

Original languageEnglish
Title of host publicationKDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
EditorsAmbuj Singh, Yizhou Sun
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Print)9798400701030
Publication statusPublished - Aug 2023
Event29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 - Long Beach, United States
Duration: 6 Aug 202310 Aug 2023

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining


Conference29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023
Country/TerritoryUnited States
CityLong Beach
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • eigenvector
  • graph traversal
  • random walk
  • spanning centrality


Dive into the research topics of 'Efficient Approximation Algorithms for Spanning Centrality'. Together they form a unique fingerprint.

Cite this