Navigability is a distinctive features of graphs associated with artificial or natural systems whose primary goal is the transportation of information or goods. We say that a graph G is navigable when an agent is able to efficiently reach any target node in G by means of local routing decisions. In a social network navigability translates to the ability of reaching an individual through personal contacts. Graph navigability is well-studied, but a fundamental question is still open: why are some individuals more likely than others to be reached via short, friend-of-a-friend, communication chains? In this article we answer the question above by proposing a novel centrality metric called the potential gain, which, in an informal sense, quantifies the easiness at which a target node can be reached. We define two variants of the potential gain, called the geometric and the exponential potential gain, and present fast algorithms to compute them. The geometric and the potential gain are the first instances of a novel class of composite centrality metrics, i.e., centrality metrics which combine the popularity of a node in G with its similarity to all other nodes. As shown in previous studies, popularity and similarity are two main criteria which regulate the way humans seek for information in large networks such as Wikipedia. We give a formal proof that the potential gain of a node is always equivalent to the product of its degree centrality (which captures popularity) and its Katz centrality (which captures similarity).

Potential gain as a centrality measure / P. De Meo, M. Levene, A. Provetti - In: WI '19: IEEE/WIC/ACM International Conference on Web Intelligence / [a cura di] P. Barnaghi, G. Gottlob, Y. Manolopoulos, T. Tzouramanis, A. Vakali. - [s.l] : ACM, 2019. - ISBN 9781450369343. - pp. 418-422 (( Intervento presentato al 19. convegno IEEE/WIC/ACM International Conference on Web Intelligence tenutosi a Thessaloniki nel 2019 [10.1145/3350546.3352559].

Potential gain as a centrality measure

A. Provetti
Ultimo
2019

Abstract

Navigability is a distinctive features of graphs associated with artificial or natural systems whose primary goal is the transportation of information or goods. We say that a graph G is navigable when an agent is able to efficiently reach any target node in G by means of local routing decisions. In a social network navigability translates to the ability of reaching an individual through personal contacts. Graph navigability is well-studied, but a fundamental question is still open: why are some individuals more likely than others to be reached via short, friend-of-a-friend, communication chains? In this article we answer the question above by proposing a novel centrality metric called the potential gain, which, in an informal sense, quantifies the easiness at which a target node can be reached. We define two variants of the potential gain, called the geometric and the exponential potential gain, and present fast algorithms to compute them. The geometric and the potential gain are the first instances of a novel class of composite centrality metrics, i.e., centrality metrics which combine the popularity of a node in G with its similarity to all other nodes. As shown in previous studies, popularity and similarity are two main criteria which regulate the way humans seek for information in large networks such as Wikipedia. We give a formal proof that the potential gain of a node is always equivalent to the product of its degree centrality (which captures popularity) and its Katz centrality (which captures similarity).
Centrality; Graph Navigability; Node Ranking in Graphs
Settore INF/01 - Informatica
2019
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
WI19_proceedings.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 587.72 kB
Formato Adobe PDF
587.72 kB Adobe PDF Visualizza/Apri
3350546.3352559.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 623.68 kB
Formato Adobe PDF
623.68 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/2434/890318
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact