Greedily Improving Our Own Centrality in A Network

Pierluigi Crescenzi (1, 2) , Gianlorenzo d'Angelo (3) , Severini Lorenzo (3) , Yllka Velaj (3)

1 Dipartimento di Ingegneria dell'Informazione [Pisa]
2 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
3 UNIVAQ - University of L'Aquila [Italy]

The closeness and the betweenness centralities are two well known measures of importance of a vertex within a given complex network. Having high closeness or betweenness centrality can have positive impact on the vertex itself: hence, in this paper we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We first prove that this problem does not admit a polynomial-time approximation scheme (unless P = NP), and we then propose a simple greedy approximation algorithm (with an almost tight approximation ratio), whose performance is then tested on synthetic graphs and real-world networks.

Domaines: Algorithme et structure de données [cs.DS]

Pierluigi Crescenzi, Gianlorenzo d'Angelo, Severini Lorenzo, Yllka Velaj. Greedily Improving Our Own Centrality in A Network. SEA 2015 - 14th International Symposium Experimental Algorithms , Jun 2015, Paris, France. pp.43-55, ⟨10.1007/978-3-319-20086-6_4⟩. ⟨hal-01248558⟩