Sphere of Influence Centrality via Shapley Values: Empirical Approximation and Network Coverage Analysis
For network analysts, this work demonstrates that Shapley-value-based centrality is practically effective for influence maximization, but the evaluation is limited to three small networks and the approach is not new.
The paper evaluates Shapley-value-based centrality for selecting nodes to maximize network coverage under three reachability criteria. Empirical results on three real-world networks show approximation ratios near 0.9, exceeding the theoretical bound, and Shapley-based selection outperforms degree-based baselines, e.g., 26 nodes (under 1% of Cora) influence half the graph under 3-hop reachability.
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$ nodes to maximize network coverage under three reachability criteria: single-hop, $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)$ 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.