IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i3p1345-1365.html
   My bibliography  Save this article

Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem

Author

Listed:
  • S. Raghavan

    (Robert H. Smith School of Business & Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

  • Rui Zhang

    (Leeds School of Business, University of Colorado, Boulder, Colorado 80309)

Abstract

Motivated by applications arising on social networks, we study a generalization of the celebrated dominating set problem called the Positive Influence Dominating Set (PIDS). Given a graph G with a set V of nodes and a set E of edges, each node i in V has a weight b i , and a threshold requirement g i . We seek a minimum weight subset T of V , so that every node i not in T is adjacent to at least g i members of T . When g i is one for all nodes, we obtain the weighted dominating set problem. First, we propose a strong and compact extended formulation for the PIDS problem. We then project the extended formulation onto the space of the natural node-selection variables to obtain an equivalent formulation with an exponential number of valid inequalities. Restricting our attention to trees, we show that the extended formulation is the strongest possible formulation, and its projection (onto the space of the node variables) gives a complete description of the PIDS polytope on trees. We derive the necessary and sufficient facet-dening conditions for the valid inequalities in the projection and discuss their polynomial time separation. We embed this (exponential size) formulation in a branch-and-cut framework and conduct computational experiments using real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. On a test-bed of 100 real-world graph instances, our approach finds solutions that are on average 0.2% from optimality and solves 51 out of the 100 instances to optimality. Summary of Contribution: In influence maximization problems, a decision maker wants to target individuals strategically to cause a cascade at a minimum cost over a social network. These problems have attracted significant attention as their applications can be found in many different domains including epidemiology, healthcare, marketing, and politics. However, computationally solving large-scale influence maximization problems to near optimality remains a substantial challenge for the computing community, which thus represent significant opportunities for the development of operations-research based models, algorithms, and analysis in this interface. This paper studies the positive influence dominating set (PIDS) problem, an influence maximization problem on social networks that generalizes the celebrated dominating set problem. It focuses on developing exact methods for solving large instances to near optimality. In other words, the approach results in strong bounds, which then provide meaningful comparative benchmarks for heuristic approaches. The paper first shows that straightforward generalizations of well-known formulations for the dominating set problem do not yield strong (i.e., computationally viable) formulations for the PIDS problem. It then strengthens these formulations by proposing a compact extended formulation and derives its projection onto the space on the natural node-selection variables, resulting in two equivalent (stronger) formulations for the PIDS problem. The projected formulation on the natural node-variables contains a new class of valid inequalities that are shown to be facet-defining for the PIDS problem. These theoretical results are complemented by in-depth computational experiments using a branch-and-cut framework, on a testbed of 100 real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. They demonstrate the effectiveness of the proposed formulation in solving large scale problems finding solutions that are on average 0.2% from optimality and solving 51 of the 100 instances to optimality.

Suggested Citation

  • S. Raghavan & Rui Zhang, 2022. "Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1345-1365, May.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1345-1365
    DOI: 10.1287/ijoc.2021.1144
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1144
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1144?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    2. Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
    3. Markus Leitner & Ivana Ljubić & Markus Sinnl, 2015. "A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 118-134, February.
    4. Anurag Verma & Austin Buchanan & Sergiy Butenko, 2015. "Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 164-177, February.
    5. Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.
    6. Bin Zhang & Paul A. Pavlou & Ramayya Krishnan, 2018. "On Direct vs. Indirect Peer Influence in Large Social Networks," Information Systems Research, INFORMS, vol. 29(2), pages 292-314, June.
    7. Güney, Evren & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Large-scale influence maximization via maximal covering location," European Journal of Operational Research, Elsevier, vol. 289(1), pages 144-164.
    8. Lin, Geng & Guan, Jian & Feng, Huibin, 2018. "An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 500(C), pages 199-209.
    9. Jose L. Walteros & Austin Buchanan, 2020. "Why Is Maximum Clique Often Easy in Practice?," Operations Research, INFORMS, vol. 68(6), pages 1866-1895, November.
    10. Sunil Chopra & Bartosz Filipecki & Kangbok Lee & Minseok Ryu & Sangho Shim & Mathieu Van Vyve, 2017. "An extended formulation of the convex recoloring problem on a tree," LIDAM Reprints CORE 2920, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Thang N. Dinh & Yilin Shen & Dung T. Nguyen & My T. Thai, 2014. "On the approximability of positive influence dominating set in social networks," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 487-503, April.
    12. Robert M. Bond & Christopher J. Fariss & Jason J. Jones & Adam D. I. Kramer & Cameron Marlow & Jaime E. Settle & James H. Fowler, 2012. "A 61-million-person experiment in social influence and political mobilization," Nature, Nature, vol. 489(7415), pages 295-298, September.
    13. Xu Zhu & Jieun Yu & Wonjun Lee & Donghyun Kim & Shan Shan & Ding-Zhu Du, 2010. "New dominating sets in social networks," Journal of Global Optimization, Springer, vol. 48(4), pages 633-642, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. S. Raghavan & Rui Zhang, 2022. "Influence Maximization with Latency Requirements on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 710-728, March.
    2. Weidong Chen & Hao Zhong & Lidong Wu & Ding-Zhu Du, 2022. "A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 1-20, August.
    3. Yuho Chung & Yiwei Li & Jianmin Jia, 2021. "Exploring embeddedness, centrality, and social influence on backer behavior: the role of backer networks in crowdfunding," Journal of the Academy of Marketing Science, Springer, vol. 49(5), pages 925-946, September.
    4. Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.
    5. Veremyev, Alexander & Boginski, Vladimir & Pasiliao, Eduardo L. & Prokopyev, Oleg A., 2022. "On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs," European Journal of Operational Research, Elsevier, vol. 297(1), pages 86-101.
    6. Yan Leng & Xiaowen Dong & Esteban Moro & Alex Pentland, 2024. "Long-Range Social Influence in Phone Communication Networks on Offline Adoption Decisions," Information Systems Research, INFORMS, vol. 35(1), pages 318-338, March.
    7. Balasundaram, Balabhaskar & Borrero, Juan S. & Pan, Hao, 2022. "Graph signatures: Identification and optimization," European Journal of Operational Research, Elsevier, vol. 296(3), pages 764-775.
    8. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. David Bergman & Andre A. Cire & Willem-Jan van Hoeve & J. N. Hooker, 2016. "Discrete Optimization with Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 47-66, February.
    10. Johnson, Nathan & Turnbull, Benjamin & Reisslein, Martin, 2022. "Social media influence, trust, and conflict: An interview based study of leadership perceptions," Technology in Society, Elsevier, vol. 68(C).
    11. Alan Gerber & Mitchell Hoffman & John Morgan & Collin Raymond, 2020. "One in a Million: Field Experiments on Perceived Closeness of the Election and Voter Turnout," American Economic Journal: Applied Economics, American Economic Association, vol. 12(3), pages 287-325, July.
    12. Kenju Kamei & Louis Putterman & Jean-Robert Tyran, 2019. "Civic Engagement as a Second-Order Public Good: The Cooperative Underpinnings of the Accountable State," Discussion Papers 19-10, University of Copenhagen. Department of Economics.
    13. Ruyi Ge & Juan Feng & Bin Gu, 2016. "Borrower’s default and self-disclosure of social media information in P2P lending," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 2(1), pages 1-6, December.
    14. Jiang, Lincheng & Zhao, Xiang & Ge, Bin & Xiao, Weidong & Ruan, Yirun, 2019. "An efficient algorithm for mining a set of influential spreaders in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 58-65.
    15. Yingli Ran & Zhao Zhang & Shaojie Tang & Ding-Zhu Du, 2021. "Breaking the r max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 774-784, May.
    16. Kristina Gavin Bigsby & Jeffrey W. Ohlmann & Kang Zhao, 2017. "Online and Off the Field: Predicting School Choice in College Football Recruiting from Social Media Data," Decision Analysis, INFORMS, vol. 14(4), pages 261-273, December.
    17. Yann Algan & Quoc-Anh Do & Nicolò Dalvit & Alexis Le Chapelain & Yves Zenou, 2015. "How Social Networks Shape Our Beliefs: A Natural Experiment among Future French Politicians," Working Papers hal-03459820, HAL.
    18. Mechtenberg, Lydia & Tyran, Jean-Robert, 2019. "Voter motivation and the quality of democratic choice," Games and Economic Behavior, Elsevier, vol. 116(C), pages 241-259.
    19. Daniele Barchiesi & Helen Susannah Moat & Christian Alis & Steven Bishop & Tobias Preis, 2015. "Quantifying International Travel Flows Using Flickr," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-8, July.
    20. repec:spo:wpmain:info:hdl:2441/78vacv4udu92eq3fec89svm9uv is not listed on IDEAS
    21. Carolin V. Zorell, 2020. "Nudges, Norms, or Just Contagion? A Theory on Influences on the Practice of (Non-)Sustainable Behavior," Sustainability, MDPI, vol. 12(24), pages 1-21, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1345-1365. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.