Game Theoretic Network Centrality

21 concepts12 papers1 proposal

Traditional network science relies heavily on structural heuristics to determine which nodes or edges are the most important. Metrics like degree centrality, betweenness, and closeness evaluate a node based on its isolated position or its alignment along fixed paths. However, real-world networks rarely operate through isolated actors. Whether spreading information, maintaining infrastructure resilience, or regulating biological pathways, network elements act in groups, generating complex interdependencies and synergies.

To capture these group dynamics, a powerful paradigm has emerged: Game-Theoretic Network Centrality. By modeling network components as players in a cooperative (coalitional) game, this approach uses cooperative game theory to distribute the total utility of group interactions fairly back to individual components.

The Core Intuition: From Isolation to Coalitions

Why do traditional metrics fail in complex scenarios? Consider the problem of influence maximization in a social network. If we simply select the two nodes with the highest degrees, their local neighborhoods might heavily overlap, making one of them highly redundant.

As noted in a comprehensive review by Mateusz Krzysztof Tarkowski et al. in Game-theoretic Network Centrality: A Review, game-theoretic centrality solves this by shifting the focus from individual attributes to coalitions (subsets of nodes). The network's function is defined via a characteristic function—a mathematical rule that assigns a value or "payout" to any given coalition based on its collective performance (e.g., the total number of unique users reached).

To determine the true importance of a single node, we calculate its marginal contribution: how much additional utility does this node bring when it joins an already existing coalition?

Traditional Centrality:  [Node] ---> Evaluated in isolation based on structure
Game-Theoretic:          [Existing Coalition] + [Node] ---> Measure change in total utility

By averaging a node's marginal contribution across all possible coalitions, we get its Shapley value (or a related power index called a semivalue). As surveyed by Xinfang Song et al. in A survey of game theory as applied to social networks, this mathematical formulation guarantees that a node's ranking accounts for redundancy and synergy, offering a far more robust measure of systemic importance than simple structural counts.

The Mathematical Engine: Marginal Utility and the Shapley Value

The reason the Shapley value serves as an exceptional centrality metric is its axiomatic fairness. It is the only allocation method that satisfies fundamental properties like efficiency (the sum of all node centralities equals the total network utility) and symmetry (nodes that contribute identically to all coalitions receive identical centrality).

In the context of influence maximization, Kamil Adamczewski et al. demonstrate this dynamic behavior in How good is the Shapley value-based approach to the influence maximization problem?. When a node is added to a coalition where its neighbors are already active, its marginal utility is low. Conversely, if it connects to an unreached community, its marginal utility is high. The resulting ranking inherently penalizes structural overlap and rewards strategic positioning.

A Universal Language for Network Importance

Is game-theoretic centrality merely a specialized alternative to classical metrics, or is it something more fundamental? Theoretical breakthroughs reveal that cooperative game theory is actually a universal framework encompassing all of network science.

In Axiomatic Characterization of Game-Theoretic Network Centralities, Oskar Skibski et al. proved a profound universality theorem: every conceivable network centrality measure can be mathematically represented as a game-theoretic centrality. By constructing a "dummy game" where a coalition's value is defined directly by a classical metric, any ranking logic can be translated into the language of coalitional games.

This theoretical bridge extends to other foundational concepts in network science:

  • Vitality Indices: A common way to measure a node's importance is to delete it and measure how much the network's quality degrades. In Vitality Indices are Equivalent to Induced Game-Theoretic Centralities, Oskar Skibski proved that all vitality indices are precisely equivalent to a specific class of Shapley value-based centralities.
  • Weighted Graphs: To handle complex organizational or social structures, Jadwiga Sosnowska et al. extended this paradigm to weighted graphs in Attachment Centrality for Weighted Graphs, proving that graph-derived formulations of the Shapley and Myerson values naturally accommodate edge and node weights while maintaining axiomatic consistency.

Taming the Computational Bottleneck

The primary obstacle to adopting game-theoretic centrality is its computational complexity. Because the Shapley value requires evaluating a node's marginal contribution across all possible subsets of a network, an exact calculation requires $2^N$ evaluations—an impossibility for large networks.

To make this framework scalable, researchers attack the problem from two angles:

  1. Localized Heuristics: In How good is the Shapley value-based approach to the influence maximization problem?, the authors introduced algorithms like the Discounted Shapley Value (DSV) and SV-LDAG. These methods restrict the evaluation of coalitions to local neighborhoods or local directed acyclic graphs, bypassing the exponential explosion of states while retaining the core benefits of marginal utility tracking.
  2. Unified Algebraic Frameworks: Rather than focusing solely on the Shapley value, Mateusz Tarkowski et al. developed a generalized framework in Efficient Computation of Semivalues for Game-Theoretic Network Centrality. By focusing on semivalues—a broader class of power indices—the authors demonstrated that under specific graph conditions, these metrics can be computed in polynomial time, unlocking game-theoretic analysis for large-scale real-world systems.

Real-World Applications

Because the characteristic function can be tailored to model any network property, game-theoretic centrality has proven highly effective across wildly diverse domains.

Genomics and Disease Prioritization

In biological systems, diseases are rarely caused by a single isolated gene; rather, they stem from complex cascades within gene interaction networks. In Game theoretic centrality: a novel approach to prioritize disease candidate genes by combining biological networks with the Shapley value, Min Woo Sun et al. applied the Shapley value to prioritize candidate genes for Autism Spectrum Disorder (ASD). By treating genes as players in a network coalition, they successfully captured multi-gene synergistic influences that traditional genome-wide association studies often miss.

Network Resilience and Core Minimization

Instead of ranking nodes to spread information, we can rank edges to understand network vulnerability. Sourav Medya et al. in A Game Theoretic Approach For Core Resilience and Tianyi Ma et al. in A Game Theoretic Approach For k-Core Minimization modeled edge removals as a cooperative game. Their goal was to find a small set of critical links whose removal causes the collapse of a network's dense core. By capturing the cascading, synergistic effects of removing multiple links simultaneously, their Shapley-based approach degraded dense network cores up to six times more effectively than standard greedy strategies.

Signed Social Networks

Traditional centrality metrics struggle when networks contain both positive (trust) and negative (distrust) edges. In Trust and Distrust Across Coalitions: Shapley Value Based Centrality Measures for Signed Networks (Student Abstract Version), Varun Gangal et al. designed a game-theoretic centrality that evaluates how nodes contribute to the collective reputation of groups. This coalitional view of trust and distrust allowed for a significant leap in performance when detecting malicious actors and trolls compared to individual-based metrics.

Infrastructure and Resource Allocation

The framework even extends to hardware optimization. In Cluster Content Caching: An Energy-Efficient Approach to Improve Quality of Service in Cloud Radio Access Networks, Zhongyuan Zhao 0001 et al. utilized the Shapley value to quantify the marginal contribution of individual base stations to content caching clusters in 5G networks. This allowed operators to decouple and optimize resource allocation in massive distributed systems, mitigating backhaul bottlenecks and lowering power consumption.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_cooperative_game_theoretic_centrality_f8c39fa7,
  title = {cooperative game-theoretic centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cooperative-game-theoretic-centrality/rdr_f8c39fa70f26473c8b320d2ba9718446},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_cooperative_game_theoretic_centrality_f8c39fa7_v1,
  title = {cooperative game-theoretic centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cooperative-game-theoretic-centrality/rdr_f8c39fa70f26473c8b320d2ba9718446/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake