Seeding with Costly Network Information
<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. How...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145811 |
| _version_ | 1826209411259957248 |
|---|---|
| author | Eckles, Dean Esfandiari, Hossein Mossel, Elchanan Rahimian, M Amin |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Eckles, Dean Esfandiari, Hossein Mossel, Elchanan Rahimian, M Amin |
| author_sort | Eckles, Dean |
| collection | MIT |
| description | <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> |
| first_indexed | 2024-09-23T14:22:05Z |
| format | Article |
| id | mit-1721.1/145811 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:22:05Z |
| publishDate | 2022 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1458112022-10-13T03:14:15Z Seeding with Costly Network Information Eckles, Dean Esfandiari, Hossein Mossel, Elchanan Rahimian, M Amin Massachusetts Institute of Technology. Department of Mathematics Sloan School of Management <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> 2022-10-12T18:42:28Z 2022-10-12T18:42:28Z 2022 2022-10-12T18:38:31Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/145811 Eckles, Dean, Esfandiari, Hossein, Mossel, Elchanan and Rahimian, M Amin. 2022. "Seeding with Costly Network Information." Operations Research, 70 (4). en 10.1287/OPRE.2022.2290 Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Eckles, Dean Esfandiari, Hossein Mossel, Elchanan Rahimian, M Amin Seeding with Costly Network Information |
| title | Seeding with Costly Network Information |
| title_full | Seeding with Costly Network Information |
| title_fullStr | Seeding with Costly Network Information |
| title_full_unstemmed | Seeding with Costly Network Information |
| title_short | Seeding with Costly Network Information |
| title_sort | seeding with costly network information |
| url | https://hdl.handle.net/1721.1/145811 |
| work_keys_str_mv | AT ecklesdean seedingwithcostlynetworkinformation AT esfandiarihossein seedingwithcostlynetworkinformation AT mosselelchanan seedingwithcostlynetworkinformation AT rahimianmamin seedingwithcostlynetworkinformation |