Efficient Exact and Approximate Betweenness Centrality Computation for Temporal Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Betweenness centrality of a vertex in a graph evaluates how often the vertex occurs in the shortest paths. It is a widely used metric of vertex importance in graph analytics. While betweenness centrality on static graphs has been extensively investigated, many real-world graphs are time-varying and modeled as temporal graphs. Examples include social networks and telecommunication networks, where a relationship between two vertices occurs at a specific time. Hence, in this paper, we target efficient methods for temporal betweenness centrality computation. We firstly propose an exact algorithm with the new notion of time instance graph, based on which, we derive a temporal dependency accumulation theory for iterative computation. To reduce the size of the time instance graph and improve the efficiency, we propose an additional optimization, which compresses the time instance graph with equivalent vertices and edges, and extends the dependency theory to the compressed graph. Since it is theoretically complex to compute temporal betweenness centrality, we further devise a probabilistically guaranteed approximate method to handle massive temporal graphs. Extensive experimental results on real-world temporal networks demonstrate the superior performance of the proposed methods. In particular, our exact and approximate methods outperform the state-of-the-art methods by up to two and five orders of magnitude, respectively.

Author Affiliations

@inproceedings{zhang2024efficient,
  title = {Efficient Exact and Approximate Betweenness Centrality Computation for Temporal Graphs},
  author = {Zhang, Tianming and Gao, Yunjun and Zhao, Jie and Chen, Lu and Jin, Lu and Yang, Zhengyi and Cao, Bin and Fan, Jing},
  series = {WWW '24},
  url = {http://dx.doi.org/10.1145/3589334.3645438},
  doi = {10.1145/3589334.3645438},
  booktitle = {Proceedings of the ACM Web Conference 2024},
  publisher = {ACM},
  year = {2024},
  month = May,
  pages = {2395-2406},
  collection = {WWW '24}
}