k-Core Decomposition
k-Core Decomposition of Networks · Also known as: Core Decomposition, Coreness Decomposition, Shell Decomposition, Çekirdek Ayrıştırma
k-Core Decomposition is a graph-theoretic method that partitions the vertices of a network into a nested sequence of subgraphs called k-cores. A k-core is the maximal subgraph in which every vertex has at least k neighbors within that subgraph. Introduced by Stephen B. Seidman in 1983, the method assigns each vertex a coreness number that captures its structural centrality relative to the local connectivity of the graph.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use k-core decomposition when you need to identify hierarchical cohesive subgroups, locate the dense influential core of a network, or rank nodes by structural embeddedness rather than by simple degree. It is well-suited to large sparse networks where clique-based cohesion measures are computationally prohibitive. The method assumes an undirected or symmetrized graph; directed and weighted extensions exist but require additional conventions. It does not detect overlapping communities and is sensitive to network density variations across subgraphs.
Strengths & limitations
- Linear time complexity O(m) on sparse graphs makes it scalable to networks with millions of edges.
- Produces an intuitive nested hierarchy of cohesive subgraphs without tuning parameters.
- Coreness values correlate with spreading influence and epidemic centrality in diffusion models.
- The decomposition is unique and deterministic for any given graph, ensuring reproducibility.
- Does not detect overlapping communities; each vertex belongs to exactly one shell.
- Ignores edge weights and directionality unless the method is explicitly extended for weighted or directed graphs.
- Coreness can be identical for many structurally diverse vertices, reducing discriminative power in homogeneous networks.
- The outermost core may collapse to a single clique in dense graphs, limiting interpretive richness.
Frequently asked
How does coreness differ from degree centrality?
Degree centrality counts only a vertex's direct neighbors without regard to how those neighbors are connected among themselves. Coreness, by contrast, measures structural depth: a vertex can have high degree but low coreness if its neighbors are all peripheral. Coreness therefore captures local density and cohesion beyond what a single-step neighbor count can reveal.
Can k-core decomposition be applied to weighted graphs?
The classical algorithm works on unweighted graphs. For weighted graphs, researchers have proposed weighted coreness measures that replace the degree condition with a weighted degree or strength threshold. However, these extensions require careful threshold selection and are not universally standardized, so results should be interpreted with reference to the specific variant used.
Is the k-core the same as the densest subgraph?
Not necessarily. The innermost k-core — the core with the highest k value — is often close to the densest subgraph, and in some graph families the two coincide. However, the densest subgraph maximizes average degree over all possible subsets, which is a different optimization criterion. The k-core with maximum k is a good approximation but not an exact solution to the densest subgraph problem in general.
Sources
- Seidman, S. B. (1983). Network structure and minimum degree. Social Networks, 5(3), 269–287. DOI: 10.1016/0378-8733(83)90028-X ↗
How to cite this page
ScholarGate. (2026, June 2). k-Core Decomposition of Networks. ScholarGate. https://scholargate.app/en/network-analysis/k-core-decomposition
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Centrality AnalysisNetwork analysis↔ compare
- Community DetectionNetwork analysis↔ compare
- PageRankNetwork analysis↔ compare