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

Analytical solution to the k-core pruning process

Author

Listed:
  • Wu, Rui-Jie
  • Kong, Yi-Xiu
  • Di, Zengru
  • Zhang, Yi-Cheng
  • Shi, Gui-Yuan

Abstract

k-core decomposition is a widely-used method in ranking nodes or extracting important information of complex networks. It is a pruning process in which we recursively remove the vertices with degree less than k to obtain the core of a complex network. The simplicity and effectiveness of this approach has led to a variety of applications in many scientific fields, including bioinformatics, neurosciences, computer sciences, economics, and network sciences. However, the analytical theory of the k-core pruning process is still lacking. Here we find that in every pruning step of any given network, the Non-Backtracking Expansion Branch (NBEB) is directly related to the remaining k-core. Using this NBEB method, we obtain the analytical results of the k-core pruning process and its detailed critical behaviour.

Suggested Citation

  • Wu, Rui-Jie & Kong, Yi-Xiu & Di, Zengru & Zhang, Yi-Cheng & Shi, Gui-Yuan, 2022. "Analytical solution to the k-core pruning process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    • Handle: RePEc:eee:phsmap:v:608:y:2022:i:p1:s0378437122008184
    DOI: 10.1016/j.physa.2022.128260
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437122008184
    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.2022.128260?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. 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. Li, Pei & Liu, Ke & Li, Keqin & Liu, Jianxun & Zhou, Dong, 2021. "Estimating user influence ranking in independent cascade model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 565(C).
    3. Kazemzadeh, Farzaneh & Safaei, Ali Asghar & Mirzarezaee, Mitra, 2022. "Influence maximization in social networks using effective community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).
    4. Samir, Ahmed M. & Rady, Sherine & Gharib, Tarek F., 2021. "LKG: A fast scalable community-based approach for influence maximization problem in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 582(C).
    5. 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.
    6. Xie, Fengjie & Ma, Mengdi & Ren, Cuiping, 2022. "Research on multilayer network structure characteristics from a higher-order model: The case of a Chinese high-speed railway system," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 586(C).
    7. Shang, Yilun, 2021. "Generalized k-cores of networks under attack with limited knowledge," Chaos, Solitons & Fractals, Elsevier, vol. 152(C).
    8. Kumari, Suchi & Saroha, Abhishek & Singh, Anurag, 2020. "Efficient edge rewiring strategies for enhancement in network capacity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    9. Zhao, Zi-Juan & Guo, Qiang & Yu, Kai & Liu, Jian-Guo, 2020. "Identifying influential nodes for the networks with community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 551(C).
    10. Hou, Lei, 2022. "Network versus content: The effectiveness in identifying opinion leaders in an online social network with empirical evaluation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).
    11. Giulio Cimini & Tiziano Squartini & Diego Garlaschelli & Andrea Gabrielli, 2014. "Systemic risk analysis in reconstructed economic and financial networks," Papers 1411.7613, arXiv.org, revised May 2015.
    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. Li, Jin-Yue & Li, Xiang & Li, Cong, 2021. "The Kronecker-clique model for higher-order clustering coefficients," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 582(C).
    14. Gross, Bnaya & Bonamassa, Ivan & Havlin, Shlomo, 2021. "Interdependent transport via percolation backbones in spatial networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 567(C).
    15. Linyuan Lü & Tao Zhou & Qian-Ming Zhang & H. Eugene Stanley, 2016. "The H-index of a network node and its relation to degree and coreness," Nature Communications, Nature, vol. 7(1), pages 1-7, April.
    16. 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).
    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. 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).
    2. 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).
    3. Ye, Yucheng & Xu, Shuqi & Mariani, Manuel Sebastian & Lü, Linyuan, 2022. "Forecasting countries' gross domestic product from patent data," Chaos, Solitons & Fractals, Elsevier, vol. 160(C).
    4. 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).
    5. Qi, Mingze & Tan, Suoyi & Chen, Peng & Duan, Xiaojun & Lu, Xin, 2023. "Efficient network intervention with sampling information," Chaos, Solitons & Fractals, Elsevier, vol. 166(C).
    6. Han, Jihui & Zhang, Ge & Dong, Gaogao & Zhao, Longfeng & Shi, Yuefeng & Zou, Yijiang, 2024. "Exact analysis of generalized degree-based percolation without memory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 642(C).
    7. Wang, Yan & Li, Haozhan & Zhang, Ling & Zhao, Linlin & Li, Wanlan, 2022. "Identifying influential nodes in social networks: Centripetal centrality and seed exclusion approach," Chaos, Solitons & Fractals, Elsevier, vol. 162(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. 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).
    10. 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).
    11. Wandelt, Sebastian & Sun, Xiaoqian & Zhang, Anming, 2023. "Towards analyzing the robustness of the Integrated Global Transportation Network Abstraction (IGTNA)," Transportation Research Part A: Policy and Practice, Elsevier, vol. 178(C).
    12. 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).
    13. 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.
    14. 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.
    15. Xu, Shuqi & Mariani, Manuel Sebastian & Lü, Linyuan & Medo, Matúš, 2020. "Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data," Journal of Informetrics, Elsevier, vol. 14(1).
    16. 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).
    17. 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.
    18. Zhong, Lin-Feng & Shang, Ming-Sheng & Chen, Xiao-Long & Cai, Shi-Ming, 2018. "Identifying the influential nodes via eigen-centrality from the differences and similarities of structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 77-82.
    19. 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.
    20. Zhang, Dayong & Men, Hao & Zhang, Zhaoxin, 2024. "Assessing the stability of collaboration networks: A structural cohesion analysis perspective," Journal of Informetrics, Elsevier, vol. 18(1).

    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:608:y:2022:i:p1:s0378437122008184. 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.