License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.42
URN: urn:nbn:de:0030-drops-95055
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9505/
Go to the corresponding LIPIcs Volume Portal

van der Grinten, Alexander ; Bergamini, Elisabetta ; Green, Oded ; Bader, David A. ; Meyerhenke, Henning

Scalable Katz Ranking Computation in Large Static and Dynamic Graphs

pdf-format:
LIPIcs-ESA-2018-42.pdf (0.5 MB)

Abstract

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 x and 3.5 x, 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 algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

BibTeX - Entry

@InProceedings{vandergrinten_et_al:LIPIcs:2018:9505,
  author =	{Alexander van der Grinten and Elisabetta Bergamini and Oded Green and David A. Bader and Henning Meyerhenke},
  title =	{{Scalable Katz Ranking Computation in Large Static and Dynamic Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9505},
  URN =		{urn:nbn:de:0030-drops-95055},
  doi =		{10.4230/LIPIcs.ESA.2018.42},
  annote =	{Keywords: network analysis, Katz centrality, top-k ranking, dynamic graphs, parallel algorithms}
}

Keywords: network analysis, Katz centrality, top-k ranking, dynamic graphs, parallel algorithms
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI