Source-linked AI summary
Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality
Tomasz Pawel Michalak, Karthik V Aadithya, Piotr L. Szczepanski, Balaraman Ravindran, Nicholas R. Jennings
TL;DR
Shapley value-based centrality is useful for network applications but has been difficult to compute exactly because direct evaluation is exponential and Monte Carlo is costly and inexact. This paper derives analytical formulas and efficient algorithms for several weighted and unweighted network games, finding substantial empirical speedups over Monte Carlo. The authors also identify scope limits: one game receives only an approximation, and more complex characteristic functions may be harder to compute.
Problem
Shapley value-based centrality lacks efficient exact computation despite its ability to account for group synergies in network rankings.
Method
The paper derives closed-form Shapley-value formulas and polynomial-time algorithms for several weighted and unweighted network centrality games.
Results
1600 times faster: on the unweighted Western States Power Grid, exact g1 and g2 computation outpaced Monte Carlo approximations with a 10% error margin.
Takeaways & Limitations
Exact, polynomial-time computation is practical for several network centrality games and is substantially faster than Monte Carlo in the evaluated networks.
Takeaways & Limitations
The fifth game receives an approximation, and more complex characteristic functions may make computation substantially harder.
Abstract
from arXiv · showhide
The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.
1. Introduction
The paper motivates Shapley value-based network centrality as a way to rank nodes while accounting for group synergies, then develops exact or approximate efficient algorithms for several network games. Experiments on real networks show substantial speedups over Monte Carlo computation.
- Motivation: Shapley value-based centrality ranks individual nodes by their contributions across possible groups, capturing synergies that conventional measures may miss.It offers a flexible framework because the cooperative game can be defined according to the application and network features.
- Computational challenge: The original Shapley value computation requires evaluating marginal contributions across O(2^|V|) coalitions, making it prohibitive for large networks.Monte Carlo sampling is feasible but inexact and can remain time-consuming as the desired error margin decreases.
- Approach: The paper develops polynomial-time algorithms for five network games extending degree- and closeness-related centrality notions.The games differ in how coalition size and sphere of influence are defined, including threshold reachability and weighted-distance cutoffs.
- Approach: For the first four games, the authors derive closed-form Shapley values and exact algorithms, including O(|V| + |E|) algorithms for g1 and g2.For g3 and g4, the stated running time is O(|V||E| + |V|^2log|V|); the fifth game receives an O(|V||E|) approximation with about 5% error on large networks.
- Empirical evaluation: 1600 times faster: on the unweighted Western States Power Grid, the algorithms exactly compute g1 and g2 Shapley values versus Monte Carlo with a 10% error margin.The evaluation also includes an astrophysics collaboration network.
2. Related Literature
The related literature contrasts conventional representations and computational results for coalitional games with the paper’s network-specific challenge. The paper seeks to exploit both graph structure and coalition-value functions without enumerating all coalitions.
- Network centrality literature: Game-theoretic network centrality extends centrality analysis by ranking individual nodes while accounting for synergies among possible coalitions.Earlier work includes graph-restricted games and approaches in which all coalitions are feasible, the latter being adopted here.
- Coalitional-game computation: Coalitional-game representations trade off succinctness and expressiveness: structural representations are compact but may not represent every game, while fully expressive ones are not always succinct.This literature commonly addresses the exponential complexity of listing all coalitions.
- Coalitional-game computation: Computing Shapley values remains NP-Hard or #P-Complete for several succinctly representable games, including weighted voting, threshold network flow, and minimum spanning tree games.The related literature therefore contains both negative and positive computational results.
- Related representation: The induced-subgraph representation defines coalition value as the sum of weights on internal edges of the coalition-induced subgraph.A three-player example illustrates this graph-based representation.
- Paper’s positioning: The paper’s specific challenge is to compute Shapley values efficiently when coalition values have closed-form expressions that depend non-trivially on the underlying network.The intended solution avoids enumerating all possible coalitions by exploiting graph structure and functional form.
3. Preliminaries and Notation
The preliminaries define networks, coalitional games, and Shapley values, then connect a network characteristic function to a centrality score. The resulting score generalizes closeness centrality from individual nodes to coalitions.
- Graph notation: A network consists of vertices and edges; weighted networks associate a weight with every edge, while vertex degree counts incident edges.Paths and shortest-path distances provide the graph-theoretic basis for later centrality formulations.
- Coalitional games: A characteristic function assigns each coalition C a real-valued performance score, with ν(∅) = 0; a coalitional game is the pair (A, ν).In the network setting, graph vertices are agents and any subset of vertices can form a coalition.
- Shapley value: The Shapley value is each agent’s average marginal contribution over all possible arrival orders of the players.The paper uses this payoff as a node-level centrality score.
- Network centrality: The network characteristic function assigns coalition value according to the coalition’s overall proximity to other nodes, extending closeness centrality to every node combination.Distance is measured by shortest-path length, and the formulation can model information-dissemination settings.
- Network centrality: A high Shapley value indicates that a node contributes more, on average, to increasing a randomly chosen coalition’s proximity to other network nodes.Computing these values yields a centrality score characterized as an improved version of closeness centrality.
- Computational setting: The main computational obstacle is exponential complexity, which the paper addresses by seeking polynomial-time computation for many centrality applications.The subsequent algorithmic treatment considers five characteristic-function formulations based on coalition spheres of influence.
4. Algorithms for Shapley Value-Based Network Centrality
The paper develops exact Shapley-value algorithms for several network centrality games by exploiting their coalition-value structure, avoiding exhaustive coalition enumeration. The first four games admit closed forms and exact algorithms, while the fifth has only an approximate formula.
- Five games model coalition influence through one-hop reachability, multi-path adjacency, weighted cutoff distance, arbitrary distance decay, or a further weighted formulation.The first two games use unweighted graphs; the remaining formulations extend the sphere of influence to weighted networks.
- Game 1: Game g1 defines coalition value as the size of its fringe, consisting of coalition members and nodes reachable within one hop.This is formalized through the fringe and characteristic function ν1.
- Game 1: Game g1 has an exact closed-form Shapley value, and Algorithm 1 computes all node values in O(|V | + |E|) time.The formula sums contributions involving each node and its neighbors; the resulting centrality also reflects neighboring-node degrees.
- Game 2: Game g2 generalizes g1 by counting coalition members or nodes adjacent to at least k coalition members, while retaining an O(|V | + |E|) exact algorithm.Algorithm 2 computes the Shapley values without enumerating coalitions.
- Weighted games: The exact algorithm for game g3 runs in O(|V ||E| + |V |2log|V |), using shortest-path computations and subsequent evaluation of the Shapley expression.The same complexity is reported for the related weighted game g4.
- Game 5: For game g5, the authors derive an approximate polynomial-time Shapley formula because they do not obtain an exact expression.Its approximation algorithm runs in O(|V ||E|) and was found accurate in practice.
5. Simulations
The simulations compare exact or approximate algorithms with Monte Carlo sampling across games and networks, measuring runtime and approximation error. Exact methods are generally much faster, although performance depends on the game and network size.
- Evaluation setup: The evaluation compares exact algorithms for games g1–g4 and an approximation algorithm for g5 against Monte Carlo sampling.Runtime and error are recorded, with error defined as the maximum discrepancy from the actual Shapley value.
- Evaluation setup: Monte Carlo methods generate random player permutations and estimate each node’s marginal contribution to preceding coalitions.The method iterates up to maxIter permutations and updates Shapley-value estimates from marginal contributions.
- Overall findings: Exact solutions generally outperform Monte Carlo even with wide error margins, but Monte Carlo remains viable when a centrality metric is not represented by games g1–g4.The exception is the approximation algorithm for g5, which does not always outperform Monte Carlo.
- Game g1: 0.43ms is sufficient for the exact g1 algorithm, whereas Monte Carlo requires more than 2000ms to guarantee 5% error, making it over 4600 times slower.Monte Carlo averages exceed 200ms for 20% error and 2000ms for 5% error on the tested network.
- Game g3: About 13s is required by the exact g3 algorithm on the Western States Power Grid, because both methods incur a one-time Dijkstra computation exceeding 12.5s.This substantially reduces the exact method’s relative speedup compared with games g1 and g2.
- Game g3: Increasing d_cutoff significantly worsens Monte Carlo performance for weighted g3 because more nodes increase both marginal-contribution cost and Monte Carlo error.The comparison concerns the astrophysics collaboration network.
- Game g4: For g4, Monte Carlo takes more than 40 hours to approach 50% error, while its error can still rise slightly with additional iterations.Randomly selected permutations can increase the approximation error, so statistical improvement is not monotonic.
- Game g5: The proposed g5 approximation has about 10% error on K6 and about 5% on K12, but Monte Carlo can slightly outperform it at higher W_cutoff values.For large networks, the approximation is inferred to remain within 5% and be at least twice as fast as Monte Carlo, assuming Monte Carlo is accurate.
6. Conclusions and Future Work
The paper shows that many network centrality games admit analytical Shapley-value solutions with exact, polynomial-time computation, while weighted-network approximations are acceptable in some situations. It identifies broader coalitional-game and centrality constructions as future work, with computational difficulty potentially increasing for more complex characteristic functions.
- Conclusions: Many centrality-related cooperative games on networks can be solved analytically with error-free polynomial-time algorithms that are faster than Monte Carlo methods.Approximate closed-form algorithms are also possible for some weighted-network games.
- Conclusions: Simulations show that the weighted-network approximations are acceptable for a range of situations.
- Future Work: Future work includes extending Shapley value-based centrality to other centrality notions and developing coalitional games tailored to particular applications.
- Future Work: Other cooperative-game solution concepts, including the Banzhaf power index and the core, could be studied as network centrality measures.
- Future Work: More formal methods could construct network coalitional games corresponding to known centrality metrics or families, but more complex characteristic functions may be computationally challenging.
Appendix A. Marginal Contribution Blocks for Algorithm 6 for g2-g5
The appendix specifies how Algorithm 6 computes marginal contributions for games g2–g5, using counting, edge, distance, and weight conditions tailored to each game.
- g2: The g2 implementation uses the Edges array to test whether a node has reached its required adjacent-edge threshold.
- Overview: The marginal-contribution block of Algorithm 6 has a different form for each of the remaining four games.The appendix discusses these blocks for g2, g3, g4, and g5.
- g2: For g2, a node contributes through itself or an adjacent node when coalition-membership and adjacent-edge-count conditions are satisfied.The algorithm tracks counted nodes and edges while iterating over neighbors.
- g3 and g4: For g3 and g4, distance-dependent values are precomputed with Dijkstra’s algorithm, then marginal contributions compare distances from a node with distances from the coalition.These precomputations speed up Monte Carlo methods.
- g5: For g5, the algorithm extends g2 to weighted graphs by testing sums of incident edge weights against node-specific weight cutoffs.The Weights array tracks the accumulated edge weights used in the condition.
Appendix B: Main Notation Used in the Paper
The notation defines the graph, coalition, game, Shapley-value, neighborhood, distance, probability, expectation, and weighting symbols used throughout the paper.
- Cooperative games: C denotes a coalition, ν(C) its characteristic-function value, and (A, ν) or g_i a coalitional game.
- Shapley value: SV_gj(v_i) denotes the Shapley value of vertex v_i in game g_j.
- Graphs and networks: G = (V, E) denotes an unweighted graph, while G = (V, E, W) denotes a weighted graph.V and E are the vertex and edge sets, and W(v, u) is an edge weight.
- Network structure: NG(v_i) is the neighbor set of vertex v_i, while distance(v, u) or d(v, u) is the distance between vertices.NG(v_j, d_cutoff) denotes an extended neighborhood within the cutoff distance.
- Game parameters: k_i is the minimum number of adjacent nodes needed to influence v_i in Game 2, whereas W_cutoff(v_i) is the minimum adjacent-edge weight sum needed in Game 5.
- Mathematical notation: E[·] and P[·] denote expectation and probability, O(·) denotes big O complexity, and f(·) is a positive-valued decreasing function.