增量k核算法

Question

通过迭代修剪顶点来计算图的k核是很容易的.但是,对于我的应用程序,我希望能够将顶点添加到起始图并获得更新的核心,而无需从头开始重新计算整个k-core.是否有可靠的算法可以利用先前迭代所做的工作？

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

编辑:

基于akappa的答案更多地考虑它,检测循环的创建确实很关键.在下图中,在添加F之前,2核是空的.添加F不会改变A的程度,但它仍然将A添加到2核.扩展它很容易看到关闭任何大小的循环会导致所有顶点同时加入2核.

添加顶点会对任意距离之外的顶点的核心性产生影响,但这可能会过多地关注最坏情况的行为.

Answer 1

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

我认为你能做的最好的事情就是在每次传递时重新计算 k 核算法，只需从图中删除 k 核中已经存在的顶点并在地图顶点 - >“k 核相邻顶点”中进行初始化“ k 核中已有的相邻顶点的数量。