Robustness to Dependency in Influence Maximization

References

• Acerbi C , Tasche D (2002) On the coherence of expected shortfall. J. Banking Finance 26(7):1487–1503.Crossref, Google Scholar
• Adamic LA , Glance N (2005) The political blogosphere and the 2004 U.S. election: Divided they blog. Proc. Third Internat. Workshop Link Discovery (Association for Computing Machinery, New York), 36–43.Google Scholar
• Agrawal S , Ding Y , Saberi A , Ye Y (2012) Price of correlations in stochastic optimization. Oper. Res. 60(1):150–162.Link, Google Scholar
• Akbarpour M , Jackson MO (2018) Diffusion in networks and the virtue of burstiness. Proc. Natl. Acad. Sci. USA 115(30):E6996–E7004.Crossref, Google Scholar
• Aral S , Dhillon PS (2018) Social influence maximization under empirical influence models. Nature Human Behav. 2(6):375–382.Crossref, Google Scholar
• Bass FM (1969) A new product growth for model consumer durables. Management Sci. 15(5):215–227.Link, Google Scholar
• Borgs C , Brautbar M , Chayes J , Lucier B (2014) Maximizing social influence in nearly optimal time. Proc. 2014 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 946–957.Google Scholar
• Chen W , Wang C , Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proc. 16th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, vol. 10 (Association for Computing Machinery, New York), 1029–1038.Google Scholar
• Chen W , Wang Y , Yang S (2009) Efficient influence maximization in social networks. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 199–208.Google Scholar
• Chen LL , Ma W , Orlin JB , Simchi-Levi D (2020) Distributionally robust max flows. Sympos. Simplicity Algorithms (SIAM, Philadelphia), 81–90.Google Scholar
• Chen W , Lin T , Tan Z , Zhao M , Zhou X (2016) Robust influence maximization. Proc. 22nd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 795–804.Google Scholar
• Chen L , Ma W , Natarajan K , Simchi-Levi D , Yan Z (2022) Distributionally robust linear and discrete optimization with marginals. Oper. Res. 70(3):1822–1834.Link, Google Scholar
• Chen W , Collins A , Cummings R , Ke T , Liu Z , Rincón D , Sun X , Wang Y , Wei W , Yuan Y (2011) Influence maximization in social networks when negative opinions may emerge and propagate. Proc. 2011 SIAM Internat. Conf. Data Mining (SIAM, Philadelphia), 379–390.Google Scholar
• Csardi G , Nepusz T (2006) The igraph software package for complex network research. InterJournal Complex Systems 1695:1–9.Google Scholar
• He X , Kempe D (2014) Stability of influence maximization. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, vol. 14 (Association for Computing Machinery, New York), 1256–1265.Google Scholar
• He X , Kempe D (2016) Robust influence maximization. Proc. 22nd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, vol. 16 (Association for Computing Machinery, New York), 885–894.Google Scholar
• Hoffmann J , Caramanis C (2018) The cost of uncertainty in curing epidemics. Proc. ACM Measurement Anal. Comput. Systems, vol. 2, no. 2 (Association for Computing Machinery, New York).Google Scholar
• Hunter DS , Zaman T (2022) Optimizing opinions with stubborn agents. Oper. Res. 70(4):2119–2137.Link, Google Scholar
• Kalimeris D , Kaplun G , Singer Y (2019) Robust influence maximization for hyperparametric models. ICML, vol. 97 (PMLR, Long Beach, CA), 3192–3200.Google Scholar
• Kempe D , Kleinberg J , Tardos É (2003) Maximizing the spread of influence through a social network. Proc. Ninth ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 137–146.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
• Klein Haneveld WK (1986) Robustness against dependence in PERT: An application of duality and distributions with known marginals. Stochastic Programming 84 Part I (Springer, Berlin, Heidelberg), 153–182.Crossref, Google Scholar
• Krause A , McMahan HB , Guestrin C , Gupta A (2008) Robust submodular observation selection. J. Machine Learn. Res. 9(93):2761–2801.Google Scholar
• Leskovec J , Krevl A (2014) SNAP datasets: Stanford large network data set collection. Accessed July 7, 2023, http://snap.stanford.edu/data.Google Scholar
• Leskovec J , Adamic LA , Huberman BA (2007) The dynamics of viral marketing. ACM Trans. Web 1(1):5.Crossref, Google Scholar
• Li Y , Fan J , Wang Y , Tan K-L (2018) Influence maximization on social graphs: A survey. IEEE Trans. Knowledge Data Engrg. 30(10):1852–1872.Crossref, Google Scholar
• Ma W (2020) Personal communication with the authors on an example graph indicating arbitrarily small price of correlations.Google Scholar
• Maehara T (2015) Risk averse submodular utility maximization. Oper. Res. Lett. 43(5):526–529.Crossref, Google Scholar
• Mallipeddi RR , Kumar S , Sriskandarajah C , Zhu Y (2022) A framework for analyzing influencer marketing in social networks: Selection and scheduling of influencers. Management Sci. 68(1):75–104.Link, Google Scholar
• Meilijson I , Nádas A (1979) Convex majorization with an application to the length of critical paths. J. Appl. Probab. 16(3):671–677.Crossref, Google Scholar
• Nannicini G , Sartor G , Traversi E , Wolfler-Calvo R (2019) An exact algorithm for robust influence maximization. Lodi A , Nagarajan V , eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 313–326.Crossref, Google Scholar
• Natarajan K , Song M , Teo C-P (2009) Persistency model and its applications in choice modeling. Management Sci. 55(3):453–469.Link, Google Scholar
• Nemhauser GL , Wolsey LA , Fisher ML (1978) An analysis of approximations for maximizing submodular set functions–I. Math. Program. 14(1):265–294.Crossref, Google Scholar
• Ohsaka N , Yoshida Y (2017) Portfolio optimization for influence spread. Proc. 26th Internat. Conf. World Wide Web (International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva), 977–985.Google Scholar
• Ohsaka N , Akiba T , Yoshida Y , Kawarabayashi K-I (2014) Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations. Proc. AAAI Conf. Artificial Intelligence, vol. 28 (AAAI Press, Palo Alto, CA), 138–144.Google Scholar
• Rockafellar RT , Uryasev S (2000) Optimization of conditional value-at-risk. J. Risk 2(3):21–41.Crossref, Google Scholar
• Rockafellar RT , Uryasev S (2002) Conditional value-at-risk for general loss distributions. J. Banking Finance 26(7):1443–1471.Crossref, Google Scholar
• Rũschendorf L (2013) Mathematical Risk Analysis: Dependence, Risk Bounds, Optimal Allocations and Portfolios , 2nd ed. (Springer Berlin, Heidelberg).Crossref, Google Scholar
• Sion M (1958) On general minimax theorems. Pacific J. Math. 8(1):171–176.Crossref, Google Scholar
• Staib M , Wilder B , Jegelka S (2019) Distributionally robust submodular maximization. Proc. Internat. Workshop Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 89 (PMLR, New York).Google Scholar
• Vaswani S , Kveton B , Wen Z , Ghavamzadeh M , Lakshmanan LV , Schmidt M (2017) Model-independent online learning for influence maximization. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 3530–3539.Google Scholar
• Wang X , Zhang J (2015) Process flexibility: A distribution-free bound on the performance of k-chain. Oper. Res. 63(3):555–571.Link, Google Scholar
• Watts DJ (2002) A simple model of global cascades on random networks. Proc. Natl. Acad. Sci. USA 99(9):5766–5771.Crossref, Google Scholar
• Weiss G (1986) Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability. Oper. Res. 34(4):595–605.Link, Google Scholar
• Wilder B (2018) Risk-sensitive submodular optimization. 32nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Yan Q , Guo S , Yang D (2011) Influence maximizing and local influenced community detection based on multiple spread model. Tang J , King I , Chen L , Wang J , eds. Advanced Data Mining and Applications (Springer, Berlin, Heidelberg), 82–95.Crossref, Google Scholar
• Zhang P , Chen W , Sun X , Wang Y , Zhang J (2014) Minimizing seed set selection with probabilistic coverage guarantee in a social network. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, vol. 14 (Association for Computing Machinery, New York), 1306–1315.Google Scholar