GENERALIZING CENTRALITY MEASURES: AXIOMS AND PROPERTIES

In social network analysis, one of the most studied problems is that of determining the importance of actors in a network. Not surprisingly, there is not a unique meaning of importance and, over the years, researchers have proposed different interpretations and tried to capture different notions of this kind. We call centrality measures all those tools and techniques that we use to quantitatively measure node importance in networks. Nowadays, they are widely used in several fields and for many different tasks, e.g., identifying influential actors in social networks, ranking web pages, identifying critical components in routing networks, and so on. Centrality silently appeared in the second half of the 19th century, but the very first uses of the term centrality can be traced back to the late forties of the 20th century. In those years, Alex Bavelas introduced closeness, one of the oldest and most notorious centralities, in the context of group collaboration and problem-solving. According to this measure, the closer a node is on average to all the other nodes of a network, the more central it is. Bavelas' experiments paved the way for the proposal of a whole zoo of definitions of centrality, each one capturing a brand-new notion of importance, or solving the issues of the previously defined centralities. Closeness, betweenness, harmonic centrality, PageRank, Katz's and Seeley's indices are only very few examples of all the centrality measures that were proposed over the years. In the seventies, in one of the most celebrated papers about centrality, Linton Freeman stated that the only consensus in those days was that centrality is an important structural attribute of social networks. As of today, while centrality has become a well-established tool of network analysis, it seems that it still lacks solid theoretical foundations. This dissertation goes exactly in this direction: in fact, our aim is to add some building blocks to the theory of centrality. To do so, we follow two main approaches. The first one, pioneered by Gert Sabidussi, can be referred to as axiomatic, and consists of defining properties of interest that centrality indices should satisfy, and then checking whether they do so or not. In particular, we study two specific axioms, namely score monotonicity and rank monotonicity, which aim to answer the following informal question: is it always a good idea to have new friends in a social network? In graphs' terminology, this is equivalent to asking whether a new edge in an undirected graph always makes the two new endpoints more central. In the directed case, the answer in general is yes: having new followers is a good idea. However, we will see that extending the analysis to the undirected case yields counter-intuitive differences. Secondly, we study geometric centralities, i.e., those measures that only depend on how many nodes each node has at any given (shortest-path) distance. A significant subclass of geometric measures can be computed as linear combination of the number of nodes at every distance, by means of suitable coefficient vectors: we call such measures linear geometric. In the literature they are usually studied assuming that the coefficients are non-increasing, following the intuition that importance comes from having closer connections rather than longer ones. We remove assumptions on the coefficients and study this class in its full generality, seeking answers to two dual questions: (1) Can we always distinguish linear geometric centralities from one another? (2) Is there a graph on which we can obtain all the possible rankings of nodes, by suitably choosing the coefficient vectors? In other words, how expressive is this class of centralities? The two approaches are undoubtedly different, but they share our intention of generalizing: in the first case, we analyze properties that we believe should be satisfied by all the centrality measures, as they express common belief and intuitions about node importance in networks. In the second case, rather than studying properties that should be general, we generalize the class of centralities under analysis, with the aim of capturing wider range of behaviors.

