Answers are grounded in this paper and cite their sources.
This randomized trial demonstrates improved efficiency in hierarchy construction and nucleus decomposition in graphs using a novel counting method.
Nucleus decomposition provides a unified framework for discovering hierarchically cohesive substructures in graphs by generalizing the notions of k -core and k -truss to higher-order ( r,s )-nucleus. Existing algorithms suffer from a fundamental bottleneck: they rely on explicit enumeration of all s -cliques, whose number grows combinatorially with s . In this paper, we revisit the existing nucleus decomposition framework and present the first counting-based approach that eliminates explicit s -clique enumeration. We propose the Clique Path Index, a compact auxiliary structure that encodes the s -clique search space as concise paths, enabling direct computation, efficient dynamic updates, and connectivity maintenance during nucleus decomposition. Extensive experiments on real-world datasets demonstrate that our approach achieves an average speedup of one order of magnitude and up to two orders of magnitude for both nucleus decomposition and hierarchy construction. More importantly, while existing algorithms often time out even for small values of s , our method scales efficiently to larger s and denser graphs.
No takes yet. Share an insight, caveat, or question.
Zhang et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: