IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v608y2022ip1s0378437122008184.html

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

    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. 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. 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).
    6. 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.
    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. 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).
    9. 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.
    10. 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).
    11. 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).
    12. Shang, Yilun, 2021. "Generalized k-cores of networks under attack with limited knowledge," Chaos, Solitons & Fractals, Elsevier, vol. 152(C).
    13. 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).
    14. 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).
    15. 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).
    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)

    Citations

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


    Cited by:

    1. Leyang Xue & Shengling Gao & Lazaros K. Gallos & Orr Levy & Bnaya Gross & Zengru Di & Shlomo Havlin, 2024. "Nucleation phenomena and extreme vulnerability of spatial k-core systems," Nature Communications, Nature, vol. 15(1), pages 1-10, December.
    2. Wu, Rui-Jie & Lin, Bin & Fang, Fanshu & Kong, Yi-Xiu & Shi, Gui-Yuan, 2026. "Predicting network topology from empirical evolution rules: A case study in email networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 688(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. Li, Shaobao & Quan, Yiran & Luo, Xiaoyuan & Wang, Juan & Tian, Changyong & Guan, Xinping, 2025. "Identifying influential nodes in complex networks via weighted k-shell entropy-based approach," Chaos, Solitons & Fractals, Elsevier, vol. 199(P3).
    2. 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).
    3. Zhu, Xiaoyu & Hao, Rongxia, 2024. "Identifying influential nodes in social networks via improved Laplacian centrality," Chaos, Solitons & Fractals, Elsevier, vol. 189(P1).
    4. Yu, Yong & Jing, Ming & Zhao, Na & Zhou, Tao, 2025. "Lowest degree decomposition of complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 199(P3).
    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. Zhu, Xiaoyu & Hao, Rongxia, 2025. "Finding influential nodes in complex networks by integrating nodal intrinsic and extrinsic centrality," Chaos, Solitons & Fractals, Elsevier, vol. 194(C).
    7. 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).
    8. 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).
    9. 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).
    10. Tang, Zemiao & Liu, Guolin & Tian, Delong & Zhang, Yu & Qi, Xingqin, 2026. "BGIC: A novel Bi-dimensional Gravitational Influence Centrality method for finding key nodes in signed hypergraphs," Chaos, Solitons & Fractals, Elsevier, vol. 202(P2).
    11. Anwesha Sengupta & Shashankaditya Upadhyay & Indranil Mukherjee & Prasanta K. Panigrahi, 2024. "A study of the effect of influential spreaders on the different sectors of Indian market and a few foreign markets: a complex networks perspective," Journal of Computational Social Science, Springer, vol. 7(1), pages 45-85, April.
    12. 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).
    13. Liu, Yan & Wang, Bin & Zhang, Simeng & Tian, Pengxu & Zhang, Hexin & Liu, Chenlu & Jiang, Xinyan, 2025. "Influential nodes identification based on Quasi-Laplacian Gravity Model," Chaos, Solitons & Fractals, Elsevier, vol. 200(P3).
    14. Ning, Xi & Zhang, Jie & Huang, Meigen & Wang, Tao & Zhang, Boquan & Ruan, Bangrong & Lei, Yonglin, 2026. "TripRank: A centrality metric based on dynamic competition of geometric–topological structures for influential nodes identification," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 688(C).
    15. 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).
    16. Zheng, Wenxin & Shi, Wenfeng & Fan, Tianlong & Lü, Linyuan, 2025. "Weighted cycle-based identification of influential node groups in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 677(C).
    17. Wang, Haiqing & Huang, He & Liu, Haiyan, 2026. "Competition or cooperation? Multiple information diffusion against epidemic spreading in a multiplex network," Chaos, Solitons & Fractals, Elsevier, vol. 203(C).
    18. Liu, Jin & Yu, Wenbin & Zhang, ChengJun & Gu, JiaRui & Yu, Louyang & Zhong, Guancheng, 2025. "Identifying active spreading nodes in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 669(C).
    19. Wang, Xiaojie & Zhang, Xue & Zhao, Chengli & Yi, Dongyun, 2018. "Effectively identifying multiple influential spreaders in term of the backward–forward propagation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 404-413.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.