Game-theoretic Network Centrality: A Review
This is an incremental review that synthesizes existing literature on game-theoretic network centrality for researchers in network theory and computer science.
The paper reviews game-theoretic centrality measures, which identify important nodes in networks by treating them as players in cooperative games based on graph properties, and organizes these measures into categories focused on connectivity and synergies, with an emphasis on algorithms and complexity.
Game-theoretic centrality is a flexible and sophisticated approach to identify the most important nodes in a network. It builds upon the methods from cooperative game theory and network theory. The key idea is to treat nodes as players in a cooperative game, where the value of each coalition is determined by certain graph-theoretic properties. Using solution concepts from cooperative game theory, it is then possible to measure how responsible each node is for the worth of the network. The literature on the topic is already quite large, and is scattered among game-theoretic and computer science venues. We review the main game-theoretic network centrality measures from both bodies of literature and organize them into two categories: those that are more focused on the connectivity of nodes, and those that are more focused on the synergies achieved by nodes in groups. We present and explain each centrality, with a focus on algorithms and complexity.