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.
Greedily improving our own centrality in a network / Crescenzi, Pierluigi; D’Angelo, Gianlorenzo; Severini, Lorenzo; Velaj, Yllka. - STAMPA. - 9125:(2015), pp. 43-55. (Intervento presentato al convegno 14th International Symposium on Experimental Algorithms, SEA 2015 nel 2015) [10.1007/978-3-319-20086-6_4].
Greedily improving our own centrality in a network
CRESCENZI, PIERLUIGI;
2015
Abstract
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.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.