У меня очень большой разреженный граф G (около 100 миллионов узлов, около 50 миллионов ребер), и я хотел бы найти эффективный алгоритм (надеюсь O(1) или сублинейный по числу узлов + ребер)который с некоторой вероятностью предсказывает наличие цикла длины k на этом графике.Для практического использования k будет очень маленьким (между 30 и 90) относительно размера G.Также гарантируется, что k всегда будет четным.G также случайный граф, поэтому я не ожидаю какой-либо последовательной кластеризации.
Алгоритм не должен перечислять фактические узлы, содержащиеся в цикле, он просто должен исключить G, если он, скорее всего, не имеет циклов длины k.
Я нашел близкое решение с ответом, представленным здесь , где trace и rank из L (где L - это лапласиан G) могутсравните, чтобы определить, имели ли G какие-либо циклы вообще.Однако я не смог найти относительно эффективный способ вычисления rank для G.Другая проблема заключалась в том, что он не учитывает k, что может сделать более эффективный подход.
Возможно получение связанных компонентов, но оно линейно по числу узлов + ребер, что не является оптимальным для графика такого размера.