Greedily Improving Our Own Centrality in A Network

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01248558
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, July 4, 2017 - 2:20:05 PM
Last modification on : Tuesday, February 26, 2019 - 10:55:14 AM
Long-term archiving on : Thursday, December 14, 2017 - 9:10:46 PM

File

Greedily Improving Our Own Cen...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

164

Files downloads

322