A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks

References

• Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theoret. Comput. Sci. 411(44):4017–4022.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
• Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discrete Optim. 8(1):87–96.Google Scholar
• Chen N (2009) On the approximability of influence in social networks. SIAM J. Discrete Math. 23(3):1400–1415.Google Scholar
• Chen W, Castillo C, Lakshmanan LV (2013) Information and Influence Propagation in Social Networks (Morgan & Claypool Publishers, San Rafael, CA).Google Scholar
• Chiang CY, Huang LH, Li BJ, Wu J, Yeh HG (2013) Some results on the target set selection problem. J. Combin. Optim. 25(4):702–715.Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, New York).Google Scholar
• Cordasco G, Gargano L, Rescigno AA, Vaccaro U (2015) Optimizing spread of influence in social networks via partial incentives. Scheideler C, ed. Structural Information and Communication Complexity (Springer, New York), 119–134.Google Scholar
• Granovetter M (1978) Threshold models of collective behavior. Amer. J. Sociol. 83(6):1420–1443.Google Scholar
• Grötschel M, Jünger M, Reinelt G (1985) On the acyclic subgraph polytope. Math. Programming 33(1):28–42.Google Scholar
• Hagberg AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using networkX. Varoquaux G, Vaught T, Millman J, eds. Proc. 7th Python Sci. Conf., Pasadena, CA, 11–15.Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, New York).Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 137–146.Google Scholar
• Kunegis J (2017) Konect network dataset – KONECT. Accessed October 15, 2018, http://konect.uni-koblenz.de/networks/konect.Google Scholar
• Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. Accessed October 15, 2018, http://snap.stanford.edu/data.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, Heidelberg, Germany), 368–376.Google Scholar
• Nemhauser G, Wolsey L (1988) Integer and Combinatorial Optimization (Wiley, New York).Google Scholar
• Newman A, Vempala S (2001) Fences are futile: On relaxations for the linear ordering problem. Aardal K, Gerards B, eds. Integer Programming and Combinatorial Optimization—IPCO 2001, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 333–347.Google Scholar
• Raghavan S, Zhang R (2018a) Rapid influence maximization on social networks: The positive influence dominating set problem. Working paper, University of Maryland, College Park.Google Scholar
• Raghavan S, Zhang R (2018b) Weighted target set selection on tress and cycles. Working paper, University of Maryland, College Park.Google Scholar
• Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Menlo Park, CA), 4292–4293.Google Scholar
• Shakarian P, Eyre S, Paulo D (2013) A scalable heuristic for viral marketing under the tipping model. Soc. Network Anal. Mining 3(4):1225–1248.Google Scholar
• Spencer G, Howarth R (2013) Maximizing the spread of stable influence: Leveraging norm-driven moral-motivation for green behavior change in networks. CoRR, abs/1309.6455. Accessed October 15, 2018, http://arxiv.org/abs/1309.6455.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. Theoret. Comput. Sci. 412(3):265–269.Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440–442.Google Scholar