1 Search Results for "Borassi, Michele"

Document

DOI: 10.4230/LIPIcs.ESA.2016.20

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

Authors: Michele Borassi and Emanuele Natale

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time |E|^{1/2+o(1)} with high probability, obtaining a significant speedup with respect to the Theta(|E|) worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the k most central nodes. Furthermore, our analysis is general, and it might be extended to other settings, as well.

Cite as

Michele Borassi and Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borassi_et_al:LIPIcs.ESA.2016.20,
  author =	{Borassi, Michele and Natale, Emanuele},
  title =	{{KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.20},
  URN =		{urn:nbn:de:0030-drops-63712},
  doi =		{10.4230/LIPIcs.ESA.2016.20},
  annote =	{Keywords: Betweenness centrality, shortest path algorithm, graph mining, sampling, network analysis}
}

Refine by Author
1 Borassi, Michele
1 Natale, Emanuele

Refine by Classification

Refine by Keyword
1 Betweenness centrality
1 graph mining
1 network analysis
1 sampling
1 shortest path algorithm

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Borassi, Michele"

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

Abstract

Cite as

Thanks for your feedback!

Could not send message