Influence Maximization with Latency Requirements on Social Networks

References

• Adcock AB, Sullivan BD, Mahoney MW (2013) Tree-like structure in large social and information networks. Proc. IEEE 13th Internat. Conf. on Data Mining (IEEE, New York), 1–10.Crossref, Google Scholar
• Balas E, Pulleyblank W (1983) The perfectly matchable subgraph polytope of a bipartite graph. Networks 13(4):495–516.Crossref, Google Scholar
• Balasundaram B, Butenko S, Hicks IV (2011) Clique relaxations in social network analysis: The maximum k-plex problem. Oper. Res. 59(1):133–142.Link, Google Scholar
• Banerjee S, Jenamani M, Pratihar DK (2020) A survey on influence maximization in a social network. Knowledge Inform. Systems 62:3417–3455.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Sigismondi G, Vance P (1993) Formulating a mixed integer programming problem to improve solvability. Oper. Res. 41(6):1013–1019.Link, 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.Crossref, Google Scholar
• Bourne F (1957) Group influence in marketing and public relations. Some Applications of Behavioral Research (UNESCO, Basel, Switzerland), 207–225.Google Scholar
• Brown J, Reingen P (1987) Social ties and word-of-mouth referral behavior. J. Consumer Res. 14(3):350–362.Crossref, Google Scholar
• Chen N (2009) On the approximability of influence in social networks. SIAM J. Discrete Math. 23(3):1400–1415.Crossref, Google Scholar
• Chen W, Castillo C, Lakshmanan LV (2013) Information and Influence Propagation in Social Networks (Morgan & Claypool Publishers).Crossref, Google Scholar
• Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inform. Comput. 206(11):1264–1275.Crossref, Google Scholar
• Coleman J, Katz E, Menzel H (1966) Medical Innovation: A Diffusion Study (Bobbs-Merrill, Indianapolis, IN).Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, New York).Crossref, Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms (MIT Press, Cambridge, MA).Google Scholar
• Dhawan A, Rink M (2015) Positive influence dominating set generation in social networks. Proc. Internat. Conf. on Computing and Network Communications (IEEE, New York), 112–117.Crossref, Google Scholar
• Dinh TN, Shen Y, Nguyen DT, Thai MT (2014) On the approximability of positive influence dominating set in social networks. J. Combination Optim. 27(3):487–503.Crossref, Google Scholar
• Fischetti M, Kahr M, Leitner M, Monaci M, Ruthmair M (2018) Least cost influence propagation in (social) networks. Math. Programming Ser. B 170(1):293–325.Crossref, Google Scholar
• Goel S, Anderson A, Hofman J, Watts DJ (2015) The structural virality of online diffusion. Management Sci. 62(1):180–196.Link, Google Scholar
• Goemans MX (1994) The Steiner tree polytope and related polyhedra. Math. Programming 63(1-3):157–182.Crossref, Google Scholar
• Goyal A, Lu W, Lakshmanan LV (2011) Celf++ optimizing the greedy algorithm for influence maximization in social networks. Proc. 20th Internat. Conf. Companion on World Wide Web (ACM, New York), 47–48.Google Scholar
• Granovetter M (1978) Threshold models of collective behavior. Amer. J. Sociol. 83(6):1420–1443.Crossref, Google Scholar
• Greaves CJ, Reddy P, Sheppard K (2010) Supporting behaviour change for diabetes prevention. Diabetes Prevention in Practice (TUMAINI Institute for Prevention Management), 19–29.Google Scholar
• Günneç D, Raghavan S (2017) Integrating social network effects in the share-of-choice problem. Decision Sci. 48(6):1098–1131.Crossref, Google Scholar
• Günneç D, Raghavan S, Zhang R (2020a) A branch-and-cut approach for the least cost influence problem on social networks. Networks 76(1):84–105.Crossref, Google Scholar
• Günneç D, Raghavan S, Zhang R (2020b) Least-cost influence maximization on social networks. INFORMS J. Comput. 32(2):289–302.Abstract, Google Scholar
• Haynes T, Hedetniemi S, Slater P (1998a) Domination in Graphs: Advanced Topics (CRC Press, Boca Raton, FL).Google Scholar
• Haynes T, Hedetniemi S, Slater P (1998b) Fundamentals of Domination in Graphs (CRC Press, Boca Raton, FL).Google Scholar
• Jackson MO, Malladi S, McAdams D (2020) Learning through the grapevine: The impact of noise and the breadth and depth of social networks. Working paper, Stanford University, Stanford, CA.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
• Khomami MMD, Rezvanian A, Bagherpour N, Meybodi MR (2018) Minimum positive influence dominating set and its application in influence maximization: A learning automata approach. Appl. Intelligence 48(3):570–593.Crossref, Google Scholar
• Kunegis J (2017) KONECT network data set. Accessed August 27, 2020, http:konect.cc/networks/.Google Scholar
• Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media? Proc. 19th Internat. Conf. on World Wide Web (ACM, New York), 591–600.Crossref, Google Scholar
• Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network data set collection. Accessed August 27, 2020, http://snap.stanford.edu/data.Google Scholar
• Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. Proc. 13th ACM SIGKDD Internat. Conf on Knowledge Discovery and Data Mining (ACM, New York), 420–429.Crossref, Google Scholar
• Lesser O, Tenenboim-Chekina L, Rokach L, Elovici Y (2013) Intruder or welcome friend: Inferring group membership in online social networks. Social Computing, Behavioral-Cultural Modeling and Prediction (Springer, Berlin), 368–376.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
• Li X, Smith JD, Dinh TN, Thai MT (2019) Tiptop: (Almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Trans. Networks 27(2):649–661.Crossref, Google Scholar
• Liben-Nowell D, Kleinberg J (2008) Tracing information flow on a global scale using Internet chain-letter data. Proc. National Acad. Sci. USA 105(12):4633–4638.Crossref, Google Scholar
• Lin G, Guan J, Feng H (2018) An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks. Physica A 500:199–209.Crossref, Google Scholar
• Magnanti TL, Wolsey LA (1995) Optimal trees. Handbook Oper. Res. Management Sci. 7:503–615.Google Scholar
• Nannicini G, Sartor G, Traversi E, Wolfler-Calvo R (2020) An exact algorithm for robust influence maximization. Math. Programming 183:419–453.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley, New York).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 (ACM, New York), 695–710.Google Scholar
• Pajouh FM, Balasundaram B, Hicks IV (2016) On the 2-club polytope of graphs. Oper. Res. 64(6):1466–1481.Link, Google Scholar
• Raghavan S, Zhang R (2017) Rapid influence maximization on social networks: The positive influence dominating set problem. Working paper, University of Maryland, College Park, MD.Google Scholar
• Raghavan S, Zhang R (2019) A branch-and-cut approach for the weighted target set selection problem on social networks. INFORMS J. Optim. 1(4):304–322.Link, Google Scholar
• Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. Proc. 29th AAAI Conf. on Artificial Intelligence (ACM, New York).Crossref, Google Scholar
• Saxena A (2004) On the dominating set polytope of a cycle. Working paper, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Schmidt M (2019) Calculating the true size of the influencer marketing industry. Forbes. Accessed August 27, 2020, https://www.forbes.com/sites/forbestechcouncil/2019/02/13/calculating-the-true-size-of-the-influencer-marketing-industry/#28b76073658d.Google Scholar
• Schomer A (2020) Influencer marketing: State of the social media influencer market in 2020. Business Insider. Accessed August 27, 2020, https://www.businessinsider.com/influencer-marketing-report.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 (ACM, New York), 1539–1554.Google Scholar
• Valente TW (2012) Network interventions. Science 337(6090):49–53.Crossref, Google Scholar
• Verma A, Buchanan A, Butenko S (2015) Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1):164–177.Link, Google Scholar
• Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Crossref, Google Scholar
• Walteros JL, Buchanan A (2020) Why is maximum clique often easy in practice? Oper. Res. 68(6):1866–1895.Link, Google Scholar
• Wang F, Camacho E, Xu K (2009) Positive influence dominating set in online social networks. Du D-Z, Hu X, Pardalos PM, eds. Combinatorial Optimization and Applications (Springer, Berlin), 313–321.Crossref, Google Scholar
• Wang F, Du H, Camacho E, Xu K, Lee W, Shi Y, Shan S (2011) On positive influence dominating sets in social networks. Theoretical Comput. Sci. 412(3):265–269.Crossref, Google Scholar
• Wu H-H, Küçükyavuz S (2018) A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3):563–595.Crossref, Google Scholar
• Zhang B, Pavlou P, Krishnan R (2018) On direct vs. indirect peer influence in large social networks. Inform. Systems Res. 29(2):292–314.Link, Google Scholar
• Zhu X, Yu J, Lee W, Kim D, Shan S, Du D-Z (2010) New dominating sets in social networks. J. Global Optim. 48(4):633–642.Crossref, Google Scholar