Sphere of Influence Centrality via Shapley Values: Empirical Approximation and Network Coverage Analysis
Sie Hendrata Dharmawan, Kevin Limanta, Brendan Liu, Peter Chin · 2026
Read Sphere of Influence Centrality via Shapley Values: Empirical Approximation and Network Coverage Analysis by Sie Hendrata Dharmawan, Kevin Limanta, Brendan Liu, Peter Chin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24121.txt.
Introduction
Dharmawan and colleagues test a game-theoretic way to pick the most influential nodes in a network. Shapley values, borrowed from cooperative game theory, credit each node for what it adds across all coalitions. That captures collective sway, which simple degree counts miss. The 2026 study scores sphere-of-influence picks: small node sets meant to maximise coverage under one-hop, multi-hop, and multi-path reach rules.
Three real networks serve as testbeds: a European road system, a Facebook page network, and the Cora citation graph. Ratios in practice cluster near the top of the range, well past the classic guarantee. Shapley-based picks crush a degree-based baseline, most of all in hub-and-spoke layouts. On Cora, a few dozen nodes, under one percent of the graph, suffice to sway half of it within three hops. Influence, the team argues, is coalitional at heart.
Catalog record
| CREATOR | Sie Hendrata Dharmawan, Kevin Limanta, Brendan Liu, Peter Chin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24121
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sphere of Influence Centrality via Shapley Values: Empirical Approximation and Network Coverage Analysis Sie Hendrata Dharmawan, Kevin Limanta, Brendan Liu, Peter Chin Abstract Node centrality is a fundamental problem in network analysis, yet classical metrics fail to capture the collective, coalitional nature of influence. We present a systematic empirical evaluation of the Shapley-value-based framework for the sphere of influence problem — selecting m m nodes to maximize network coverage under three reachability criteria: single-hop, k k -hop, and multi-path connectivity — using exact polynomial-time algorithms due to Michalak et al. Evaluation across three diverse real-world networks (Euroroad, Facebook TV Shows, and Cora) demonstrates that practical approximation ratios consistently approach 0.9, substantially exceeding the theoretical ( 1 − 1 / e ) (1-1/e) lower bound, and that the Shapley-based approach dramatically outperforms a degree-based baseline, particularly in hub-and-spoke topologies. In the most striking case, Shapley-based selection identifies just 26 nodes (under 1% of the Cora network) sufficient to influence half the graph under 3-hop reachability, compared to substantially larger sets required by the naive baseline. 1 Introduction Identifying the most strategically important nodes in a network is a central problem across many domains. Classical centrality measures such as degree, betweenness, and closeness quantify individual node importance efficiently, but they treat nodes in isolation. In practice, influence is a collective phenomenon: the combined effect of a set of nodes can differ substantially from the sum of their individual contributions, and a node that appears unremarkable by degree may be critical when acting alongside others. This paper studies the sphere of influence problem, which formalizes this collective perspective. Given a graph G and a budget m , the goal is to select a coalition S of m nodes whose sphere of influence (the set of nodes covered by S under a chosen reachability criterion) is maximized. We consider three reachability criteria introduced in prior work [ 12 , 5 ] : coverage within 1-hop distance ( g_{\text{base}} ), coverage within k -hop distance ( g_{\text{hop}} ), and coverage by at least k distinct coalition members within 1-hop distance ( g_{\text{conn}} ). All three variants are NP-hard [ 12 ] , making approximation algorithms essential. The approximation technique we build on leverages Shapley values from cooperative game theory [ 11 ] . Each node’s Shapley value captures its expected marginal contribution to coverage across all possible coalition orderings, satisfying the axioms of efficiency, symmetry, linearity, and the null player property [ 13 ] . Selecting the m nodes with highest Shapley values yields a (1-1/e)\approx 0.63 approximation guarantee [ 12 ] . Crucially, Michalak et al. [ 5 ] showed that exact Shapley values for all three game variants can be computed in polynomial time, eliminating the Monte Carlo estimation required by the original approach. While the theoretical foundations are well established, the practical performance of this framework across diverse real-world network topologies has not been systematically studied. The contributions of this paper are as follows: 1. A comprehensive empirical evaluation of the Shapley-value-based framework across three structurally diverse real-world networks (Euroroad, Facebook TV Shows, and Cora), demonstrating that practical approximation ratios consistently approach 0.9, well above the theoretical (1-1/e) floor. 2. An empirical comparison against a degree-based baseline showing that Shapley-based selection substantially outperforms naive heuristics in heterogeneous network topologies, with the performance gap most pronounced in hub-and-spoke structures. 3. A systematic analysis of the qualitative differences between the three reachability models ( g_{\text{base}} , g_{\text{hop}} , g_{\text{conn}} ), revealing a fundamental trade-off between reachability-based and consensus-based influence, and demonstrating remarkable efficiency: as few as 2 nodes suffice to cover 50% of the Facebook network at k=3 , and 26 nodes suffice in Cora. The paper is structured as follows. Section 2 surveys related work. Section 3 defines notation and the three game formulations with their exact Shapley value algorithms. Section 4 empirically verifies the approximation ratio on random graphs. Section 5 describes the real-world datasets. Section 6 presents experimental results. Section 7 presents our conclusion and future directions. 2 Related Work Node Centrality. A broad survey of centrality measures in complex networks is provided by Saxena and Iyengar [ 10 ] , covering degree, betweenness, closeness, and eigenvector-based metrics including PageRank. These measures are efficiently computable but capture only individual structural properties. Our work departs from this tradition by adopting a cooperative game-theoretic formulation that models nodes’ contributions when acting collectively — a distinction with direct consequences for which nodes are selected and how much coverage they achieve. Influence Maximization. Kempe, Kleinberg, and Tardos [ 3 ] formally introduced the influence maximization problem, proving NP-hardness under probabilistic cascade models and establishing the (1-1/e) greedy approximation guarantee via submodularity. Subsequent work by Leskovec et al. [ 4 ] introduced the CELF algorithm, significantly reducing the Monte Carlo simulation cost of evaluating marginal gains. Our sphere of influence formulation shares the same approximation structure but adopts deterministic reachability criteria rather than probabilistic diffusion, which enables exact, closed-form Shapley value computation without simulation. Game-Theoretic Network Centrality. Suri and Narahari [ 12 ] pioneered the coalitional game formulation of the sphere of influence problem and established the (1-1/e) approximation guarantee for Shapley-based node selection, relying on Monte Carlo estimation of Shapley values. Michalak et al. [ 5 ] significantly advanced this by deriving polynomial-time exact algorithms for the base, k -hop, and connectivity variants — the algorithms we implement and evaluate here. Narayanam and Narahari [ 6 ] explored Shapley values for influence in network formation games, further demonstrating the breadth of this game-theoretic lens. Submodular Optimization. The (1-1/e) guarantee common to all three game variants follows from the classical result of Nemhauser, Wolsey, and Fisher [ 7 ] on greedy maximization of monotone submodular functions under cardinality constraints. Feige [ 2 ] established that this ratio cannot be improved beyond (1-1/e) unless P = NP, contextualizing our empirical finding that practical ratios near 0.9 represent a meaningful gap above the worst-case bound. Domain-Specific Network Analysis. The three datasets used in our evaluation (Euroroad [ 8 ] , Facebook TV Shows [ 9 ] , and Cora [ 1 ] ) represent qualitatively distinct network topologies: spatially constrained infrastructure networks, community-structured social networks, and hierarchically influenced citation networks, respectively. These structural differences make them collectively well-suited to stress-testing whether the advantages of Shapley-based selection generalize beyond homogeneous random graphs, which is a central empirical question of this paper. 3 Definition And Notation In this section we reuse the notation from [ 5 ] . A graph G consists of nodes and edges , sets of which will be denoted V(G) and E(G) respectively. Every edge from set E(G) connects two nodes in set V(G) . An edge (u,v) connects vertices u,v\in V(G) . The number of edges incident to a vertex is called a vertex degree . The neighboring vertices of v\in V are all vertices connected to v . A path is, informally, a sequence of connected edges. A coalition S=\{v_{1},\dots,v_{k}\}\subset V(G) represents a subset of nodes within graph G . We define a characteristic function \nu(S) that maps any coalition to another coalition, with the corresponding payoff measured by |\nu(S)| (the cardinality of the resulting coalition). Across all three game formulations presented below, we