A fast algorithm for estimating the maximum k-core number in random graphs with given expected degree sequences

Yang-Ming Hu, Gui-Yuan Shi, Huimin Bai, Yi-Xiu Kong, Zhang Yicheng and Rui-Jie Wu

Chaos, Solitons & Fractals, 2026, vol. 208, issue P2

Abstract: The maximum k-core number of a network, defined as the largest value of k for which a k-core exists, serves as a key metric for identifying core structures and assessing network resilience. Conventional approaches to establishing its relationship with degree distribution rely on computationally intensive processes involving graph generation and subsequent decomposition. To address this limitation, we introduce a fast algorithm that directly estimates the maximum k-core number solely from a given degree sequence, entirely bypassing the need for explicit network instantiation. Extensive validation on both model networks and degree sequences extracted from real-world networks demonstrates that our method achieves accurate estimates within milliseconds, offering a powerful and efficient tool for large-scale network analysis.

Keywords: k-core; Coreness; Fast algorithm; Degree sequence; Complex networks; Random network (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077926003449
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:208:y:2026:i:p2:s0960077926003449

DOI: 10.1016/j.chaos.2026.118203

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().