1 Search Results for "Slobbe, Arie"

Document

DOI: 10.4230/LIPIcs.SEA.2017.23

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
1 Bergamini, Elisabetta
1 Meyerhenke, Henning
1 Ortmann, Mark
1 Slobbe, Arie

Refine by Classification

Refine by Keyword
1 Graph algorithms
1 distances
1 dynamic algorithms
1 shortest paths

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Slobbe, Arie"

Faster Betweenness Centrality Updates in Evolving Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message