Seeding with Costly Network Information
arXiv:1905.04325 · doi:10.1287/opre.2022.2290
Abstract
We study the task of selecting nodes, in a social network of size , to seed a diffusion with maximum expected spread size, under the independent cascade model with cascade probability . Most of the previous work on this problem (known as influence maximization) focuses on efficient algorithms to approximate the optimal seed set with provable guarantees given knowledge of the entire network; however, obtaining full knowledge of the network is often very costly in practice. Here we develop algorithms and guarantees for approximating the optimal seed set while bounding how much network information is collected. First, we study the achievable guarantees using a sublinear influence sample size. We provide an almost tight approximation algorithm with an additive loss and show that the squared dependence of sample size on is asymptotically optimal when is small. We then propose a probing algorithm that queries edges from the graph and use them to find a seed set with the same almost tight approximation guarantee. We also provide a matching (up to logarithmic factors) lower-bound on the required number of edges. This algorithm is implementable in field surveys or in crawling online networks. Our probing takes as an input which may not be known in advance, and we show how to down-sample the probed edges to match the best estimate of if they are collected with a higher probability. Finally, we test our algorithms on an empirical network to quantify the tradeoff between the cost of obtaining more refined network information and the benefit of the added information for guiding improved seeding strategies.
References in corpus (15)
- Efficient Immunization Strategies for Computer Networks and Populations
- Social Structure of Facebook Networks
- Social Network Sensors for Early Detection of Contagious Outbreaks
- Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
- Crawling Facebook for Social Network Analysis Purposes
- Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
- Online Influence Maximization (Extended Version)
- Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
- Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
- Scalable Methods for Adaptively Seeding a Social Network
- Evaluating stochastic seeding strategies in networks
- Neighborhood Matters: Influence Maximization in Social Networks with Limited Access
- Subsampling large graphs and invariance in networks
- Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization
- Sample Complexity Bounds for Influence Maximization