Efficient Computation of Semivalues for Game-Theoretic Network Centrality

Mateusz Krzysztof Tarkowski, Piotr L. Szczepanski, Tomasz P. Michalak, Paul Harrenstein, Michael J. WooldridgeJAIR 2018 · DOI · OpenReview

TL;DR

This paper introduces a unified framework for computing game-theoretic network centrality measures, specifically those based on semivalues. By developing a general algorithm and demonstrating its polynomial-time computability under certain conditions, the authors significantly advance the efficiency of calculating these important network analysis metrics, covering existing measures and enabling the creation of new ones.

What Problem Does This Paper Address?

Networks are ubiquitous, and understanding the importance of individual nodes within them is crucial for various applications, from social science to biology. Traditional centrality measures (like degree, closeness, and betweenness) focus on individual node properties. However, recent research has explored "game-theoretic network centrality," which views nodes as players in a cooperative game and uses concepts like the Shapley value or Banzhaf index to quantify a node's importance based on its contribution to groups (coalitions) of nodes.

While promising, a major hurdle has been the computational complexity of these game-theoretic measures. Calculating them often requires enumerating an exponential number of possible coalitions, making them intractable for all but the smallest networks. Existing polynomial-time solutions were specific to individual measures, lacking a unifying approach. This paper aims to bridge this gap by providing a general framework and demonstrating that a broad class of semivalue-based network centralities can be computed efficiently.

Methods

The core contribution is a generic framework for modeling group centrality measures. This framework breaks down a group centrality measure into two key components:

  • Items: These are the fundamental graph-theoretic entities that contribute to a group's centrality (e.g., shortest paths for betweenness, neighbors for degree). Items have associated values and are grouped based on these values.
  • Relations: These define how nodes (and thus coalitions) interact with items (positive, negative, or neutral).

By defining these components, the authors can model a wide range of group centrality measures as characteristic functions of cooperative games. They then introduce a general semivalue computation algorithm that leverages this framework. The key insight is that by imposing certain structural regularity constraints on the item partitions and the computability of item/group values (defined as the class $M^*$), the semivalue computation can be reduced from exponential to polynomial time. This allows for a "plug-and-play" approach: define the items, relations, and functions according to the framework, and the general algorithm guarantees polynomial computation.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and algorithmic development, using example graphs for illustration rather than specific datasets.

Key Insights and Ideas

  • Unified Framework: The most significant insight is the creation of a general framework that unifies the study and computation of a broad class of game-theoretic network centralities. This moves beyond ad-hoc solutions for individual measures.
  • Items and Relations: The decomposition of group centrality into "items" and "relations" provides a powerful and abstract way to model diverse centrality concepts, making their computational properties more transparent.
  • Polynomial Computability is Widespread: The paper demonstrates that many existing and novel game-theoretic centrality measures, including those based on degree, closeness, and betweenness, can indeed be computed in polynomial time when modeled within their framework and satisfying specific regularity conditions. This is a crucial result for practical application.
  • Semivalues as a General Tool: The focus on semivalues (including Shapley and Banzhaf) as the aggregation mechanism for group contributions highlights their versatility in capturing different notions of player importance in a network context.

Key Results

  • Theorem 1: For any group centrality measure $\psi$ belonging to the class $M^*$ (defined by specific polynomial-time computability and structural constraints), the semivalue-based centrality $\phi_u(\psi(G))$ can be computed in polynomial time.
  • Algorithm 1 (SEMI): A general algorithm is presented that computes semivalue-based centralities for any measure within $M^*$.
  • Polynomial-Time Algorithms for Specific Centralities: The paper provides polynomial-time algorithms for parametrised versions of:
  • Group Degree Centrality (including weighted, impact factor, and normalized variants).
  • Group Betweenness Centrality (including stress, distance-scaled, and normalized variants).
  • Group Closeness Centrality (including harmonic and influence game variants).
  • Faster Banzhaf Index Computation: Specific algorithms are developed for efficiently computing the Banzhaf index for these centrality measures, often achieving faster polynomial complexities.
  • Table 1, 3, 4, 5: These tables summarize the proposed algorithms and their computational complexities for various centrality measures, demonstrating the broad applicability of the framework.

Limitations and Future Work

  • Class $M^*$ Restrictions: While the framework is general, polynomial computability is guaranteed only for measures within the class $M^*$, which requires specific structural properties (e.g., polynomial-sized item partitions, efficient computability of item values). Measures not fitting $M^*$ might remain intractable.
  • Focus on Semivalues: The current work focuses on semivalues. Future work could explore other single-valued solution concepts (e.g., probabilistic values, the core, nucleolus) and their computational complexity in network settings.
  • More General Networks: The framework could be extended to analyze more complex network structures like multi-layer networks, hypergraphs, or networks with additional extraneous information beyond topology.
  • Axiomatic Study: The axiomatic characterization of game-theoretic network centralities is still nascent. Future research could investigate the relationship between axioms and computational properties.
  • Applications and Empirical Studies: More research is needed on the practical applications of these measures and comparative studies to evaluate their effectiveness in real-world scenarios.

Summary updated

BibTeX
@article{tarkowski2018efficient,
  author = {Mateusz Krzysztof Tarkowski and Piotr L. Szczepanski and Tomasz P. Michalak and Paul Harrenstein and Michael J. Wooldridge},
  title = {{Efficient Computation of Semivalues for Game-Theoretic Network Centrality}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11239},
}
Figure