The Core That Springs From Nothing

Two ways to strip a network

The previous drop but one watched a scatter of dots knit itself into a single connected web the instant the lines reached an average of one per dot. That was the giant component, and its arrival is a phase transition: below one connection each you have a litter of tiny pieces, above it a structure the size of the whole thing. But the giant grows up gently. Right at the threshold it is vanishingly small, and it swells smoothly as you add more edges. Nothing lurches.

There is a second, stranger threshold hiding in the same random graph, and finding it takes a different question. Instead of asking what is connected to what, ask who is well-connected enough to stay. Pick a number k and start deleting: remove every node with fewer than k neighbours. That is a natural thing to want, a node with only one or two links is a loose end, not really part of the dense heart of the network. But deleting a node lowers the degree of each of its neighbours, so some of them now fall below k and must go too, and the deletions cascade. When the dust settles, what is left is a subgraph in which every remaining node still has at least k neighbours among the other survivors. That is the k-core, named by Béla Bollobás in 1984, and it is unique: peel in any order you like and you land on the same core.

The 1-core is just "throw away the totally isolated dots." The 2-core is the network with all its dangling tendrils trimmed off, every dead-end chain pruned back until only loops and their connective tissue remain. And the 3-core, the 4-core, and beyond ask for something genuinely robust: a neighbourhood where everyone has real support. The surprise of this drop is that the moment you ask for k = 3 or more, the way the core appears changes completely.

Peel it yourself

Module 01 is the peeling, live, on one fixed graph of 140 nodes. Choose k, set the average number of links per node, and then strip the graph a round at a time. Each round removes, all at once, every node currently holding fewer than k links; the survivors of the whole cascade light up in ice.

At k = 2 the core is forgiving and shows up early. The interesting thing is what happens when you demand k = 3 and slide the average degree down toward three. At an average of four connections each, a solid three-core survives, most of the graph, every node in it braced by at least three others. Drop the dial to three and something abrupt happens: the peeling that used to halt partway now never halts. One round exposes a few under-connected nodes, deleting them drops their neighbours below three, that exposes more, and the cascade runs all the way to the bottom. The core is not small. It is empty. Nudge the dial back up a touch and a large core snaps back into existence, intact. There is no setting that gives you a little three-core. It is all, or it is nothing.

That is the whole phenomenon in one board. Now the honest way to see it sharply is, as ever, to stop looking at one small graph and average over many.

The double jump

Module 02 builds a fresh random graph for each average degree, peels it to its k-core, and plots the surviving fraction, averaged over thousands of graphs, against the average degree. The reference curve is the 2-core, and it behaves exactly like the giant component: it lifts off the floor at an average of one connection each and rises smoothly. That is no coincidence. The 2-core is the giant component with its dangling ends trimmed, so it is born at the very same threshold and grows up the same continuous way.

Switch to k = 3 and the curve changes its character entirely. It does not lift off gently anywhere. It clings to exactly zero, not merely small but flat on the floor, all the way out to an average degree of about 3.35, and then it jumps, straight up to more than a third of the whole graph, in a single step. Watch what happens as the graph grows from 250 nodes to 2,000 to 12,000: at the small size the jump is a rounded shoulder, blurred by luck, but as the graph grows it tightens into a genuine vertical cliff. This is a discontinuity, a jump from nothing to a finite fraction with no values in between, the fingerprint of what physicists call a first-order transition. The 4-core does the same thing, later and higher, leaping into being near an average degree of 5.15.

So a random graph has not one phase transition but a whole staircase of them. The giant appears at one connection each, continuously. Then, as you keep adding edges, the 3-core springs in at 3.35, the 4-core at 5.15, the 5-core at 6.80, each one arriving all at once. This stacking of a discontinuous transition on top of the continuous giant-component one is the double jump. And it raises the obvious question: why does asking for one extra neighbour turn a gentle lift-off into a leap?

Why it jumps

The answer is the prettiest kind, a single self-consistency picture, and it is the exact mirror of the one that explained the giant component.

Track one quantity: μ, the average number of a node's edges that reach into the surviving core. Now follow one such edge. Its far endpoint stays in the core only if that endpoint is itself well-supported, meaning it has at least k − 1 other edges holding it in (the one you arrived along does not count). The number of a node's edges is Poisson with mean c, so the chance an endpoint has k − 1 other supporting links is P(Po(μ) ≥ k − 1), and self-consistency demands

μ = c · P(Po(μ) ≥ k − 1),

with the core fraction then equal to P(Po(μ) ≥ k). Module 03 draws it: the curve y = c · P(Po(μ) ≥ k − 1) against the line y = μ, their crossings being the solutions.

For k = 2 the curve is c·(1 − e^(−μ)), which leaves the origin with slope c, tangent to the line right at zero. That is precisely the giant-component story: the moment c passes one, the crossing peels away from the origin and grows smoothly. Continuous.

For k ≥ 3 the curve is flat at the origin. It has to be: having two or more other links is a second-order event, so near μ = 0 the curve rises like μ^(k−1), far slower than the line. Down near zero the line always wins, so the only solution is the empty core, and it stays the only solution no matter how you nudge c upward, at first. Keep raising c and the curve bulges up until, at one critical value, it rises just enough to kiss the line tangentially at a point μ* well away from zero. At that instant a crossing materializes out of nowhere, and it is already at a finite μ*. Push c a hair further and that single tangent point splits into two crossings. The core cannot be born small for the simplest possible reason: there is no small solution for it to be born into. The fixed point is finite the moment it exists at all.

That single geometric difference, a curve tangent at the origin versus a curve tangent away from it, is the whole distinction between a phase transition that ramps and one that jumps. The table in module 03 collects where each core arrives and how big it is at birth: the 2-core at one connection each, born from nothing; the 3-core at 3.35, born holding 27%; the 4-core at 5.15, born at 44%; the 5-core at 6.80, born at 54%. The deeper into the network you demand robustness, the longer the core makes you wait, and the more of the graph it seizes the instant it finally comes.

Why anyone counts cores

The k-core is not a curiosity of random graphs; it is one of the standard ways to find the dense heart of any real network. Peeling by degree is exactly how you locate the influential middle of a social network (the users everyone keeps connecting back to, not the leaf accounts with one follower), how you rank the robust backbone of a protein interaction map, and how a graph's coreness becomes a measure of how central each node is. The double jump is the warning that comes attached: robustness in a network is not something that fades in gradually as connections accumulate. A collaboration network, an infrastructure grid, a mesh of trust can sit below the critical density with no well-connected core at all, and then a modest increase in average connectivity brings a large, mutually-reinforcing core into existence all at once. Removing links runs the film backwards, and the same discontinuity means a core that looks solid can collapse to nothing from a small loss, the mechanism behind cascading failures and bootstrap percolation.

The thresholds were pinned down precisely by Boris Pittel, Joel Spencer and Nicholas Wormald in 1996, and everything above ran in your browser to check them: a random-number generator, a graph knit from its output, and a peel that deletes the under-connected until the cascade stops. Nothing was fetched. The number 3.35 was not looked up. It was measured, live, as the exact place a curve stops touching a line only at the origin and starts touching it somewhere out in the open.