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

Leveraging Minimum Nodes for Optimum Key Player Identification in Complex Networks: A Deep Reinforcement Learning Strategy with Structured Reward Shaping

Author

Listed:
  • Li Zeng

    (School of International Business and Management, Sichuan International Studies University, Chongqing 400031, China)

  • Changjun Fan

    (College of Systems Engineering, National University of Defense Technology, Changsha 410073, China)

  • Chao Chen

    (College of Systems Engineering, National University of Defense Technology, Changsha 410073, China)

Abstract

The problem of finding key players in a graph, also known as network dismantling, or network disintegration, aims to find an optimal removal sequence of nodes (edges, substructures) through a certain algorithm, ultimately causing functional indicators such as the largest connected component (GCC) or network pair connectivity in the graph to rapidly decline. As a typical NP-hard problem on graphs, recent methods based on reinforcement learning and graph representation learning have effectively solved such problems. However, existing reinforcement-learning-based key-player-identification algorithms often need to remove too many nodes in order to achieve the optimal effect when removing the remaining network until no connected edges remain. The use of a minimum number of nodes while maintaining or surpassing the performance of existing methods is a worthwhile research problem. To this end, a novel algorithm called MiniKey was proposed to tackle such challenges, which employs a specific deep Q-network architecture for reinforcement learning, a novel reward-shaping mechanism based on network functional indicators, and the graph-embedding technique GraphSage to transform network nodes into latent representations. Additionally, a technique dubbed ‘virtual node technology’ is integrated to grasp the overarching feature representation of the whole network. This innovative algorithm can be effectively trained on small-scale simulated graphs while also being scalable to large-scale real-world networks. Importantly, experiments from both six simulated datasets and six real-world datasets demonstrates that MiniKey can achieve optimal performance, striking a perfect balance between the effectiveness of key node identification and the minimization of the number of nodes that is utilized, which holds potential for real-world applications such as curbing misinformation spread in social networks, optimizing traffic in transportation systems, and identifying key targets in biological networks for targeted interventions.

Suggested Citation

  • Li Zeng & Changjun Fan & Chao Chen, 2023. "Leveraging Minimum Nodes for Optimum Key Player Identification in Complex Networks: A Deep Reinforcement Learning Strategy with Structured Reward Shaping," Mathematics, MDPI, vol. 11(17), pages 1-13, August.
  • Handle: RePEc:gam:jmathe:v:11:y:2023:i:17:p:3690-:d:1226674
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/17/3690/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/11/17/3690/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Hai-Jun Zhou, 2013. "Spin glass approach to the feedback vertex set problem," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 86(11), pages 1-9, November.
    2. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    3. David Bright & Catherine Greenhill & Thomas Britz & Alison Ritter & Carlo Morselli, 2017. "Criminal network vulnerabilities and adaptations," Global Crime, Taylor & Francis Journals, vol. 18(4), pages 424-441, October.
    4. 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.
    5. Hsinchun Chen, 2005. "Introduction to the special topic issue: Intelligence and security informatics," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 56(3), pages 217-220, February.
    6. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    7. Flaviano Morone & Hernán A. Makse, 2015. "Influence maximization in complex networks through optimal percolation," Nature, Nature, vol. 524(7563), pages 65-68, August.
    8. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    9. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    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. Tianle Pu & Li Zeng & Chao Chen, 2024. "Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach," Mathematics, MDPI, vol. 12(8), pages 1-12, April.

    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. Wandelt, Sebastian & Lin, Wei & Sun, Xiaoqian & Zanin, Massimiliano, 2022. "From random failures to targeted attacks in network dismantling," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    2. Annamaria Ficara & Francesco Curreri & Giacomo Fiumara & Pasquale De Meo & Antonio Liotta, 2022. "Covert Network Construction, Disruption, and Resilience: A Survey," Mathematics, MDPI, vol. 10(16), pages 1-43, August.
    3. 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).
    4. Xiao-Long Ren & Niels Gleinig & Dijana Tolić & Nino Antulov-Fantulin, 2018. "Underestimated Cost of Targeted Attacks on Complex Networks," Complexity, Hindawi, vol. 2018, pages 1-15, January.
    5. Tianle Pu & Li Zeng & Chao Chen, 2024. "Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach," Mathematics, MDPI, vol. 12(8), pages 1-12, April.
    6. 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).
    7. Yibo Dong & Jin Liu & Jiaqi Ren & Zhe Li & Weili Li, 2023. "Protecting Infrastructure Networks: Solving the Stackelberg Game with Interval-Valued Intuitionistic Fuzzy Number Payoffs," Mathematics, MDPI, vol. 11(24), pages 1-18, December.
    8. Alexandru Topîrceanu, 2022. "Benchmarking Cost-Effective Opinion Injection Strategies in Complex Networks," Mathematics, MDPI, vol. 10(12), pages 1-16, June.
    9. Kovalenko, K. & Romance, M. & Vasilyeva, E. & Aleja, D. & Criado, R. & Musatov, D. & Raigorodskii, A.M. & Flores, J. & Samoylenko, I. & Alfaro-Bittner, K. & Perc, M. & Boccaletti, S., 2022. "Vector centrality in hypergraphs," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    10. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    11. 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.
    12. 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).
    13. Wu, Tao & Xian, Xingping & Zhong, Linfeng & Xiong, Xi & Stanley, H. Eugene, 2018. "Power iteration ranking via hybrid diffusion for vital nodes identification," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 802-815.
    14. 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).
    15. Ho-Chun Herbert Chang & Brooke Harrington & Feng Fu & Daniel Rockmore, 2023. "Complex Systems of Secrecy: The Offshore Networks of Oligarchs," Papers 2303.03371, arXiv.org.
    16. Xia, Ling-Ling & Song, Yu-Rong & Li, Chan-Chan & Jiang, Guo-Ping, 2018. "Improved targeted immunization strategies based on two rounds of selection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 540-547.
    17. 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).
    18. 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.
    19. Michael Fritsch & Moritz Zoellner, 2020. "The fluidity of inventor networks," The Journal of Technology Transfer, Springer, vol. 45(4), pages 1063-1087, August.
    20. Yin, Haofei & Zhang, Aobo & Zeng, An, 2023. "Identifying hidden target nodes for spreading in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).

    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:11:y:2023:i:17:p:3690-:d:1226674. 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.