增量k-core算法

Question

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

出于好奇，k-core被用作集团发现算法的预处理阶段。任何大小为5的团都保证是图的4核的一部分。在我的数据集中，4核比整个图要小得多，所以从那里强制它可能是很容易处理的。增量添加顶点可以让算法处理尽可能小的数据集。我的顶点集是无限有序的(质数)，但我只关心编号最低的集团。

编辑：

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

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

​

​

Answer 1

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

我认为你能做的最好的就是在每次遍历时重新计算k-核心算法，从图中删除已经在k-核心中的顶点，并在地图顶点->中初始化已经在k-核心中的相邻顶点的数量。

Answer 2

这是一个困难的问题，但绝对不是NP难的。据我所知，学术界对K核的增量更新还没有通用的解决方案，但以下两篇论文绝对值得一读：

1网络中三角形K-Core模体的提取、分析和可视化。http://www.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf

2 k-core分解的流式算法。http://www.cse.ohio-state.edu/~sariyuce/file/Publications_files/VLDB13.pdf

它们出现在数据管理领域的主要会议上，因此方法应该是可靠的。

Answer 3

快速的想法:你可以将历史记录保存在列表L中，也就是说，保存节点被移除的顺序。每当你添加一个新的节点v时，从L中与v相邻的第一个节点w开始，然后从w开始按线性顺序遍历L中的其余节点。(并测试节点v，并可能将其添加到L。)