我有一个非常大的稀疏图G（约1亿个节点，约5000万个边缘），我想找到一个有效的算法（希望在O(1)或sub-linear中节点 边缘），以一定的概率预测该图中长度k周期的存在。为了实际使用，相对于G的大小，k将非常小（30至90之间）。还可以保证k永远是偶数。G也是随机图，因此我不希望任何一致的聚类。
该算法不需要枚举周期中包含的实际节点，如果它很可能没有长度k的任何周期，则只需消除G即可。
我找到了一个近距离解决方案，其中有答案，其中可以比较L的trace和rank（其中L是G的Laplacian），以确定G是否完全有任何周期。但是，我找不到一种相对有效的方法来计算G的rank。另一个问题是，它不考虑k，这可能能够采用更有效的方法。
获得连接的组件是一种可能性，但在节点 边的数量中是线性的，这对于此大小的图不是最佳的。
如果它是erdos-renyi随机图，那么由于拥有这样的周期是图形的单调属性，因此有一个零法律（https：//www.ams。org/journals/proc/1996-124-10/s0002-9939-96-03732-x/s0002-9939-96-96-03732-x.pdf），这意味着您可以通过设置正确的猜测来设置正确的猜测，。（哪个阈值？我不知道，但可能您可以从较小的图中推断出来。）