通过反复修剪顶点计算图的k-core很容易。但是，对于我的应用程序，我希望能够将顶点添加到起始图形并获得更新的核心，而无需从头重新计算整个k-core。有没有一种可靠的算法可以利用之前迭代所做的工作？增量k核算法
为了好奇，K核被用作一个派系寻找算法的预处理阶段。任何大小为5的派系保证是图的4核心的一部分。在我的数据集中，4核比整个图小得多，所以从那里蛮横逼迫它可能会很难处理。递增添加顶点可以使算法尽可能少地使用数据集。我的顶点集是无限的，并且是有序的（素数），但我只关心编号最小的团。
编辑：
关于它的思考多一些基于akappa的回答，检测一个循环的建立确实是至关重要的。在下面的图表中，在添加F之前，2内核是空的。添加F并不会改变A的程度，但它仍将A添加到2内核。这很容易扩展，以查看关闭任何大小的循环如何导致所有顶点同时加入双核。
添加一个顶点可以影响任意距离的顶点的核心性，但是这可能会关注最坏情况的行为。
在我看来，基于图形的局部探索，而不是一个“全局”迭代修剪，对于增量k-核计算的算法，需要一个增量环路检测才能看到哪些边缘可能有助于进入k核心的顶点，这是一个难题。
我认为你可以做的最好的是重新计算每遍的k核算法，只是从图中去除已经存在于k核中的顶点并初始化，在顶点顶点→k中核心相邻顶点“是已经在K核中的相邻顶点的数量。
快速构思： 您可以将历史保存在列表L中，即保存删除节点的顺序。每当添加一个新节点v时，从L中与v相邻的第一个节点w开始，然后按照线性顺序从L中开始执行L中剩余的节点。 （并测试节点v以及可能将其添加到L.）
这是一个难题，但绝对不是NP-Hard。据我所知，在学术界没有增量更新任何数K的K核的通用解决方案。但以下两篇论文绝对值得参考：
[1]提取分析和可视化三角形K-网络中的核心图案。 http://www.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf
[2] k核分解的流式算法。 http://www.cse.ohio-state.edu/~sariyuce/file/Publications_files/VLDB13.pdf
它们出现在数据管理领域的重要会议中，所以方法应该是可靠的。