IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v278y2019i1p105-119.html
   My bibliography  Save this article

Influence maximization with deactivation in social networks

Author

Listed:
  • Tanınmış, Kübra
  • Aras, Necati
  • Altınel, I.K.

Abstract

In this paper, we consider an extension of the well-known Influence Maximization Problem in a social network which deals with finding a set of k nodes to initiate a diffusion process so that the total number of influenced nodes at the end of the process is maximized. The extension focuses on a competitive variant where two decision makers are involved. The first one, the leader, tries to maximize the total influence spread by selecting the most influential nodes and the second one, the follower, tries to minimize it by deactivating some of these nodes. The formulated bilevel model is solved by complete enumeration for small-sized instances and by a matheuristic for large-sized instances. In both cases, the lower level problem, which is a stochastic optimization problem, is approximated via the Sample Average Approximation method.

Suggested Citation

  • Tanınmış, Kübra & Aras, Necati & Altınel, I.K., 2019. "Influence maximization with deactivation in social networks," European Journal of Operational Research, Elsevier, vol. 278(1), pages 105-119.
    • Handle: RePEc:eee:ejores:v:278:y:2019:i:1:p:105-119
    DOI: 10.1016/j.ejor.2019.04.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719303303
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.04.010?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Mehdi Hemmati & J. Cole Smith & My Thai, 2014. "A cutting-plane algorithm for solving a weighted influence interdiction problem," Computational Optimization and Applications, Springer, vol. 57(1), pages 71-104, January.
    3. Jeffrey W. Ohlmann & Barrett W. Thomas, 2007. "A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 80-90, February.
    4. Hao-Hsiang Wu & Simge Küçükyavuz, 2018. "A two-stage stochastic programming approach for influence maximization in social networks," Computational Optimization and Applications, Springer, vol. 69(3), pages 563-595, April.
    5. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    6. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. CORNUEJOLS, Gérard & FISHER, Marshall L. & NEMHAUSER, George L., 1977. "Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms," LIDAM Reprints CORE 292, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Li, Pei & Yu, Jianyong & Liu, Jianxun & Zhou, Dong & Cao, Buqing, 2020. "Generating weighted social networks using multigraph," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    2. Tavasoli, Ali & Shakeri, Heman & Ardjmand, Ehsan & Young, William A., 2021. "Incentive rate determination in viral marketing," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1169-1187.

    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. Awi Federgruen & Nan Yang, 2008. "Selecting a Portfolio of Suppliers Under Demand and Supply Risks," Operations Research, INFORMS, vol. 56(4), pages 916-936, August.
    2. Jon Lee & Maxim Sviridenko & Jan Vondrák, 2010. "Submodular Maximization over Multiple Matroids via Generalized Exchange Properties," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 795-806, November.
    3. Kübra Tanınmış & Markus Sinnl, 2022. "A Branch-and-Cut Algorithm for Submodular Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2634-2657, September.
    4. Kurt Spielberg, 2007. "IP over 40+ Years at IBM Scientific Centers and Marketing," Annals of Operations Research, Springer, vol. 149(1), pages 195-208, February.
    5. Niv Buchbinder & Moran Feldman & Roy Schwartz, 2017. "Comparing Apples and Oranges: Query Trade-off in Submodular Maximization," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 308-329, May.
    6. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    7. Klages-Mundt, Ariah & Minca, Andreea, 2022. "Optimal intervention in economic networks using influence maximization methods," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1136-1148.
    8. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2017. "Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 767-779, November.
    9. Kung, Ling-Chieh & Liao, Wei-Hung, 2018. "An approximation algorithm for a competitive facility location problem with network effects," European Journal of Operational Research, Elsevier, vol. 267(1), pages 176-186.
    10. Hao-Hsiang Wu & Simge Küçükyavuz, 2018. "A two-stage stochastic programming approach for influence maximization in social networks," Computational Optimization and Applications, Springer, vol. 69(3), pages 563-595, April.
    11. Niv Buchbinder & Moran Feldman, 2019. "Constrained Submodular Maximization via a Nonsymmetric Technique," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 988-1005, August.
    12. Zhigang Li & Mingchuan Zhang & Junlong Zhu & Ruijuan Zheng & Qikun Zhang & Qingtao Wu, 2018. "Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization," Complexity, Hindawi, vol. 2018, pages 1-11, December.
    13. Hao Shen & Yong Liang & Zuo-Jun Max Shen, 2021. "Reliable Hub Location Model for Air Transportation Networks Under Random Disruptions," Manufacturing & Service Operations Management, INFORMS, vol. 23(2), pages 388-406, March.
    14. Ariah Klages-Mundt & Andreea Minca, 2021. "Optimal Intervention in Economic Networks using Influence Maximization Methods," Papers 2102.01800, arXiv.org, revised Mar 2023.
    15. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    16. 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.
    17. Kahr, Michael & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Benders decomposition for competitive influence maximization in (social) networks," Omega, Elsevier, vol. 100(C).
    18. George Nemhauser, 2007. "Hooked on IP," Annals of Operations Research, Springer, vol. 149(1), pages 157-161, February.
    19. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    20. Dam, Tien Thanh & Ta, Thuy Anh & Mai, Tien, 2022. "Submodularity and local search approaches for maximum capture problems under generalized extreme value models," European Journal of Operational Research, Elsevier, vol. 300(3), pages 953-965.

    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:eee:ejores:v:278:y:2019:i:1:p:105-119. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.