Greedily Improving Our Own Closeness Centrality in a Network
| Autor: | Yllka Velaj, Lorenzo Severini, Pierluigi Crescenzi, Gianlorenzo D'Angelo |
|---|---|
| Přispěvatelé: | Sagot, Marie-France, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Sistemi e Informatica (DSI), Università degli Studi di Firenze = University of Florence (UniFI), Institut de Biologie Valrose (IBV), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Gran Sasso Science Institute (GSSI), Istituto Nazionale di Fisica Nucleare (INFN), Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) General Computer Science [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Vertex cover Approximation algorithm [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences 02 engineering and technology Network theory Directed graph 01 natural sciences Network controllability Combinatorics Betweenness centrality 010201 computation theory & mathematics Approximation algorithms Graph augmentation Greedy algorithm Large networks 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Centrality Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | ACM Transactions on Knowledge Discovery from Data (TKDD) ACM Transactions on Knowledge Discovery from Data (TKDD), 2016, 11 (1), pp.1-32. ⟨10.1145/2953882⟩ ACM Transactions on Knowledge Discovery from Data (TKDD), ACM, 2016, 11 (1), pp.1-32. ⟨10.1145/2953882⟩ |
| ISSN: | 1556-4681 1556-472X |
| DOI: | 10.1145/2953882⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|