Seeding with Costly Network Information

Dean Eckles (), Hossein Esfandiari (), Elchanan Mossel () and M. Amin Rahimian ()
Additional contact information
Dean Eckles: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Hossein Esfandiari: Google Research, New York, New York 10011
Elchanan Mossel: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
M. Amin Rahimian: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261

Operations Research, 2022, vol. 70, issue 4, 2318-2348

Abstract: We study the task of selecting k nodes, in a social network of size n , to seed a diffusion with maximum expected spread size, under the independent cascade model with cascade probability p . 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 ε n loss and show that the squared dependence of sample size on k 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 p 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 p 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.

Keywords: Market Analytics and Revenue Management; influence maximization; submodular maximization; query oracle; viral marketing (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2290 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:2318-2348

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().