python - 计算图的退化？

Question

我正在寻找一种方法来计算给定图的退化。维基百科文章概述了一种方法，但它也存储了简并排序，我想我几周前在网上的某个地方看到了一个更简单的算法，但现在找不到了。如果我对存储图的简并排序不感兴趣，我想知道是否有更有效的方法来计算图的简并？

如果重要的话，我正在使用 networkx 和 Python。

谢谢！

Answer 1

NetworkX 有 Batagelj 和 Zaversnik 的 O(m) 核心算法，我认为您可以将其用于您的目的 degeneracy(G) = max(networkx.core_number(G).values())： http://networkx.lanl.gov/reference/algorithms.core.html