The onion decomposition (OD) extends the k -core decomposition by assigning to each node not only a core index but also a layer index that records the iteration at which the node is removed during the peeling process [2]. The OD is obtained through the following steps:

  1. Initialize the core index \(k = 1\) and the layer index \(\ell = 1\). Compute the degree \(d_i\) of each node \(i\) in the network \(G\).
  2. Identify all nodes with degree \(d_i \le k\). Assign to each such node a core index \(c_i = k\) and a layer index \(\ell_i = \ell\), then remove them from the network and update the degrees of their neighbors.
  3. Increment \(\ell\) by 1. Repeat step 2 until no nodes with degree \(d_i \le k\) remain in the network.
  4. Update \(k\) to the minimal degree among the remaining nodes and repeat steps 2-3 until all nodes have been assigned both a core index \(c_i\) and a layer index \(\ell_i\).
Each node \(i\) in the onion decomposition is characterized by the pair \((c_i, \ell_i)\), where \(c_i\) is the coreness and \(\ell_i\) the removal iteration within its core. The pair \((c_i, \ell_i)\) captures both the core hierarchy and intra-core connectivity, with higher values associated with nodes in denser regions of the network.The onion decomposition has been applied in a variety of contexts [3], including detecting atypical structures within \(k\)-cores of empirical networks [2], ranking nodes according to their structural position in the network [4, 5, 6], and designing heuristics for NP-hard optimization problems [7]. Other applications include using the OD to parameterize dynamical models of water distribution [8] and organizational networks [9], as well as for retrieving the underlying filamentary structure of the cosmic web [10].

References

[1] Shvydun, S. (2025). Zoo of Centralities: Encyclopedia of Node Metrics in Complex Networks. arXiv: 2511.05122 https://doi.org/10.48550/arXiv.2511.05122
[2] Hébert-Dufresne, L., Grochow, J. A., & Allard, A. (2016). Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition. Scientific reports, 6(1), 31708. doi: 10.1038/srep31708.
[3] Thibault, F., Hébert-Dufresne, L., & Allard, A. (2024). On the uniform sampling of the configuration model with centrality constraints. arXiv preprint arXiv:2409.20493. doi: 10.48550/arXiv.2409.20493.
[4] Young, J. G., St-Onge, G., Laurence, E., Murphy, C., Hébert-Dufresne, L., & Desrosiers, P. (2019). Phase transition in the recoverability of network history. Physical Review X, 9(4), 041056. doi: 10.1103/PhysRevX.9.041056.
[5] Mimar, S., & Ghoshal, G. (2022). A sampling-guided unsupervised learning method to capture percolation in complex networks. Scientific Reports, 12(1), 4147. doi: 10.1038/s41598-022-07921-x.
[6] Lu, Y., Huang, Y., Nie, J., Chen, Z., & Xuan, Q. (2024). RK-CORE: An Established Methodology for Exploring the Hierarchical Structure within Datasets. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 3150-3154). IEEE. doi: 10.1109/ICASSP48485.2024.10447791.
[7] García-Pérez, G., Allard, A., Serrano, M. Á., & Boguñá, M. (2019). Mercator: uncovering faithful hyperbolic embeddings of complex networks. New Journal of Physics, 21(12), 123033. doi: 10.1088/1367-2630/ab57d2.
[8] Zhou, X., Duenas‐Osorio, L., Doss‐Gollin, J., Liu, L., Stadler, L., & Li, Q. (2023). Mesoscale modeling of distributed water systems enables policy search. Water Resources Research, 59(5), e2022WR033758. doi: 10.1029/2022WR033758.
[9] Hébert-Dufresne, L., St-Onge, G., Meluso, J., Bagrow, J., & Allard, A. (2023). Hierarchical team structure and multidimensional localization (or siloing) on networks. Journal of Physics: Complexity, 4(3), 035002. doi: 10.1088/2632-072X/ace602.
[10] Bonnaire, T., Aghanim, N., Decelle, A., & Douspis, M. (2020). T-ReX: a graph-based filament detection method. Astronomy & Astrophysics, 637, A18. doi: 10.1051/0004-6361/201936859.