GENERALIZING CENTRALITY MEASURES: AXIOMS AND PROPERTIES

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.

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2025

Author dc:creator

• FURIA, FLAVIO

Contributors dc:contributor

• tutore: P. Boldi ; co-tutore: S. Vigna ; coordinatore: R. Sassi
• F. Furia
• BOLDI, PAOLO
• SASSI, ROBERTO

• network analysi
• centrality measure
• centrality axioms
• analisi di reti
• misure di centralità
• assiomi di centralità
• Settore INFO-01/A - Informatica

Statement dc:rights

• info:eu-repo/semantics/openAccess
• license:Creative commons
• license uri:http://creativecommons.org/licenses/by-sa/4.0/

Language dc:language

eng

Handle dc:identifier

https://hdl.handle.net/2434/1205073

OAI identifier oai:identifier

oai:air.unimi.it:2434/1205073