Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Seeding with Costly Network Information

Eckles, Dean and Esfandiari, Hossein and Mossel, Elchanan and Rahimian, M Amin (2022) Seeding with Costly Network Information. In: UNSPECIFIED.

Accepted Version

Download (2MB) | Preview
[img] Plain Text (licence)
Download (1kB)


<jats:p> In the presence of contagion, decision makers strategize about where in a network to intervene (e.g., seeding a new product). A large literature has developed methods for approximately optimizing the choice of k seeds to cause the largest cascade of, for example, product adoption. However, it is often impractical to measure an entire social network. In “Seeding with Costly Network Information,” Eckles, Esfandiari, Mossel, and Rahimian develop and analyze algorithms for making a bounded number of queries of a social network and then selecting k seeds. They prove hardness results for this problem and provide almost tight approximation guarantees for their proposed algorithms under widely used models of contagion. One proposed algorithm is practical for both querying online social networks and structuring in-person surveys. This framework further allows reasoning about tradeoffs between spending budget on collecting more network data versus increasing the number of seeds. </jats:p>


Social Networking:
Share |


Item Type: Conference or Workshop Item (UNSPECIFIED)
Status: Published
CreatorsEmailPitt UsernameORCID
Eckles, Dean
Esfandiari, Hossein
Mossel, Elchanan
Rahimian, M AminRAHIMIAN@pitt.eduRAHIMIAN0000-0001-9384-1041
Date: July 2022
Date Type: Publication
Journal or Publication Title: Operations Research
Volume: 70
Number: 4
Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
Page Range: 2318 - 2348
DOI or Unique Handle: 10.1287/opre.2022.2290
Schools and Programs: Swanson School of Engineering > Industrial Engineering
Refereed: Yes
ISSN: 0030-364X
Date Deposited: 06 Jun 2022 15:10
Last Modified: 24 Aug 2022 07:55


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item