KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
DOI: 10.5445/IR/1000086341
Veröffentlicht am 12.10.2018
DOI: 10.4230/LIPIcs.ESA.2018.42

Scalable Katz ranking computation in large static and dynamic graphs

Van Der Grinten, A.; Bergamini, E.; Green, O.; Bader, D. A.; Meyerhenke, H.

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this paper, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between 1.5× and 3.5×, depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10000 edges. We provide efficient parallel CPU and GPU implementations of our al ... mehr

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2018
Sprache Englisch
Identifikator ISBN: 978-3-9597708-1-1
ISSN: 1868-8969
URN: urn:nbn:de:swb:90-863418
KITopen ID: 1000086341
Erschienen in 26th European Symposium on Algorithms, ESA 2018; Helsinki; Finland; 20 August 2018 through 22 August 2018
Verlag LZI Schloss Dagstuh, Wadern
Serie Leibniz International Proceedings in Informatics, LIPIcs ; 112
Schlagworte network analysis, Katz centrality, top-k ranking, dynamic graphs, parallel algorithms
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page