algorithm - 确定图中是否存在 k 大小循环的高效近似算法

Question

我有一个非常大的稀疏图 G(大约 1 亿个节点，大约 5000 万条边)，我想找到一种有效的算法(希望是 O(1) 或节点 + 边数的次线性)，它可以预测一些此图中存在长度为 k 的循环的概率。对于实际使用， k 相对于 G 的大小将非常小(在 30 到 90 之间)。也保证 k 永远是偶数。 G 也是一个随机图，所以我不期望任何一致的聚类。

该算法不需要枚举循环中包含的实际节点，如果很可能没有任何长度为 G 的循环，它只需要消除 k 。

我找到了一个答案为 here 的近似解决方案，其中可以比较 trace 和 rank 的 L(其中 L 是 G 的拉普拉斯算子)以确定 G 是否有任何循环。但是，我找不到相对有效的方法来为 rank 计算 G 。另一个问题是它没有考虑 k，这可能是一种更有效的方法。

获取连通分量是可能的，但它在节点 + 边的数量上是线性的，这对于这种大小的图来说不是最优的。

Answer 1

如果它是 Erdos--Renyi 随机图，那么由于具有这样的循环是图的单调属性，因此存在零一定律 (https://www.ams.org/journals/proc/1996-124-10/S0002-9939-96-03732-X/S0002-9939-96-03732-X.pdf)，这意味着您可以通过设置正确的阈值。 (哪个阈值？我不知道，但你可能可以从较小的图表中推断出来。)