Just a Few Seeds More: The Inflated Value of Network Data for Diffusion. with Suraj Malladi and Amin Saberi

          @misc{ scivideos_22846,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/tbd-487},
            author = {},
            keywords = {},
            language = {en},
            title = {Just a Few Seeds More: The Inflated Value of Network Data for Diffusion. with Suraj Malladi and Amin Saberi},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {oct},
            note = {22846 see, \url{https://scivideos.org/simons-institute/22846}}
          }
          

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.