IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i9p1449-d405791.html
   My bibliography  Save this article

MINE: Identifying Top- k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion

Author

Listed:
  • Xinyu Huang

    (Software College, Northeastern University, Shenyang 110169, China)

  • Dongming Chen

    (Software College, Northeastern University, Shenyang 110169, China)

  • Dongqi Wang

    (Software College, Northeastern University, Shenyang 110169, China)

  • Tao Ren

    (Software College, Northeastern University, Shenyang 110169, China)

Abstract

Identifying vital nodes in complex networks is of paramount importance in understanding and controlling the spreading dynamics. Currently, this study is facing great challenges in dealing with big data in many real-life applications. With the deepening of the research, scholars began to realize that the analysis on traditional graph model is insufficient because many nodes in a multilayer network share connections among different layers. To address this problem both efficiently and effectively, a novel algorithm for identifying vital nodes in both monolayer and multilayer networks is proposed in this paper. Firstly, a node influence measure is employed to determine the initial leader of a local community. Subsequently, the community structures are revealed via the Maximum Influential Neighbors Expansion (MINE) strategy. Afterward, the communities are regarded as super-nodes for an iteratively folding process till convergence, in order to identify influencers hierarchically. Numerical experiments on 32 real-world datasets are conducted to verify the performance of the proposed algorithm, which shows superiority to the competitors. Furthermore, we apply the proposed algorithm in the graph of adjacencies derived from the maps of China and USA. The comparison and analysis of the identified provinces (or states) suggest that the proposed algorithm is feasible and reasonable on real-life applications.

Suggested Citation

  • Xinyu Huang & Dongming Chen & Dongqi Wang & Tao Ren, 2020. "MINE: Identifying Top- k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion," Mathematics, MDPI, vol. 8(9), pages 1-25, August.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:9:p:1449-:d:405791
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/9/1449/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/9/1449/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Georgios Fragkos & Pavlos Athanasios Apostolopoulos & Eirini Eleni Tsiropoulou, 2019. "ESCAPE: Evacuation Strategy through Clustering and Autonomous Operation in Public Safety Systems," Future Internet, MDPI, vol. 11(1), pages 1-17, January.
    2. Pablo M. Gleiser & Leon Danon, 2003. "Community Structure In Jazz," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 6(04), pages 565-573.
    3. Hu, Ping & Fan, Wen-Li, 2020. "Mitigation strategy against cascading failures considering vulnerable transmission line in power grid," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    4. Weiyi Liu & Toyotaro Suzumura & Hongyu Ji & Guangmin Hu, 2018. "Finding overlapping communities in multilayer networks," PLOS ONE, Public Library of Science, vol. 13(4), pages 1-22, April.
    5. H. W. Corley, Jr. & Han Chang, 1974. "Finding the n Most Vital Nodes in a Flow Network," Management Science, INFORMS, vol. 21(3), pages 362-364, November.
    6. 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.
    7. Ma, Ling-ling & Ma, Chuang & Zhang, Hai-Feng & Wang, Bing-Hong, 2016. "Identifying influential spreaders in complex networks based on gravity formula," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 451(C), pages 205-212.
    8. Duncan J. Watts & Steven H. Strogatz, 1998. "Collective dynamics of ‘small-world’ networks," Nature, Nature, vol. 393(6684), pages 440-442, June.
    9. Yuanzhi Yang & Lei Yu & Xing Wang & Siyi Chen & You Chen & Yipeng Zhou, 2020. "A novel method to identify influential nodes in complex networks," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 31(02), pages 1-14, February.
    10. Flaviano Morone & Hernán A. Makse, 2015. "Correction: Corrigendum: Influence maximization in complex networks through optimal percolation," Nature, Nature, vol. 527(7579), pages 544-544, November.
    11. Nikolaou, Paraskevas & Dimitriou, Loukas, 2020. "Identification of critical airports for controlling global infectious disease outbreaks: Stress-tests focusing in Europe," Journal of Air Transport Management, Elsevier, vol. 85(C).
    12. Flaviano Morone & Hernán A. Makse, 2015. "Influence maximization in complex networks through optimal percolation," Nature, Nature, vol. 524(7563), pages 65-68, August.
    13. Salavati, Chiman & Abdollahpouri, Alireza & Manbari, Zhaleh, 2018. "BridgeRank: A novel fast centrality measure based on local structure of the network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 635-653.
    14. Shashank Sheshar Singh & Ajay Kumar & Shivansh Mishra & Kuldeep Singh & Bhaskar Biswas, 2019. "Influence Maximization in Social Networks," Springer Optimization and Its Applications, in: Mahdi Fathi & Marzieh Khakifirooz & Panos M. Pardalos (ed.), Optimization in Large Scale Problems, pages 255-267, Springer.
    15. Manlio De Domenico & Vincenzo Nicosia & Alexandre Arenas & Vito Latora, 2015. "Structural reducibility of multilayer networks," Nature Communications, Nature, vol. 6(1), pages 1-9, November.
    16. Singh, Shashank Sheshar & Singh, Kuldeep & Kumar, Ajay & Biswas, Bhaskar, 2019. "MIM2: Multiple influence maximization across multiple social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 526(C).
    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. Liu, Panfeng & Li, Longjie & Fang, Shiyu & Yao, Yukai, 2021. "Identifying influential nodes in social networks: A voting approach," Chaos, Solitons & Fractals, Elsevier, vol. 152(C).
    2. Namtirtha, Amrita & Dutta, Animesh & Dutta, Biswanath, 2018. "Identifying influential spreaders in complex networks based on kshell hybrid method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 499(C), pages 310-324.
    3. Mishra, Shivansh & Singh, Shashank Sheshar & Kumar, Ajay & Biswas, Bhaskar, 2022. "ELP: Link prediction in social networks based on ego network perspective," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    4. Sun, Peng Gang & Che, Wanping & Quan, Yining & Wang, Shuzhen & Miao, Qiguang, 2022. "Random networks are heterogeneous exhibiting a multi-scaling law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 587(C).
    5. Kumar, Ajay & Singh, Shashank Sheshar & Singh, Kuldeep & Biswas, Bhaskar, 2020. "Link prediction techniques, applications, and performance: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    6. Alexandru Topîrceanu, 2022. "Benchmarking Cost-Effective Opinion Injection Strategies in Complex Networks," Mathematics, MDPI, vol. 10(12), pages 1-16, June.
    7. Wang, Min & Li, Wanchun & Guo, Yuning & Peng, Xiaoyan & Li, Yingxiang, 2020. "Identifying influential spreaders in complex networks based on improved k-shell method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 554(C).
    8. Fink, Christian G. & Fullin, Kelly & Gutierrez, Guillermo & Omodt, Nathan & Zinnecker, Sydney & Sprint, Gina & McCulloch, Sean, 2023. "A centrality measure for quantifying spread on weighted, directed networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    9. Fan, Dongming & Sun, Bo & Dui, Hongyan & Zhong, Jilong & Wang, Ziyao & Ren, Yi & Wang, Zili, 2022. "A modified connectivity link addition strategy to improve the resilience of multiplex networks against attacks," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    10. Wang, Jingjing & Xu, Shuqi & Mariani, Manuel S. & Lü, Linyuan, 2021. "The local structure of citation networks uncovers expert-selected milestone papers," Journal of Informetrics, Elsevier, vol. 15(4).
    11. Gangwal, Utkarsh & Singh, Mayank & Pandey, Pradumn Kumar & Kamboj, Deepak & Chatterjee, Samrat & Bhatia, Udit, 2022. "Identifying early-warning indicators of onset of sudden collapse in networked infrastructure systems against sequential disruptions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    12. Li, Hanwen & Shang, Qiuyan & Deng, Yong, 2021. "A generalized gravity model for influential spreaders identification in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 143(C).
    13. Wang, Zhixiao & Zhao, Ya & Xi, Jingke & Du, Changjiang, 2016. "Fast ranking influential nodes in complex networks using a k-shell iteration factor," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 171-181.
    14. Alexander Tselykh & Vladislav Vasilev & Larisa Tselykh & Fernando A. F. Ferreira, 2022. "Influence control method on directed weighted signed graphs with deterministic causality," Annals of Operations Research, Springer, vol. 311(2), pages 1281-1305, April.
    15. Zareie, Ahmad & Sheikhahmadi, Amir, 2019. "EHC: Extended H-index Centrality measure for identification of users’ spreading influence in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 141-155.
    16. Natarajan Meghanathan, 2019. "Unit Disk Graph-Based Node Similarity Index for Complex Network Analysis," Complexity, Hindawi, vol. 2019, pages 1-22, March.
    17. Yin, Haofei & Zhang, Aobo & Zeng, An, 2023. "Identifying hidden target nodes for spreading in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).
    18. Qi, Mingze & Tan, Suoyi & Chen, Peng & Duan, Xiaojun & Lu, Xin, 2023. "Efficient network intervention with sampling information," Chaos, Solitons & Fractals, Elsevier, vol. 166(C).
    19. Li, Sheng & Liu, Wenwen & Wu, Ruizi & Li, Junli, 2023. "An adaptive attack model to network controllability," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    20. James Flamino & Alessandro Galeazzi & Stuart Feldman & Michael W. Macy & Brendan Cross & Zhenkun Zhou & Matteo Serafino & Alexandre Bovet & Hernán A. Makse & Boleslaw K. Szymanski, 2023. "Political polarization of news media and influencers on Twitter in the 2016 and 2020 US presidential elections," Nature Human Behaviour, Nature, vol. 7(6), pages 904-916, June.

    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:gam:jmathe:v:8:y:2020:i:9:p:1449-:d:405791. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.