Нахождение цикла из 3-х узлов (или треугольников) в графе

Question

Я работаю со сложными сетями. Я хочу найти группу узлов, которая образует цикл из 3 узлов (или треугольников) в данном графе. Поскольку мой график содержит около миллиона ребер, использование простого итеративного решения (многократного цикла «для») не очень эффективно.

Я использую python для своего программирования, если это какие-то встроенные модули для решения этих проблем, пожалуйста, дайте мне знать.

Если кто-то знает какой-либо алгоритм, который можно использовать для поиска треугольников на графиках, просьба ответить.

Answer 1

Вам нужно найти «все» из «треугольников» или просто «некоторые» / «любые»? Или, возможно, вам просто нужно проверить, является ли конкретный узел частью треугольника?

Тест прост - для узла A есть два любых подключенных узла B & C, которые также напрямую связаны.

Если вам нужно найти все треугольники, в частности, все группы из 3 узлов, в которых каждый узел соединен с двумя другими, то вам нужно проверить каждую возможную группу в очень длительном цикле «для каждого».

Единственная оптимизация - это то, что вы не проверяете одну и ту же «группу» дважды, например если вы уже проверяли, что B & C не входят в группу с A, то не проверяйте, входят ли A & C в группу с B.