IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v513y2019icp477-496.html
   My bibliography  Save this article

Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization

Author

Listed:
  • Tang, Jianxin
  • Zhang, Ruisheng
  • Yao, Yabing
  • Yang, Fan
  • Zhao, Zhili
  • Hu, Rongjing
  • Yuan, Yongna

Abstract

Influence maximization aims to select a subset of top-k influential nodes to maximize the influence propagation, and it remains an open research topic of viral marketing and social network analysis. Submodularity-based methods including greedy algorithm can provide solutions with performance guarantee, but the time complexity is unbearable especially in large-scale networks. Meanwhile, conventional centrality-based measures cannot provide steady performance for multiple influential nodes identification. In this paper, we propose an improved discrete particle swarm optimization with an enhanced network topology-based strategy for influence maximization. According to the strategy, the k influential nodes in a temporary optimal seed set are recombined firstly in ascending order by degree metric to let the nodes with lower degree centrality exploit more influential neighbors preferentially. Secondly, a local greedy strategy is applied to replace the current node with the most influential node from the direct neighbor set of each node from the temporary seed set. The experimental results conducted in six social networks under independent cascade model show that the proposed algorithm outperforms typical centrality-based heuristics, and achieves comparable results to greedy algorithm but with less time complexity.

Suggested Citation

  • Tang, Jianxin & Zhang, Ruisheng & Yao, Yabing & Yang, Fan & Zhao, Zhili & Hu, Rongjing & Yuan, Yongna, 2019. "Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 477-496.
    • Handle: RePEc:eee:phsmap:v:513:y:2019:i:c:p:477-496
    DOI: 10.1016/j.physa.2018.09.040
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437118311774
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2018.09.040?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. Bao, Zhong-Kui & Ma, Chuang & Xiang, Bing-Bing & Zhang, Hai-Feng, 2017. "Identification of influential nodes in complex networks: Method from spreading probability viewpoint," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 468(C), pages 391-397.
    2. Heidari, Mehdi & Asadpour, Masoud & Faili, Hesham, 2015. "SMG: Fast scalable greedy algorithm for influence maximization in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 420(C), pages 124-133.
    3. Liu, Ruochen & Li, Jianxia & fan, Jing & Mu, Caihong & Jiao, Licheng, 2017. "A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1028-1051.
    4. Fei, Liguo & Zhang, Qi & Deng, Yong, 2018. "Identifying influential nodes in complex networks based on the inverse-square law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 1044-1059.
    5. Cho, Youngsang & Hwang, Junseok & Lee, Daeho, 2012. "Identification of effective opinion leaders in the diffusion of technological innovation: A social network approach," Technological Forecasting and Social Change, Elsevier, vol. 79(1), pages 97-106.
    6. C Prem Sankar & Asharaf S. & K Satheesh Kumar, 2016. "Learning from Bees: An Approach for Influence Maximization on Viral Campaigns," PLOS ONE, Public Library of Science, vol. 11(12), pages 1-15, December.
    7. Wang, Qiyao & Jin, Yuehui & Cheng, Shiduan & Yang, Tan, 2017. "ConformRank: A conformity-based rank for finding top-k influential users," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 474(C), pages 39-48.
    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. Jiang, Jianhua & Yang, Xi & Meng, Xianqiu & Li, Keqin, 2020. "Enhance chaotic gravitational search algorithm (CGSA) by balance adjustment mechanism and sine randomness function for continuous optimization problems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 537(C).
    2. Abbas Salehi & Behrooz Masoumi, 2020. "KATZ centrality with biogeography-based optimization for influence maximization problem," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 205-226, July.
    3. Jiang, Jianhua & Xu, Meirong & Meng, Xianqiu & Li, Keqin, 2020. "STSA: A sine Tree-Seed Algorithm for complex continuous optimization problems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 537(C).

    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. Sheng, Jinfang & Dai, Jinying & Wang, Bin & Duan, Guihua & Long, Jun & Zhang, Junkai & Guan, Kerong & Hu, Sheng & Chen, Long & Guan, Wanghao, 2020. "Identifying influential nodes in complex networks based on global and local structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 541(C).
    2. Wang, Xiaojie & Slamu, Wushour & Guo, Wenqiang & Wang, Sixiu & Ren, Yan, 2022. "A novel semi local measure of identifying influential nodes in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    3. 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.
    4. Chaharborj, Sarkhosh Seddighi & Nabi, Khondoker Nazmoon & Feng, Koo Lee & Chaharborj, Shahriar Seddighi & Phang, Pei See, 2022. "Controlling COVID-19 transmission with isolation of influential nodes," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    5. Duan, Shuyu & Wen, Tao & Jiang, Wen, 2019. "A new information dimension of complex network based on Rényi entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 529-542.
    6. Gagliardi, Dimitri & Ramlogan, Ronnie & Navarra, Pierluigi & Dello Russo, Cinzia, 2018. "Diffusion of complementary evolving pharmaceutical innovations: The case of Abacavir and its pharmacogenetic companion diagnostic in Italy," Technological Forecasting and Social Change, Elsevier, vol. 134(C), pages 223-233.
    7. Xiaodong Liu & Xiangke Liao & Shanshan Li & Si Zheng & Bin Lin & Jingying Zhang & Lisong Shao & Chenlin Huang & Liquan Xiao, 2017. "On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks," Complexity, Hindawi, vol. 2017, pages 1-14, September.
    8. Nasirian, Farzaneh & Mahdavi Pajouh, Foad & Balasundaram, Balabhaskar, 2020. "Detecting a most closeness-central clique in complex networks," European Journal of Operational Research, Elsevier, vol. 283(2), pages 461-475.
    9. Fatima Canseco-Lopez & Francesc Miralles, 2023. "Adoption of Plant-Based Diets: A Process Perspective on Adopters’ Cognitive Propensity," Sustainability, MDPI, vol. 15(9), pages 1-29, May.
    10. Wang, Qiyao & Jin, Yuehui & Lin, Zhen & Cheng, Shiduan & Yang, Tan, 2016. "Influence maximization in social networks under an independent cascade-based model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 20-34.
    11. De Xia & Nian Xia & Yishi Zhang & Jiwei Xiong & Ruilin Zhu, 2022. "Diffusion Path Identification of Public Opinion Involving Enterprise Green Technology Adoption: An Interpretive-Structural-Modeling-Based Approach," IJERPH, MDPI, vol. 19(5), pages 1-15, February.
    12. Teng Yu & Ai Ping Teoh & Chengliang Wang & Qing Bian, 2024. "Convenient or risky? Investigating the behavioral intention to use facial recognition payment in smart hospitals," Palgrave Communications, Palgrave Macmillan, vol. 11(1), pages 1-20, December.
    13. Charikhi, Mourad, 2024. "Association of the PageRank algorithm with similarity-based methods for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 637(C).
    14. Li, Meizhu & Zhang, Qi & Deng, Yong, 2018. "Evidential identification of influential nodes in network of networks," Chaos, Solitons & Fractals, Elsevier, vol. 117(C), pages 283-296.
    15. Jiang, Cheng & Liu, Zhonghua, 2019. "Detecting multiple key players under the positive effect by using a distance-based connectivity approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    16. Xu, Guiqiong & Meng, Lei, 2023. "A novel algorithm for identifying influential nodes in complex networks based on local propagation probability model," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).
    17. Abdullah Almaatouq, 2016. "Complex Systems and a Computational Social Science Perspective on the Labor Market," Papers 1606.08562, arXiv.org.
    18. Xu, Paiheng & Zhang, Rong & Deng, Yong, 2018. "A novel visibility graph transformation of time series into weighted networks," Chaos, Solitons & Fractals, Elsevier, vol. 117(C), pages 201-208.
    19. Sun, Hong-liang & Chen, Duan-bing & He, Jia-lin & Ch’ng, Eugene, 2019. "A voting approach to uncover multiple influential spreaders on weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 519(C), pages 303-312.
    20. Wen, Tao & Jiang, Wen, 2019. "Identifying influential nodes based on fuzzy local dimension in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 119(C), pages 332-342.

    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:phsmap:v:513:y:2019:i:c:p:477-496. 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.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.