OnionDecomposition

Onion decomposition is a graph-theoretic method for revealing the layered structure of a network by repeatedly removing vertices in order of their current degree. Each vertex is assigned an onion layer, or peel level, corresponding to the step at which it is removed. The approach provides a finer-grained alternative to the standard k-core decomposition, capturing a multi-layered perspective on how tightly a node is integrated into the network.

The typical procedure starts with the original graph and iteratively removes vertices of minimum remaining degree. In one common variant, all vertices with the current minimum degree are removed together in a single peeling round and labeled with the same layer index; the process then proceeds to the next distinct minimum degree, creating successive onion layers. Another variant removes one vertex at a time, updating degrees after each removal while recording the removal order and layer for each vertex. The resulting data assign to every vertex a layer value that reflects its position within the hierarchical peeling of the graph.

Interpretation and use of the onion decomposition emphasize how nodes differ in their embeddedness beyond a single core number. Layers typically correspond to a node’s resilience or centrality within the network and can help identify core-periphery structure, influential nodes, and mesoscale organization. The technique is related to, but more nuanced than, the k-core decomposition and can be computed efficiently with bucket-queue data structures in near-linear time.

Applications are common in network science, including social, biological, and information networks, where understanding layered participation and robustness is of interest.