Greedily Improving Our Own Closeness Centrality in a Network

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.
Type de document :
Article dans une revue
ACM Transactions on Knowledge Discovery from Data (TKDD), ACM, 2016, 11 (1), pp.1-32. 〈10.1145/2953882〉
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01390134
Contributeur : Marie-France Sagot <>
Soumis le : jeudi 29 juin 2017 - 11:11:12
Dernière modification le : jeudi 3 mai 2018 - 13:08:47
Document(s) archivé(s) le : jeudi 18 janvier 2018 - 02:43:52

Fichier

crescenzi2016.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Collections

Citation

Pierluigi Crescenzi, Gianlorenzo D'Angelo, Lorenzo Severini, Yllka Velaj. Greedily Improving Our Own Closeness Centrality in a Network. ACM Transactions on Knowledge Discovery from Data (TKDD), ACM, 2016, 11 (1), pp.1-32. 〈10.1145/2953882〉. 〈hal-01390134〉

Partager

Métriques

Consultations de la notice

258

Téléchargements de fichiers

189