Centrality metrics are among the main tools in social network analysis. Being central for a user of a network leads to several benefits to the user: central users are highly influential and play key roles within the network. Therefore, the optimization problem of increasing the centrality of a network user recently received considerable attention. Given a network and a target user v, the centrality maximization problem consists in creating k new links incident to v in such a way that the centrality of v is maximized, according to some centrality metric. Most of the algorithms proposed in the literature are based on showing that a given centrality metric is monotone and submodular with respect to link addition. However, this property does not hold for several shortest-path based centrality metrics if the links are undirected. In this paper we study the centrality maximization problem in undirected networks for one of the most important shortestpath based centrality measures, the coverage centrality. We provide several hardness and approximation results. We first show that the problem cannot be approximated within a factor greater than 1 − 1/e, unless P = NP, and, under the stronger gap-ETH hypothesis, the problem cannot be approximated within a factor better than 1/no(1), where n is the number of users. We then propose two greedy approximation algorithms, and show that, by suitably combining them, we can guarantee an approximation factor of Ω(1/ √ n). We experimentally compare the solutions provided by our approximation algorithm with optimal solutions computed by means of an exact IP formulation. We show that our algorithm produces solutions that are very close to the optimum

Coverage Centrality Maximization in Undirected Networks

D'Angelo G;
2019

Abstract

Centrality metrics are among the main tools in social network analysis. Being central for a user of a network leads to several benefits to the user: central users are highly influential and play key roles within the network. Therefore, the optimization problem of increasing the centrality of a network user recently received considerable attention. Given a network and a target user v, the centrality maximization problem consists in creating k new links incident to v in such a way that the centrality of v is maximized, according to some centrality metric. Most of the algorithms proposed in the literature are based on showing that a given centrality metric is monotone and submodular with respect to link addition. However, this property does not hold for several shortest-path based centrality metrics if the links are undirected. In this paper we study the centrality maximization problem in undirected networks for one of the most important shortestpath based centrality measures, the coverage centrality. We provide several hardness and approximation results. We first show that the problem cannot be approximated within a factor greater than 1 − 1/e, unless P = NP, and, under the stronger gap-ETH hypothesis, the problem cannot be approximated within a factor better than 1/no(1), where n is the number of users. We then propose two greedy approximation algorithms, and show that, by suitably combining them, we can guarantee an approximation factor of Ω(1/ √ n). We experimentally compare the solutions provided by our approximation algorithm with optimal solutions computed by means of an exact IP formulation. We show that our algorithm produces solutions that are very close to the optimum
978-1-57735-809-1
Centrality measures, GRAPHS
File in questo prodotto:
File Dimensione Formato  
2019_33rdAAAIConf_33_DAngelo.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Accesso gratuito
Dimensione 1.27 MB
Formato Adobe PDF
1.27 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/3268
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 4
social impact