网络是表示和分析社会、生物和技术领域中由相互作用实体构成的复杂系统的强大工具。网络科学已发展成为一个关键的跨学科领域，连接了离散数学、统计物理学、计算机科学和应用学科[1,2]。现实世界网络的一个显著特征是其异质性结构，表现为少数节点具有不成比例的高连接性或中心性[3]。这种结构不对称性表明，大规模系统的功能往往严重依赖于少数关键节点。识别这些关键节点是网络科学中最重要的任务之一[4]，这使我们能够开展更成功的社会广告活动、对疫情高风险人群进行免疫、发现药物靶点候选物和必需蛋白质，以及防止电网、金融市场和生态系统中的级联故障。

因为找到网络中的关键节点这个问题非常重要，近年来有数以百计的节点重要性指标被提出[5,6]，包括只考虑节点局部结构的，如度和H指数[7]；考虑连接节点的路径的，如closeness和betweenness[8]；考虑邻接矩阵特征向量的，如eigencentrality[9]，等等。其中，通过网络分解（一般而言，是把网络按从不重要到重要，就像剥洋葱一样，分解成很多层次）来寻找网络中的关键节点，特别是k-core分解的方法，被认为在很多实际场景中表现优异[10]。

假设我们有一个无向简单连通图。我们先取k=1，然后开始“清理”网络，把所有度小于等于1的节点移除掉，之后可能又会出现一些度小于等于1的节点，我们继续移除，依此类推，直到剩下的子网络每一个节点的度都大于1。这些被移除的节点就构成了k-core分解的第一层，我们称之为1-shell。接下来，我们取k=2，然后又开始“清理”网络，把所有度小于等于2的节点移除掉，之后可能又会出现一些度小于等于2的节点，我们继续移除，依此类推，直到剩下的子网络每一个节点的度都大于2。这些被移除的节点就构成了k-core分解的第二层，我们称之为2-shell。我们接着取k=3, k=4, ……直到网络中所有的节点都被移除。这个时候，一个节点所在的层数，就被称之为这个节点的k-shell指数，或者核数（coreness）。下图a给出了一个网络k-core分解的结果。

k-core分解有一个显而易见的缺点，就是分辨率特别低。如图a，网络中34个节点只有4个层次，所以很多节点的k-shell指数都一样，没有办法区分哪个节点更加重要。最小度分解（Lowest Degree Decomposition, LDD）就是为了克服这个问题而提出的一种新的网络分解方式[11,12]。一个无向简单连通图，最小度分解每次把网络中所有度等于当前最小度的节点移除，而一个节点的LDD指数就是它被移除的批次数——比如一个节点第4批被移除，那么它的LDD指数就为4。上图b给出了一个网络最小度分解的结果。有趣的是，可以证明，最小度分解是k-core分解的一个细分[12]，换句话说，具有相同k-shell指数的两个节点可能被最小度分解划分到不同批次，因此具有不同的LDD指数（LDD指数比k-shell指数分辨率更高），但是如果i节点的k-shell指数大于j节点的k-shell指数，那么i节点的LDD指数肯定也比j节点大。所以，最小度分解就是把k-core分解的每一层再做分解从而提高k-core分解分辨率的一种方法。我们还注意到，最小度分解得到的最重要节点在网络中分布比较分散（如下图，排名前5%节点被标为红色），这使其在寻找一组关键节点之类的任务中占据优势[6]。

进一步地，我们测试了传播动力学（SIR和SIS模型）[13]、生态动力学（基于食物链网络的捕食-被捕食动力学）[14]、牵引控制（控制少数节点使网络达到同步）[15]等网络中得到充分研究的一些动力学过程，发现在找出关键节点的任务中，最小度分解都显示出了好于k-core分解的表现，也比很多前沿的方法效果要好。

最小度分解只有线性复杂度，实施起来非常简单，数学性质也很优美[12]。最小度分解不仅可以用于挖掘关键节点，而且可以作为分析网络的一种新工具，同时也可以作为网络可视化的一种新工具。

参考文献：

[1] Barabási A-L. Network science. Cambridge: Cambridge University Press; 2016.

[2] Newman MEJ. Networks. Oxford: Oxford University Press; 2018.

[3] Caldarelli G. Scale-free networks: complex webs in nature and technology. Oxford: Oxford University Press; 2007.

[4] Lü L, Chen D, Ren X-L, Zhang Q-M, Zhang Y-C, Zhou T. Vital nodes identification in complex networks. Physics Reports 2016; 650: 1-63,

[5] Oldham S, Fulcher B, Parkes L, Arnatkeviciute A, Suo C, Fornito A. Consistency and differences between centrality measures across distinct classes of networks. PLoS ONE 2019; 14: e0220061.

[6] Bi Y, Jiao X, Zhou T. Performances and Correlations of Centrality Measures in Complex Networks. arXiv: 2508.09563.

[7] Lü L, Zhou T, Zhang Q-M, Stanley HE. The H-index of a network node and its relation to degree and coreness. Nature Communications 2016; 7: 10168.

[8] Freeman LC. A set of measures of centrality based on betweenness. Sociometry 1977; 40: 35-41.

[9] Bonacich P. Power and centrality: A family of measures. American Journal of Sociology 1987; 92: 1170-1182.

[10] Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA. Identification of influential spreaders in complex networks. Nature Physics 2010; 6: 888-893.

[11] Yang F, Li X, Xu Y, Liu X, Wang J, Zhang Y, Zhang R, Yao Y. Ranking the spreading influence of nodes in complex networks: An extended weighted degree centrality based on a remaining minimum degree decomposition. Physics Letters A 2018; 382: 2361-2371.

[12] Yu Y, Jing M, Zhao N, Zhou T. Lowest degree decomposition of complex networks. Chaos, Solitons and Fractals 2025; 199: 116765.

[13] Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A. Epidemic processes in complex networks. Review of Modern Physics 2015; 87: 925-979.

[14] Morone F, Del Ferraro G, Makse HA. The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature Physics 2019; 15: 95-102.

[15] Li X, Wang X, Chen G. Pinning a complex dynamical network to its equilibrium. IEEE Transactions on Circuits and Systems I: Regular Papers 2004; 51: 2074-2087.