IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v40y2020i4d10.1007_s10878-020-00638-5.html
   My bibliography  Save this article

Influence maximization problem: properties and algorithms

Author

Listed:
  • Wenguo Yang

    (University of Chinese Academy of Sciences)

  • Yapu Zhang

    (University of Chinese Academy of Sciences)

  • Ding-Zhu Du

    (University of Texas at Dallas)

Abstract

The influence maximization problem has become one of the fundamental combinatorial optimization problems over the past decade due to its extensive applications in social networks. Although a $$1-1/e$$ 1 - 1 / e approximation ratio is easily obtained using a greedy algorithm for the submodular case, how to solve the non-submodular case and enhance the solution quality deserve further study. In this paper, based on the marginal increments, we devise a non-negative decomposition property for monotone function and a non-increasing decomposition property for monotone submodular function (NDP). According to the exchange improvement (EI), a necessary condition for an optimal solution is also proposed. With the help of NDP and EI condition, an exchange improvement algorithm is proposed to improve further the quality of the solution to the non-submodular influence maximization problem. For the influence maximization, we devise effective methods to compute the influence spread and marginal gain in a successive iteration update manner. These methods make it possible to calculate the influence spread directly and accurately. Next, we design a data-dependent approximation algorithm for a non-submodular topology change problem from a marginal increment perspective.

Suggested Citation

  • Wenguo Yang & Yapu Zhang & Ding-Zhu Du, 2020. "Influence maximization problem: properties and algorithms," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 907-928, November.
    • Handle: RePEc:spr:jcomop:v:40:y:2020:i:4:d:10.1007_s10878-020-00638-5
    DOI: 10.1007/s10878-020-00638-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00638-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-020-00638-5?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," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. 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)

    Citations

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


    Cited by:

    1. Liman Du & Shengminjie Chen & Suixiang Gao & Wenguo Yang, 2022. "Nonsubmodular constrained profit maximization from increment perspective," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2598-2625, November.

    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. Yijing Wang & Dachuan Xu & Yishui Wang & Dongmei Zhang, 2020. "Non-submodular maximization on massive data streams," Journal of Global Optimization, Springer, vol. 76(4), pages 729-743, April.
    2. 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.
    3. 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.
    4. Guanyi Wang, 2024. "Robust Network Targeting with Multiple Nash Equilibria," Papers 2410.20860, arXiv.org, revised Nov 2024.
    5. Rad Niazadeh & Negin Golrezaei & Joshua Wang & Fransisca Susan & Ashwinkumar Badanidiyuru, 2023. "Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization," Management Science, INFORMS, vol. 69(7), pages 3797-3817, July.
    6. Averbakh, Igor & Berman, Oded, 1996. "Locating flow-capturing units on a network with multi-counting and diminishing returns to scale," European Journal of Operational Research, Elsevier, vol. 91(3), pages 495-506, June.
    7. Laetitia Legalais, 2015. "L'Influence D'Un Blocage De Carriere Sur La Construction De L'Identite Professionnelle : Le Cas Des Contrôleurs De Gestion," Post-Print hal-01188764, HAL.
    8. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.
    9. Bin Liu & Miaomiao Hu, 2022. "Fast algorithms for maximizing monotone nonsubmodular functions," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1655-1670, July.
    10. repec:dgr:rugsom:99a17 is not listed on IDEAS
    11. Tami Tamir & Benny Vaksendiser, 2010. "Algorithms for storage allocation based on client preferences," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 304-324, April.
    12. Lehmann, Daniel, 2020. "Quality of local equilibria in discrete exchange economies," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 141-152.
    13. 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.
    14. Eric DuBois & Ashley Peper & Laura A. Albert, 2023. "Interdicting Attack Plans with Boundedly Rational Players and Multiple Attackers: An Adversarial Risk Analysis Approach," Decision Analysis, INFORMS, vol. 20(3), pages 202-219, September.
    15. Shengminjie Chen & Donglei Du & Wenguo Yang & Suixiang Gao, 2024. "Maximizing stochastic set function under a matroid constraint from decomposition," Journal of Combinatorial Optimization, Springer, vol. 48(1), pages 1-21, August.
    16. Zhenning Zhang & Bin Liu & Yishui Wang & Dachuan Xu & Dongmei Zhang, 2022. "Maximizing a monotone non-submodular function under a knapsack constraint," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1125-1148, July.
    17. Lee, Heesang & Nemhauser, George L. & Wang, Yinhua, 1996. "Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case," European Journal of Operational Research, Elsevier, vol. 94(1), pages 154-166, October.
    18. Zhenning Zhang & Donglei Du & Yanjun Jiang & Chenchen Wu, 2021. "Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint," Journal of Global Optimization, Springer, vol. 80(3), pages 595-616, July.
    19. 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.
    20. Yingfei Wang & Inbal Yahav & Balaji Padmanabhan, 2024. "Smart Testing with Vaccination: A Bandit Algorithm for Active Sampling for Managing COVID-19," Information Systems Research, INFORMS, vol. 35(1), pages 120-144, March.
    21. Chenggang Wang & Zengfu Wang & Xiong Xu & Yuhang Hao, 2021. "A balanced sensor scheduling for multitarget localization in a distributed multiple-input multiple-output radar network," International Journal of Distributed Sensor Networks, , vol. 17(7), pages 15501477211, July.

    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:spr:jcomop:v:40:y:2020:i:4:d:10.1007_s10878-020-00638-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.