我有一个非常大的稀疏图G（大约1亿个节点，大约5000万个边缘），我想找到一个有效的算法（希望O(1)或节点数+边缘的子线性），以某种可能性预测存在在该图中，k长度的周期。对于实际使用，相对于k的大小，G将非常小（在30到90之间）。保证k永远是平等的。 G也是一个随机图，所以我不期望任何一致的聚类。
该算法不需要枚举循环中包含的实际节点，如果它很可能没有任何长度为G的循环，则只需要消除k。
我找到了一个接近解决方案，答案是here，其中trace和rank的L（其中L是G的拉普拉斯）可以进行比较，以确定G是否有任何循环。但是，我找不到一种相对有效的方法来为rank计算G。另一个问题是它不考虑k，这可能能够提供更有效的方法。
获取连接组件是可能的，但它在节点数+边数方面是线性的，对于此大小的图形而言，这不是最佳的。
如果它是一个鄂尔多斯 - 仁义随机图，那么由于这样的周期是图的单调性质，所以存在零一法（https://www.ams.org/journals/proc/1996-124-10/S0002-9939-96-03732-X/S0002-9939-96-03732-X.pdf），这意味着你可以通过设置正确的阈值来做出相当好的猜测。 （哪个阈值？我不知道，但可能你可以从较小的图中推断出来。）