Поиск цикла из 3 узлов (или треугольников) в графе

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

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

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

    Миллион ребер довольно мал. Если вы не делаете это тысячи раз, просто используйте наивную реализацию.

    Я предполагаю, что у вас есть словарь node_ids, который указывает на последовательность их соседей и что график направлен.

    Например:

    nodes = {} nodes[0] = 1,2 nodes[1] = tuple() # empty tuple nodes[2] = 1 

    Мое решение:

     def generate_triangles(nodes): """Generate triangles. Weed out duplicates.""" visited_ids = set() # remember the nodes that we have tested already for node_a_id in nodes: for node_b_id in nodes[node_a_id]: if nod_b_id == node_a_id: raise ValueError # nodes shouldn't point to themselves if node_b_id in visited_ids: continue # we should have already found b->a->??->b for node_c_id in nodes[node_b_id]: if node_c_id in visited_ids: continue # we should have already found c->a->b->c if node_a_id in nodes[node_c_id]: yield(node_a_id, node_b_id, node_c_id) visited_ids.add(node_a_id) # don't search a - we already have all those cycles 

    Проверка производительности:

     from random import randint n = 1000000 node_list = range(n) nodes = {} for node_id in node_list: node = tuple() for i in range(randint(0,10)): # add up to 10 neighbors try: neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node except: continue if not neighbor_id in node: node = node + (neighbor_id,) nodes[node_id] = node cycles = list(generate_triangles(nodes)) print len(cycles) 

    Когда я это пробовал, потребовалось больше времени, чтобы построить случайный граф, чем считать циклы.

    Возможно, вы захотите его протестировать;) Я не буду гарантировать, что это правильно.

    Вы также можете посмотреть в networkx, которая является большой библиотекой графов python.

    Я не хочу звучать суровым, но вы пытались это сделать Google? Первая ссылка – довольно быстрый алгоритм для этого: http://www.mail-archive.com/algogeeks@googlegroups.com/msg05642.html

    И затем есть статья об ACM (к которой у вас может быть доступ): http://portal.acm.org/citation.cfm?id=244866 (и если у вас нет доступа, я уверен, что если вы любезны спросите у леди, которая ее написала, вы получите копию.)

    Кроме того, я могу представить себе метод перечисления треугольника, основанный на клике-декомпозиции, но я не знаю, было ли это описано где-то.

    Довольно простой и понятный способ – использовать Networkx:

    С помощью Networkx вы можете получить петли неориентированного графика с помощью nx.cycle_basis (G), а затем выбрать те, у которых есть 3 узла

     cycls_3 = [c for c in nx.cycle_basis(G) if len(c)==3] 

    или вы можете найти все клики find_cliques (G), а затем выбрать нужные (с 3 узлами). cliques – это части графика, где все узлы связаны друг с другом, что происходит в циклах / циклах с тремя узлами.