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.
Type de document :
Communication dans un congrès
Evripidis Bampis. SEA 2015 - 14th International Symposium Experimental Algorithms , Jun 2015, Paris, France. Springer, Lecture Notes in Computer Science, Springer-Verlag, 9125, pp.43-55, 2015, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-20086-6_4〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248558
Contributeur : Marie-France Sagot <>
Soumis le : mardi 4 juillet 2017 - 14:20:05
Dernière modification le : mercredi 11 avril 2018 - 01:53:41
Document(s) archivé(s) le : jeudi 14 décembre 2017 - 21:10:46

Fichier

Greedily Improving Our Own Cen...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierluigi Crescenzi, Gianlorenzo D'Angelo, Severini Lorenzo, Yllka Velaj. Greedily Improving Our Own Centrality in A Network. Evripidis Bampis. SEA 2015 - 14th International Symposium Experimental Algorithms , Jun 2015, Paris, France. Springer, Lecture Notes in Computer Science, Springer-Verlag, 9125, pp.43-55, 2015, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-20086-6_4〉. 〈hal-01248558〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

108