Abstract
When a behavior (e.g., product adoption) may spread through a social network, it can be advantageous to consider network structure when deciding where to seed that behavior. Much prior work in this area assumes the network is already or costlessly observed, but some recent empirical work employs methods — motivated by the cost of measuring the network — that only rely on local network information (e.g., by exploiting the friendship paradox). Unlike methods for fully observed networks, however, these methods do not come with guarantees about how large of a cascade they will produce. Here we propose and analyze algorithms that make a bounded number of queries of the network structure and provide almost tight approximation guarantees. We test our algorithms on empirical network data to quantify the trade-off between the cost of obtaining more refined network information, and the benefit of the added information for guiding improved seeding policies.
Joint work with Hossein Esfandiari, Elchanan Mossel, and M. Amin Rahimian. Also featuring additional joint work with Alex Chin and Johan Ugander.