The closeness centrality is a well-known measure of importance of a vertex within a given complex network. Having high closeness centrality can have positive impact on the vertex itself: hence, in this paper we consider the optimization problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We will consider both the undirected and the directed graph cases. In both cases, we first prove that the optimization problem does not admit a polynomial-time approximation scheme (unless P = NP), and then propose a 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 closeness centrality in a network / Crescenzi, Pierluigi; D'Angelo, Gianlorenzo; Severini, Lorenzo; Velaj, Yllka. - In: ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA. - ISSN 1556-4681. - ELETTRONICO. - 11:(2016), pp. 1-32. [10.1145/2953882]
Greedily improving our own closeness centrality in a network
CRESCENZI, PIERLUIGI;
2016
Abstract
The closeness centrality is a well-known measure of importance of a vertex within a given complex network. Having high closeness centrality can have positive impact on the vertex itself: hence, in this paper we consider the optimization problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We will consider both the undirected and the directed graph cases. In both cases, we first prove that the optimization problem does not admit a polynomial-time approximation scheme (unless P = NP), and then propose a greedy approximation algorithm (with an almost tight approximation ratio), whose performance is then tested on synthetic graphs and real-world networks.File | Dimensione | Formato | |
---|---|---|---|
Crescenzi et al - 2016 ACM TKD.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
1.93 MB
Formato
Adobe PDF
|
1.93 MB | Adobe PDF | Richiedi una copia |
Crescenzi et al - Manuscript.pdf
accesso aperto
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
550.82 kB
Formato
Adobe PDF
|
550.82 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.