Determinare l'importanza degli attori di una rete è uno dei problemi più studiati nella social network analysis. Non sorprendentemente, non c'è un unico significato possibile di importanza, e negli anni ne sono state proposte diverse interpretazioni, con lo scopo di catturare diverse nozioni di questo tipo. Chiamiamo misure di centralità tutte quelle tecniche che vengono usate per quantificare l'importanza di nodi in una rete. Al giorno d'oggi, le centralità sono largamente utilizzate in molti campi e per molte applicazioni, per esempio l'identificazione di attori influenti nelle reti sociali, la classificazione di pagine web, l'individuazione di componenti critiche nelle reti di trasporto, etc. I primi accenni al concetto di centralità di nodi sono riconducibili alla seconda metà del diciannovesimo secolo, ma i primi utilizzi del termine centralità risalgono agli anni quaranta del novecento. In quegli anni, Alex Bavelas formalizzò la closeness, una delle prime e più note misure di centralità, studiandola nell'ambito della cooperazione di gruppi di persone a cui venivano assegnati problemi da risolvere. Per questa centralità, un nodo è tanto più importante (quindi, centrale) quanto più è vicino in media a tutti gli altri nodi della rete. Gli esperimenti di Bavelas ispirarono molti studiosi a proporre la loro definizione di centralità, ognuna delle quali cercava di catturare una nuova nozione di importanza, o di risolvere i difetti delle precedenti. Closeness, betweenness, la centralità armonica, PageRank, gli indici di Katz e Seeley sono solo alcuni esempi di tutte le misure che negli anni sono apparse in letteratura. Negli anni settanta, in uno dei lavori più celebri riguardo le centralità, Linton Freeman affermò che in quegli anni l'unico punto d'incontro fosse che la centralità è un'importante caratteristica strutturale delle reti sociali. Oggi la situazione non sembra essere cambiata radicalmente: nonostante siano ormai diventate uno strumento molto utilizzato nella network analysis, sembrano ancora mancare delle solide basi formali per la teoria delle centralità. L'obiettivo di questa tesi di dottorato è proprio quello di aggiungere dei nuovi elementi costitutivi alla teoria delle centralità. A questo scopo, seguiremo due approcci principali. Il primo, chiamato assiomatico e introdotto da Gert Sabidussi, consiste nel definire proprietà di interesse che gli indici di centralità dovrebbero soddisfare e, successivamente, verificare formalmente se queste le soddisfino o meno. In particolare, in questa tesi approfondiremo due assiomi, la score monotonicity e la rank monotonicity, il cui scopo è rispondere alla seguente domanda informale: è sempre una buona idea stringere nuove amicizie in una rete sociale? Volendo utilizzare una terminologia più affine alla teoria dei grafi, ciò è equivalente a chiedersi se, in un grafo non orientato, aggiungere un nuovo lato tra due vertici li renda sempre più centrali o meno. Nel caso orientato, la risposta, in generale, è sì: avere nuovi seguaci è una cosa positiva. Tuttavia, in questo lavoro vedremo come estendere l'analisi al caso non orientato generi delle differenze piuttosto controintuitive. In seconda istanza, studieremo le centralità geometriche, ovvero quelle centralità che dipendono solo da quanti nodi sono a ogni possibile distanza (intesa come lunghezza di un cammino minimo) da un dato nodo. Una sottoclasse considerevole di centralità geometriche può essere calcolata come combinazione lineare del numero di nodi a ogni distanza per mezzo di opportuni vettori di coefficienti: chiamiamo queste misure lineari geometriche. In letteratura queste centralità sono solitamente studiate sotto l'assunzione che i coefficienti siano non crescenti, seguendo l'intuizione che si dovrebbe attribuire più importanza, in termini di centralità, a connessioni brevi piuttosto che a connessioni lunghe. In questa tesi rimuoveremo le suddette assunzioni sui coefficienti e studieremo la classe risultante nella sua intera generalità, cercando di rispondere alle due seguenti domande: (1) Possiamo sempre distinguere centralità lineari geometriche le une dalle altre? (2) C'è un grafo su cui possiamo ottenere tutti i possibili ranking di nodi indotti dai valori di centralità, scegliendo opportunamente i vettori di coefficienti? In altre parole, quanto è espressiva questa classe di centralità? I due approcci appena descritti sono indubbiamente differenti, ma condividono il nostro intento di generalizzare: nel primo caso, analizziamo proprietà che crediamo debbano essere soddisfatte da tutte le misure di centralità, poiché catturano credenze e intuizioni comuni riguardo l'importanza dei nodi di una rete. Nel secondo caso, piuttosto che studiare proprietà che dovrebbero essere generali, generalizziamo la classe di centralità in analisi, con l'obiettivo di catturare un più ampio ventaglio di comportamenti.