2 Search Results for "Bergamini, Elisabetta"


Document
Scalable Katz Ranking Computation in Large Static and Dynamic Graphs

Authors: Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, and Henning Meyerhenke

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


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.

Cite as

Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, and Henning Meyerhenke. Scalable Katz Ranking Computation in Large Static and Dynamic Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{vandergrinten_et_al:LIPIcs.ESA.2018.42,
  author =	{van der Grinten, Alexander and Bergamini, Elisabetta and Green, Oded and Bader, David A. and Meyerhenke, Henning},
  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 =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.42},
  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}
}
Document
Faster Betweenness Centrality Updates in Evolving Networks

Authors: Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)


Abstract
Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today’s networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms. Our experimental evaluation on a variety of real-world networks reveals that our approach is significantly faster than the current state-of-the-art dynamic algorithms, approximately by one order of magnitude on average.

Cite as

Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe. Faster Betweenness Centrality Updates in Evolving Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bergamini_et_al:LIPIcs.SEA.2017.23,
  author =	{Bergamini, Elisabetta and Meyerhenke, Henning and Ortmann, Mark and Slobbe, Arie},
  title =	{{Faster Betweenness Centrality Updates in Evolving Networks}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.23},
  URN =		{urn:nbn:de:0030-drops-76093},
  doi =		{10.4230/LIPIcs.SEA.2017.23},
  annote =	{Keywords: Graph algorithms, shortest paths, distances, dynamic algorithms}
}
  • Refine by Author
  • 2 Bergamini, Elisabetta
  • 2 Meyerhenke, Henning
  • 1 Bader, David A.
  • 1 Green, Oded
  • 1 Ortmann, Mark
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Parallel algorithms

  • Refine by Keyword
  • 1 Graph algorithms
  • 1 Katz centrality
  • 1 distances
  • 1 dynamic algorithms
  • 1 dynamic graphs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail