algorithm - 增量 k 核心算法

Question

计算 k-core通过迭代修剪顶点的图是很容易的。但是，对于我的应用程序，我希望能够将顶点添加到起始图中并获得更新的核心，而不必从头开始重新计算整个 k-core。是否有可靠的算法可以利用之前迭代中完成的工作？

出于好奇，k-core 被用作 clique 查找算法中的预处理阶段。任何大小为 5 的团都保证是图的 4 核的一部分。在我的数据集中，4 核比整个图小得多，因此从那里暴力破解它可能很容易处理。递增地添加顶点可以让算法使用尽可能小的数据集。我的顶点集是无限且有序的(质数)，但我只关心编号最小的团。

编辑:

根据 akappa 的回答再考虑一下，检测循环的创建确实很关键。在下图中，在添加 F 之前 2-core 是空的。添加 F 不会改变 A 的度数，但它仍然会将 A 添加到 2-core。很容易扩展它以查看关闭任何大小的循环将如何导致所有顶点同时加入 2 核。

添加一个顶点可能会对任意距离外的顶点的核心性产生影响，但也许这过于关注最坏情况的行为。

Answer 1

在我看来，基于图的局部探索的增量 k 核计算算法，而不是“全局”迭代修剪，需要增量循环检测，以便查看哪些边可能有助于进入k-core中的一个顶点，这是一个难题。

我认为你能做的最好的事情就是在每次通过时重新计算 k-core 算法，只需从图中删除已经在 k-core 中的顶点并在 map 顶点 -> “k- core adjacent vertices"已经在 k-core 中的相邻顶点的数量。