Shapley-based network centrality identifies 1% of nodes to influence half a graph

Network centrality metrics like degree or betweenness measure individual node importance but ignore collective influence. A new paper from Dharmawan et al., accepted at ICANN 2026, tackles this by applying Shapley values from cooperative game theory to the 'sphere of influence' problem: selecting a set of m nodes that maximize network coverage under reachability criteria (single-hop, k-hop, multi-path). Using exact polynomial-time algorithms by Michalak et al., the authors evaluate the approach on three real-world networks: Euroroad, Facebook TV Shows, and Cora. Results show practical approximation ratios consistently approach 0.9, significantly exceeding the theoretical lower bound of (1-1/e) ~ 0.63.

Most strikingly, on the Cora citation network, the Shapley-based method selects only 26 nodes (less than 1% of the graph) to influence half the network under 3-hop reachability. In contrast, a degree-based baseline requires substantially larger sets. The approach dramatically outperforms naive baselines especially in hub-and-spoke topologies. This work demonstrates that Shapley value centrality is not only theoretically sound but also empirically efficient, opening the door for real-world applications in viral marketing, epidemiology, and social network analysis where maximizing influence with minimal seeding is critical.