Greedily Improving Our Own Centrality in A Network - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

Greedily Improving Our Own Centrality in A Network

(1, 2) , (3) , (3) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
Greedily Improving Our Own Centrality in A Network.pdf (163.35 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01248558 , version 1 (04-07-2017)

Identifiers

Cite

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⟩

Collections

INRIA INRIA2
71 View
443 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More