我有一个非常大的稀疏图G(大约1亿个节点,大约5000万个边),我想找到一个有效的算法(希望O(1)或在节点+边的数量上是次线性的)以某种概率预测这个图中是否存在长度k的循环。对于实际应用,k相对于G的大小将非常小(介于30到90之间)。它还保证k将始终是均匀的。G也是一个随机图,因此我不期望任何一致的集群。
该算法不需要枚举循环中包含的实际节点,只要消除G,如果它很可能没有任何长度k的循环。
我找到了一个答案为here的封闭解,其中可以比较tracerankL(其中LG的拉普拉斯)来确定G是否有任何循环。但是,我找不到一种相对有效的方法来计算rank。另一个问题是它没有考虑到G,这可能会使方法更有效。
获取连接的组件是可能的,但是它在节点数+边数上是线性的,这对于这样大的图来说不是最优的。

最佳答案

如果它是一个鄂尔多斯——仁义随机图,那么既然有这样一个循环是一个图的单调性质,那么就有一个零一定律(https://www.ams.org/journals/proc/1996-124-10/S0002-9939-96-03732-X/S0002-9939-96-03732-X.pdf),这意味着你可以通过设置正确的阈值做出一个合理的猜测。(哪个门槛?我不知道,但也许你可以从更小的图表中推断出来。)

关于algorithm - 高效的近似算法,可确定图中是否存在k尺寸的循环,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/55087010/

10-11 23:03
查看更多