Betweenness centrality is a widely adopted metric to analyze the impact of critical nodes of graphs in several domains (social, biological, transportation, service, computer networks). Its exact computation is very demanding due to an O(nm) time complexity on a graph with n nodes and m edges. This represents an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. In this paper, we analyze the performance of a parametric two-level clustering algorithm for computing approximated values of betweenness with different kinds of graph. The analysis aims at evaluating how the properties of different complex networks impact the reduction of the number of single-source shortest-paths explorations of Brandes’ algorithm. The results confirm that one-level clustering strongly reduces the number of pivots (and consequently the computation time) on scale-free graphs, while small-world (and random) graphs need an additional level of clustering to achieve acceptable results.

Reducing pivots of approximated betweenness computation by hierarchically clustering complex networks

Zimeo E.
2017

Abstract

Betweenness centrality is a widely adopted metric to analyze the impact of critical nodes of graphs in several domains (social, biological, transportation, service, computer networks). Its exact computation is very demanding due to an O(nm) time complexity on a graph with n nodes and m edges. This represents an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. In this paper, we analyze the performance of a parametric two-level clustering algorithm for computing approximated values of betweenness with different kinds of graph. The analysis aims at evaluating how the properties of different complex networks impact the reduction of the number of single-source shortest-paths explorations of Brandes’ algorithm. The results confirm that one-level clustering strongly reduces the number of pivots (and consequently the computation time) on scale-free graphs, while small-world (and random) graphs need an additional level of clustering to achieve acceptable results.
978-331972149-1
Algorithms, Electric network analysis, Influential spreaders
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12070/13051
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact