Approximating Temporal Katz Centrality with Monte Carlo Methods

RAIDS Lab Authors

Zhengyi Yang

(corresponding author)

Director

Details

Research Area

Tags

Resources

Abstract

Graphs have long served as fundamental data models across various disciplines such as data mining, social media analysis, and knowledge management. In real-world applications, interactions between nodes often evolve over time, necessitating the use of temporal graphs. Centrality measures are pivotal in graph analysis for identifying key nodes. Specifically, Temporal Katz Centrality (TKC) has garnered significant attention in recent years for its ability to measure node influence in temporal graphs. TKC evaluates the influence of nodes by considering all walks originating from a node, where contributions are weighted based on a user-specified time decay factor. This approach captures temporal dynamics by incorporating both the timing of interactions and the intervals between them, offering a comprehensive assessment of node importance over time. However, computing TKC in large temporal graphs is computationally intensive due to the requirement to traverse all edges and update centrality values along temporal paths. To address this challenge, this paper proposes an efficient Monte Carlo approximation method for TKC. This approach employs random sampling via Simple Random Walk and Alpha Walk to estimate TKC values. The paper rigorously proves the asymptotic consistency of the method using the Law of Large Numbers and Central Limit Theorem, ensuring that estimated TKC values converge to true TKC values as the sample size increases. Experiments conducted on six real-world temporal graph datasets demonstrate the effectiveness of the proposed approximation methods. Under the same running time, the Alpha walk outperforms other methods on large temporal graphs, exhibiting the lowest mean relative error and highest precision.

Author Affiliations

@inproceedings{yan2024approximating,
  title = {Approximating Temporal Katz Centrality with Monte Carlo Methods},
  author = {Yan, Haonan and Yang, Zhengyi and Zhang, Tianming and Wen, Dong and Luo, Qi and Ukey, Nimish},
  editor = {Zhang, Wenjie and Tung, Anthony and Zheng, Zhonglong and Yang, Zhengyi and Wang, Xiaoyang and Guo, Hongjie},
  booktitle = {Web and Big Data. APWeb-WAIM 2024 International Workshops},
  year = {2025},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {3--16},
  isbn = {978-981-96-0055-7}
}