Seeding with Costly Network Information

References

• Akbarpour M, Malladi S, Saberi A (2020) Just a few seeds more: Value of network information for diffusion. Preprint, submitted November 1, 2017, https://dx.doi.org/10.2139/ssrn.3062830.Google Scholar
• Alon N, Fischer E, Krivelevich M, Szegedy M (2000) Efficient testing of large graphs. Combinatorica 20(4):451–476.Crossref, Google Scholar
• Alon N, Fischer E, Newman I, Shapira A (2009) A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM J. Comput. 39(1):143–167.Crossref, Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Proc. 25th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1497–1514.Google Scholar
• Balkanski E, Immorlica N, Singer Y (2017a) The importance of communities for learning to influence. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Long Beach, CA), 5862–5871.Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2016) The power of optimization from samples. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Long Beach, CA) 4017–4025.Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2017b) The limitations of optimization from samples. Proc. 49th Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 1016–1027.Google Scholar
• Banerjee A, Chandrasekhar AG, Duflo E, Jackson MO (2013) The diffusion of microfinance. Science 341(6144):1236498.Crossref, Google Scholar
• Banerjee A, Chandrasekhar AG, Duflo E, Jackson MO (2019) Using gossips to spread information: Theory and evidence from two randomized controlled trials. Rev. Econom. Stud. 86(6):2453–2490.Crossref, Google Scholar
• Bateni MH, Esfandiari H, Mirrokni V (2017) Almost optimal streaming algorithms for coverage problems. Proc. 29th ACM Sympos. on Parallelism in Algorithms and Architectures (ACM, New York), 13–23.Google Scholar
• Bateni M, Esfandiari H, Mirrokni V (2018) Optimal distributed submodular optimization via sketching. Proc. 24th ACM SIGKDD Internat. Conf. on Knowledge Discovery & Data Mining (ACM, New York), 1138–1147.Google Scholar
• Behrman JR, Kohler HP, Watkins SC (2002) Social networks and changes in contraceptive use over time: Evidence from a longitudinal study in rural Kenya. Demography 39(4):713–738.Crossref, Google Scholar
• Bollobás B (2001) Random Graphs (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. Proc. 25th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 946–957.Google Scholar
• Cai J, De Janvry A, Sadoulet E (2015) Social networks and the decision to insure. Amer. Econom. J. Appl. Econom. 7(2):81–108.Crossref, Google Scholar
• Catanese SA, De Meo P, Ferrara E, Fiumara G, Provetti A (2011) Crawling Facebook for social network analysis purposes. Proc. Internat. Conf. on Web Intelligence, Mining and Semantics, 1–8.Google Scholar
• Chami GF, Ahnert SE, Kabatereine NB, Tukahebwa EM (2017) Social network fragmentation and community health. Proc. National Acad. Sci. USA 114(36):E7425–E7431.Crossref, Google Scholar
• Chazelle B, Rubinfeld R, Trevisan L (2005) Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput. 34(6):1370–1379.Crossref, Google Scholar
• Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. Proc. 15th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 199–208.Google Scholar
• Chen W, Lin T, Tan Z, Zhao M, Zhou X (2016) Robust influence maximization. Proc. 22nd ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 795–804.Google Scholar
• Chin A, Eckles D, Ugander J (2022) Evaluating stochastic seeding strategies in networks. Management Sci. 68(3):1714–1736.Google Scholar
• Christakis NA, Fowler JH (2010) Social network sensors for early detection of contagious outbreaks. PLoS One 5(9):e12948.Crossref, Google Scholar
• Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91(24):247901.Crossref, Google Scholar
• Cohen E, Delling D, Pajor T, Werneck RF (2014) Sketch-based influence maximization and computation: Scaling up with guarantees. Proc. 23rd Internat. Conf. on Inform. and Knowledge Management (ACM, New York), 629–638.Google Scholar
• Domingos P, Richardson M (2001) Mining the network value of customers. Proc. 7th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 57–66.Google Scholar
• Eckles D, Esfandiari H, Mossel E, Rahimian MA (2019) Seeding with costly network information. Proc. 2019 ACM Conf. on Econom. and Comput. (ACM, New York), 421–422.Google Scholar
• Esfandiari H, Mitzenmacher M (2018) Metric sublinear algorithms via linear sampling. 59th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 11–22.Google Scholar
• Feld SL (1991) Why your friends have more friends than you do. Amer. J. Sociol. 96(6):1464–1477.Crossref, Google Scholar
• Feng C, Fu L, Jiang B, Zhang H, Wang X, Tang F, Chen G (2020) Neighborhood matters: Influence maximization in social networks with limited access. IEEE Trans. Knowledge Data Engrg. ePub ahead of print August 10, https://doi.org.10.1109/TKDE.2020.3015387.Crossref, Google Scholar
• Flodgren G, Parmelli E, Doumit G, Gattellari M, O’Brien MA, Grimshaw J, Eccles MP (2011) Local opinion leaders: Effects on professional practice and healthcare outcomes. Cochrane Database Systems Rev. 2011(8):CD000125.Google Scholar
• Godes D, Mayzlin D (2009) Firm-created word-of-mouth communication: Evidence from a field test. Marketing Sci. 28(4):721–739.Link, Google Scholar
• Goel S, Salganik MJ (2010) Assessing respondent-driven sampling. Proc. National Acad. Sci. USA 107(15):6743–6747.Crossref, Google Scholar
• Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42:427–486.Google Scholar
• Gomez-Rodriguez M, Leskovec J, Krause A (2012) Inferring networks of diffusion and influence. ACM Trans. Knowledge Discovery Data 5(4):1–37.Crossref, Google Scholar
• Gonen M, Ron D, Shavitt Y (2011) Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math. 25(3):1365–1411.Crossref, Google Scholar
• Goyal A, Bonchi F, Lakshmanan LVS (2010) Learning influence probabilities in social networks. Proc. 3rd ACM Internat. Conf. on Web Search and Data Mining (ACM, New York), 241–250.Google Scholar
• He X, Kempe D (2016) Robust influence maximization. Proc. 22nd ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 885–894.Google Scholar
• He X, Kempe D (2018) Stability and robustness in influence maximization. ACM Trans. Knowledge Discovery Data 12(6):66:1–66:34.Google Scholar
• Heckathorn DD, Cameron CJ (2017) Network sampling: From snowball and multiplicity to respondent-driven sampling. Annu. Rev. Sociol. 43:101–119.Crossref, Google Scholar
• Hinz O, Skiera B, Barrot C, Becker JU (2011) Seeding strategies for viral marketing: An empirical comparison. J. Marketing 75(6):55–71.Crossref, Google Scholar
• Horel T, Singer Y (2015) Scalable methods for adaptively seeding a social network. Proc. 24th Internat. Conf. on World Wide Web, 441–451.Google Scholar
• Indyk P (1999) Sublinear time algorithms for metric space problems. Proc. 31st Annual ACM Sympos. on Theory of Comput. (ACM, New York), 428–434.Google Scholar
• Janson S, Luczak T, Rucinski A (2011) Random Graphs, vol. 45 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Karimi M, Lucic M, Hassani H, Krause A (2017) Stochastic submodular maximization: The case of coverage functions. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Long Beach, CA) 6853–6863.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 137–146.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2005) Influential nodes in a diffusion model for social networks. Proc. 32nd Internat. Colloquium on Automata, Languages, and Programming (Springer, Berlin), 1127–1138.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11(4):105–147.Crossref, Google Scholar
• Kim DA, Hwong AR, Stafford D, Hughes DA, O’Malley AJ, Fowler JH, Christakis NA (2015) Social network targeting to maximise population behaviour change: A cluster randomised controlled trial. Lancet 386(9989):145–153.Crossref, Google Scholar
• Kumar V, Sudhir K (2019) Can friends seed more buzz and adoption? Cowles Foundation Discussion Paper No. 2178, Yale University, New Haven, CT.Google Scholar
• Kumar V, Krackhardt D, Feld S (2018) Network interventions based on inversity: Leveraging the friendship paradox in unknown network structures. Working paper, Yale University, New Haven, CT.Google Scholar
• Kumar R, Moseley B, Vassilvitskii S, Vattani A (2015) Fast greedy algorithms in MapReduce and streaming. ACM Trans. Parallel Comput. 2(3):14.Crossref, Google Scholar
• Lattanzi S, Singer Y (2015) The power of random neighbors in social networks. Proc. 8th ACM Internat. Conf. on Web Search and Data Mining (ACM, New York), 77–86.Google Scholar
• Leskovec J, Faloutsos C (2006) Sampling from large graphs. Proc. 12th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 631–636.Google Scholar
• Libai B, Muller E, Peres R (2013) Decomposing the value of word-of-mouth seeding programs: Acceleration vs. expansion. J. Marketing Res. 50(2):161–176.Crossref, Google Scholar
• Lungeanu A, McKnight M, Negron R, Munar W, Christakis NA, Contractor NS (2021) Using Trellis software to enhance high-quality large-scale network data collection in the field. Soc. Networks 66:171–184.Crossref, Google Scholar
• Manshadi V, Misra S, Rodilitz S (2020) Diffusion in random networks: Impact of degree distribution. Oper. Res. 68(6):1722–1741.Link, Google Scholar
• Mihara S, Tsugawa S, Ohsaki H (2015) Influence maximization problem for unknown social networks. Proc. Internat. Conf. on Advances in Soc. Networks Analysis and Mining (IEE/ACM, New York), 1539–1546.Google Scholar
• Mihara S, Tsugawa S, Ohsaki H (2017) On the effectiveness of random jumps in an influence maximization algorithm for unknown graphs. Proc. Internat. Conf. on Inform. Networking (IEEE, New York), 395–400.Google Scholar
• Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondrák J, Krause A (2015) Lazier than lazy greedy. Proc. 29th AAAI Conf. on Artificial Intelligence (AAAI, Palo Alto, CA), 1812–1818.Google Scholar
• Mossel E, Roch S (2010) Submodularity of influence in social networks: From local to global. SIAM J. Comput. 39(6):2176–2188.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions–I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. Proc. Internat. Conf. on Management of Data, 695–710.Google Scholar
• Paluck EL, Shepherd H, Aronow PM (2016) Changing climates of conflict: A social network experiment in 56 schools. Proc. National Acad. Sci. USA 113(3):566–571.Crossref, Google Scholar
• Sadeh G, Cohen E, Kaplan H (2020) Sample complexity bounds for influence maximization. Vidick T, ed. Proc. 11th Innovations in Theoretical Computer Science Conf., vol. 151 of Leibniz Internat. Proc. in Informatics (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 29:1–29:36.Google Scholar
• Salganik MJ, Heckathorn DD (2004) Sampling and estimation in hidden populations using respondent-driven sampling. Sociol. Methodology 34(1):193–240.Crossref, Google Scholar
• Schoenebeck G, Tao B (2019) Beyond worst-case (in)approximability of nonsubmodular influence maximization. ACM Trans. Comput. Theory 11(3):12:1–12:56.Crossref, Google Scholar
• Seeman L, Singer Y (2013) Adaptive seeding in social networks. Proc. 54th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 459–468.Google Scholar
• Stein S, Eshghi S, Maghsudi S, Tassiulas L, Bellamy RKE, Jennings NR (2017) Heuristic algorithms for influence maximization in partially observable social networks. Proc. 3rd Internat. Workshop on Soc. Influence Analysis, 20–32.Google Scholar
• Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: A martingale approach. Proc. ACM SIGMOD Internat. Conf. on Management of Data, 1539–1554.Google Scholar
• Tang Y, Xiao X, Shi Y (2014) Influence maximization: Near-optimal time complexity meets practical efficiency. Proc. ACM SIGMOD Internat. Conf. on Management of Data, 75–86.Google Scholar
• Traud AL, Mucha PJ, Porter MA (2012) Social structure of Facebook networks. Phys. A 391(16):4165–4180.Crossref, Google Scholar
• van der Vaart AW, Wellner JA (1996) Weak Convergence and Empirical Processes: With Applications to Statistics (Springer-Verlag, New York).Crossref, Google Scholar
• Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining Knowledge Discovery 25(3):545–576.Crossref, Google Scholar
• Wen Z, Kveton B, Valko M, Vaswani S (2017) Online influence maximization under independent cascade model with semi-bandit feedback Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Long Beach, CA), 3022–3032.Google Scholar
• Wilder B, Immorlica N, Rice E, Tambe M (2017a) Influence maximization with an unknown network by exploiting community structure. Proc. 3rd Internat. Workshop on Social Influence Analysis, 2–7.Google Scholar
• Wilder B, Immorlica N, Rice E, Tambe M (2018) Maximizing influence in an unknown social network. Proc. 32nd AAAI Conf. on Artificial Intelligence (AAAI, Palo Alto, CA), 4743–4750.Google Scholar
• Wilder B, Yadav A, Immorlica N, Rice E, Tambe M (2017b) Uncharted but not uninfluenced: Influence maximization with an uncertain network. Proc. 16th Conf. on Autonomous Agents and Multiagent Systems, 1305–1313.Google Scholar
• Wu Q, Li Z, Wang H, Chen W, Wang H (2019) Factorization bandits for online influence maximization. Proc. 25th ACM SIGKDD Internat. Conf. on Knowledge Discovery & Data Mining, 636–646.Google Scholar
• Yadav A, Wilder B, Rice E, Petering R, Craddock J, Yoshioka-Maxwell A, Hemler M, et al. (2017) Influence maximization in the field: The arduous journey from emerging to deployed application. Proc. 16th Conf. on Autonomous Agents and Multiagent Systems, 150–158.Google Scholar