ETD

• centrality
• game-theory
• network analysis
• Shapley value

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.