The betweenness is a well-known measure of centrality of a node in a network. We consider the problem of determining how much a node can increase its betweenness centrality by creating a limited amount of new edges incident to it. If the graph is directed, this problem does not admit a polynomial-time approximation scheme (unless P=NP) and a simple greedy approximation algorithm guarantees an almost tight approximation ratio. In this paper we focus on the undirected graph case: we show that also in this case the problem does not admit a polynomial-time approximation scheme (unless P=NP). Moreover, we show that, differently from the directed case, the greedy algorithm can have an unbounded approximation ratio. In order to test the practical performance of the greedy algorithm, we experimentally measured its efficiency in term of ranking improvement, comparing it with another algorithm that simply adds edges to the nodes that have highest betweenness. Our experiments show that the greedy algorithm adds only few edges in order to increase the betweenness of a node and to reach the top positions in the ranking. Moreover, the greedy algorithm outperforms the second approach.

On the Maximum Betweenness Improvement Problem

D'Angelo G;
2016

Abstract

The betweenness is a well-known measure of centrality of a node in a network. We consider the problem of determining how much a node can increase its betweenness centrality by creating a limited amount of new edges incident to it. If the graph is directed, this problem does not admit a polynomial-time approximation scheme (unless P=NP) and a simple greedy approximation algorithm guarantees an almost tight approximation ratio. In this paper we focus on the undirected graph case: we show that also in this case the problem does not admit a polynomial-time approximation scheme (unless P=NP). Moreover, we show that, differently from the directed case, the greedy algorithm can have an unbounded approximation ratio. In order to test the practical performance of the greedy algorithm, we experimentally measured its efficiency in term of ranking improvement, comparing it with another algorithm that simply adds edges to the nodes that have highest betweenness. Our experiments show that the greedy algorithm adds only few edges in order to increase the betweenness of a node and to reach the top positions in the ranking. Moreover, the greedy algorithm outperforms the second approach.
Betweenness centrality; approximation algorithms; graph augmentation
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: https://hdl.handle.net/20.500.12571/1364
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 10
social impact