Efficient Parallel Algorithm for Approximating Betweenness Centrality Values of Top k Nodes in Large Graphs

TOROSLU İ. H., Suleymanli G.

Concurrency and Computation: Practice and Experience, cilt.37, sa.4-5, 2025 (SCI-Expanded, Scopus) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 37 Sayı: 4-5
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1002/cpe.70022
  • Dergi Adı: Concurrency and Computation: Practice and Experience
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Anahtar Kelimeler: betweenness centrality, community detection algorithms, heuristics, Louvain clustering, multiprocessing, parallelization
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Computing betweenness centrality (BC) in large graphs is crucial for various applications, including telecommunications, social, and biological networks. However, the huge size of the data presents significant challenges. In this paper, we introduce a novel approximate approach for efficiently extracting top k BC nodes by combining the Louvain community detection algorithm with Brandes' algorithm. Our method significantly enhances the runtime efficiency of the traditional Brandes' algorithm while preserving accuracy across both synthetic and real-world datasets. Additionally, our approach is suitable for parallelization, further improving its efficiency. Experimental results confirm the effectiveness of our method for large and sparse graphs.