Game theoretic network centrality: exact formulas and efficient algorithms

The concept of centrality plays an important role in network analysis. Game theoretic centrality measures have been recently proposed, which are based on computing the Shapley Value (SV) of each node (agent) in a suitably constructed co-operative network game (for example see [1]). However, the naive method of exact computation of SVs takes exponential time in the number of nodes. In this paper, we develop analytical formulas for computing SVs of nodes for various kinds of centrality-related co-operative games played on both weighted and unweighted networks. These formulas not only provide an efficient and error-free way of computing node centralities, but their surprisingly simple closed form expressions also offer intuition into why certain nodes are relatively more important to a network.