Consider, for instance, an epidemiology application, where the aim is to contain the spread of a disease. If we ask the question of whether the vaccination of any individual node is sufficient to stop the spread of the disease then the answer is most probably No. A much more likely way to contain the disease is to simultaneously vaccinate a (possibly relatively small) group of nodes. Based on this, to quantify the importance of a node, we need to consider the potential gain of vaccinating it as part of a bigger group, rather than just considering the potential gain of vaccinating it alone.
Such analysis of groups of nodes in the network directly corresponds to coalitional game theory, where the performance of players is studied in ``coalitions'' (i.e., subsets of players). Importantly, by imposing the combinatorial structure of a coalitional game over a network, it is possible to analyse the performance of nodes using a plethora of game-theoretic solution concepts developed over decades to analyse the performance of players. One such well-known game-theoretic solution concept is the Shapley value, which received ample attention in the literature due to its desirable properties. Another one is the Banzhaf index of power.
A particular advantage of such a game-theoretic perspective of network analysis is that it exposes the possibility of extending a wide variety of centrality measures. This is because a cooperative game typically places no assumptions or restrictions on how the groups are evaluated. This evaluation can be tailored to best fit the centrality measure at hand. For instance, a group of nodes can be evaluated based on the average degree therein, or based on its diameter, or its closeness to other nodes, etc.
A potential downside of game-theoretic network centralities is that they are based on solution concepts that are themselves hard to compute. For instance, given a coalitional game defined over a network of
O(|V|) nodes, a straight-forward computation of the Shapley value requires considering all possible
O(2|V|) coalitions (i.e., groups) of nodes. This is clearly prohibitive for networks with hundreds, or even tens, of nodes. Indeed, it has been shown that in some cases the exponential number of computations cannot be avoided, i.e., it is impossible to compute certain game-theoretic network centralities in time polynomial in the size of the network. This negative result holds, for instance, for game-theoretic network centralities in the spirit of Myerson's (1977) graph-restricted games.
Fortunately, various positive computational results have also been found. In particular, Michalak et al. (2013) analysed various Shapley value-based extensions of degree centrality and showed that it is possible to leverage the fact that the values of groups of nodes depend on the topology of the network. As a result, they showed that some game-theoretic centrality measures can be computable in polynomial time. Similarly, polynomial-time results are known for the Shapley value-based betweenness centrality (Szczepański et al., 2012).
Back to top