logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-04252022-123223


Tipo di tesi
Tesi di laurea magistrale
Autore
ZIGLIOTTO, FRANCESCO
URN
etd-04252022-123223
Titolo
Game-theoretic centrality
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Benzi, Michele
Parole chiave
  • centrality
  • game-theory
  • network analysis
  • Shapley value
Data inizio appello
13/05/2022
Consultabilità
Tesi non consultabile
Riassunto
Over the last few years, the problem of determining the most important nodes in a graph has gained a lot of attention, as the possible applications in real-world networks are countless and span a wide range of contexts. Examples are social networks, citation graphs, infrastructures, spread of diseases and many others.
Of course, the notion of importance (or centrality) of a node can be defined in a variety of ways depending on the context. In literature, many centrality indices have been proposed to meet this variety.
This thesis is about a quite recent line of research whose main goal is to consider the synergies between nodes when evaluating the importance of a given node. This can be done using concepts from cooperative game theory, and it leads to a class of centrality indices that is referred to as game-theoretic centrality.
In general, the game-theoretic centrality of a node is very expensive to compute. Nonetheless, in many cases it is possible to derive equivalent formulae which lead to much faster algorithms. In this work I present a general framework to express game-theoretic centrality indices and derive those equivalent formulae for many centrality indices inside this framework. Some game-theoretic centrality indices were also analyzed from an axiomatic point of view, in order to better understand their properties and potential uses, and also providing some theoretical foundations.
File