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) ofeach node (agent) in a suitably constructed co-operative networkgame. However, the naive method of exactcomputation of SVs takes exponential time in the number of nodes. In this paper, we develop analytical formulas for computing SVsof nodes for various kinds of centrality-related co-operative gamesplayed on both weighted and unweighted networks. These formulas not only provide an efficient and error-free way of computingnode centralities, but their surprisingly simple closed form expressions also offer intuition into why certain nodes are relatively moreimportant to a network.

Authors

• Karthik Aadithya
• Balaraman Ravindran

Keywords

• Game Theory
• Co-operative Games
• Shapley Value
• Social Networks