![Graph Limits and Processes on Networks_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-03/Graph%20Limits%20and%20Processes%20on%20Networks_hi-res.jpg?h=6dcb57f1&itok=0PfSnAhz)
Abstract
Abstract
Identifying the optimal set of individuals to first receive information (‘seeds’) in a social network is a widely-studied question in many settings, such as diffusion of information, spread of microfinance programs, and adoption of new technologies. Numerous studies have proposed various network-centrality based heuristics to choose seeds in a way that is likely to boost diffusion. Here we show that, for the classic SIR model of diffusion and some of its generalizations, randomly seeding s + x individuals can prompt a larger diffusion than optimally targeting the best s individuals, for a small x. We prove our results for large classes of random networks, and verify them in several small, real-world networks. Our results identify practically relevant settings under which collecting and analyzing network data to boost diffusion is not cost-effective.