New Shapley-based method fairly attributes seed influence in social networks

A team of computer scientists from Duke University has developed a principled framework to fairly credit individual seed users in social network influence campaigns before any diffusion actually happens. Their paper, accepted at SIGKDD 2026, addresses the underexplored problem of ex-ante influence attribution — determining how much each influencer or advertiser contributes to a potential cascade, without relying on post-hoc logs. The solution adapts Shapley values from cooperative game theory, which capture each seed's marginal impact in an equitable manner.

Applying Shapley values to stochastic diffusion processes is computationally challenging. The authors tackle this by designing polynomial-time algorithms for the special case of single-step activation, useful for scenarios like one-hop sharing. They prove that attribution becomes #P-hard for any propagation beyond one step, establishing a sharp tractability boundary. For the standard Independent Cascade (IC) model and time-bounded variants, they develop approximation algorithms with provable guarantees. Empirical tests on real-world and synthetic networks confirm that their methods are both efficient and effective, offering a practical tool for budget allocation, influencer pricing, and privacy-preserving credit distribution.