2017/12/31 by Mateusz Tarkowski, Tarkowski, Mateusz K., Tomasz Michalak +5 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Complex Network Analysis Techniques #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1801.00218
openalex publication_date 2017/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.