Abstract
Spread of influence in a network can be modeled and studied within the concept of dynamic monopolies in graphs. We give an integer programming formulation for finding a minimum dynamic monopoly in an undirected graph. The corresponding 0–1 polytope and its facets are studied and several families of facet defining inequalities are introduced. Computational experiments have been performed to show the strength of the IP formulation and its facet defining inequalities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Gurobi Optimization Inc., Gurobi Optimizer Reference Manual (2016), http://www.gurobi.com.
T. Christof, M. Stoer, and A. Loebel, PORTA - a polyhedron representation transformation algorithm, Version 1.3 (1997), http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA.
If f and g are Boolean functions on \( \{0,1\}^n \),then \( f\le g \) means \( f(x) \le g(x) \) for all \( x \in \{0,1\}^n \).
References
Ackerman, E., Ben-Zwi, O., & Wolfovitz, G. (2010). Combinatorial model and bounds for target set selection. Theoretical Computer Science, 411(44–46), 4017–4022. https://doi.org/10.1016/j.tcs.2010.08.021.
Chang, C. L., & Lyuu, Y. D. (2013). Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades. Theoretical Computer Science, 468, 37–49. https://doi.org/10.1016/j.tcs.2012.11.016, http://www.sciencedirect.com/science/article/pii/S0304397512010468.
Flocchini, P., Lodi, E., Luccio, F., Pagli, L., & Santoro, N. (2004). Dynamic monopolies in Tori. Discrete Applied Mathematics 137(2):197–212. https://doi.org/10.1016/S0166-218X(03)00261-0, 1st international workshop on algorithms, combinatorics, and optimization in interconnection networks (IWACOIN ’99)
Günneç, D., Raghavan, S., & Zhang, R. (2017). Tailored incentives and least cost influence maximization on social networks. http://terpconnect.umd.edu/~raghavan/preprints/LCIP.pdf
Hammer, P. L., Johnson, E. L., & Peled, U. N. (1975). Facets of regular 0–1 polytopes. Mathematical Programming, 8, 179–206. https://doi.org/10.1007/BF01580442.
Kempe, D., Kleinberg, J., & Tardos, E. (2015). Maximizing the spread of influence through a social network. Theory of Computation, 11, 105–147. https://doi.org/10.4086/toc.2015.v011a004.
Khoshkhah, K., Soltani, H., & Zaker, M. (2012). On dynamic monopolies of graphs: the average and strict majority thresholds. Discrete Optimization 9(2):77–83. http://www.sciencedirect.com/science/article/pii/S1572528612000151
Khoshkhah, K., Nemati, M., Soltani, H., & Zaker, M. (2013). A study of monopolies in graphs. Graphs and Combinatorics, 29(5), 1417–1427. https://doi.org/10.1007/s00373-012-1214-7.
Khoshkhah, K., Soltani, H., & Zaker, M. (2014). Dynamic monopolies in directed graphs: The spread of unilateral influence in social networks. Discrete Applied Mathematics, 171, 81–89. https://doi.org/10.1016/j.dam.2014.02.006.
Moazzez, B., & Soltani, H. (2018). Integer programming approach to static monopolies in graphs. Journal of Combinatorial Optimization, 35(4), 1009–1041. https://doi.org/10.1007/s10878-018-0256-z.
Nemhauser, G., & Wolsey, L. (1999). Integer and combinatorial optimization. Wiley-interscience series in discrete mathematics and optimization. New York: Wiley, reprint of the 1988 original, A Wiley-Interscience Publication
Soltani, H., & Zaker, M. (2014). On dynamic monopolies of graphs with probabilistic thresholds. Bulletin of the Australian Mathematical Society, 90(3), 363–375. https://doi.org/10.1017/S0004972714000604.
Zaker, M. (2012). On dynamic monopolies of graphs with general thresholds. Discrete Mathematics, 312(6), 1136–1143. https://doi.org/10.1016/j.disc.2011.11.038.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Soltani, H., Moazzez, B. A polyhedral study of dynamic monopolies. Ann Oper Res 279, 71–87 (2019). https://doi.org/10.1007/s10479-018-3107-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-3107-5