Friday, May 10, 2019 - 12:30pm to 1:30pm
Event Calendar Category
Other LIDS Events
Speaker Name
Amin Saberi
Affiliation
Stanford University
Building and Room number
E18-304
Abstract
Identifying the optimal set of individuals to first receive information (“seeds”) in a social network is a widely-studied question with applications in marketing new technologies, ideas, or economic development programs like micro-finance. 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 some frequently studied diffusion processes and a small x, randomly seeding s plus x individuals can prompt a larger cascade than optimally targeting the best s individuals. We prove our results for large classes of random networks and also show that they hold in simulations over several real-world networks. This suggests that returns to collecting and analyzing network data to identify the optimal seeds may not be economically significant. Given these findings, practitioners interested in communicating a message to a large number of people may wish to compare the cost of network-based targeting to that of slightly expanding initial outreach.
Joint work with Mohammad Akbarpour and Suraj Malladi