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

Question

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

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

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

Answer 1

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

Я предполагаю, что у вас есть словарь 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, большую библиотеку графов питонов.

Answer 2

Предполагая, что это неориентированный граф, ответ лежит в библиотеке Python networkx. если вам просто нужно посчитать треугольники, используйте:

import networkx as nx
tri=nx.triangles(g)

Но если вам нужно знать список ребер с треугольным (триадным) отношением, используйте

all_cliques= nx.enumerate_all_cliques(g)

Это даст вам все клики (k = 1,2,3 ... максимальная степень - 1)

Итак, чтобы отфильтровать только треугольники, т.е. k = 3,

triad_cliques=[x for x in all_cliques if len(x)==3 ]

triad_cliques выдаст список ребер только с треугольниками.

Answer 3

Довольно простой и понятный способ сделать это - использовать 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 узлами). клики - это части графика, где все узлы связаны друг с другом, что происходит в циклах / циклах с 3 узлами.

Answer 4

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

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

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

Answer 5

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

    #### function for counting undirected cycles
    def generate_triangles(nodes):
        visited_ids = set() # mark visited node
        for node_a_id in nodes:
            temp_visited = set() # to get undirected triangles
            for node_b_id in nodes[node_a_id]:
                if node_b_id == node_a_id:
                    raise ValueError # to prevent self-loops, if your graph allows self-loops then you don't need this condition
                if node_b_id in visited_ids:
                    continue
                for node_c_id in nodes[node_b_id]:
                    if node_c_id in visited_ids:
                        continue    
                    if node_c_id in temp_visited:
                        continue
                    if node_a_id in nodes[node_c_id]:
                        yield(node_a_id, node_b_id, node_c_id)
                    else:
                        continue
                temp_visited.add(node_b_id)
            visited_ids.add(node_a_id)

Конечно, вам нужно использовать словарь, например

    #### Test cycles ####

    nodes = {}

    nodes[0] = [1, 2, 3]
    nodes[1] = [0, 2]
    nodes[2] = [0, 1, 3]
    nodes[3] = [1]

    cycles = list(generate_triangles(nodes))
    print cycles

Используя код Wisty, найденные треугольники будут [(0, 1, 2), (0, 2, 1), (0, 3, 1), (1, 2, 3)]

, который считал треугольник (0, 1, 2) и (0, 2, 1) как два разных треугольника. С измененным кодом они считаются только одним треугольником.

Я использовал это с относительно небольшим словарем из 100 ключей, и каждый ключ в среднем имеет 50 значений.

Answer 6

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

Тогда, когда вы пробуете новые подходы, вы можете сделать две вещи: 1) Убедитесь, что ответ остается прежним. 2) Посмотрите, что это за улучшение.

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

После того, как у вас будет медленный тест, вы можете увидеть, можете ли вы сделать это параллельно, и посмотреть, каково увеличение производительности.

Затем вы можете увидеть, можете ли вы отметить все узлы, которые имеют менее 3 вершин.

В идеале вы можете сначала сократить его до 100 или около того, чтобы вы могли нарисовать его и посмотреть, что происходит в графическом виде.

Иногда ваш мозг увидит паттерн, который не так очевиден при взгляде на алгоритмы.

Answer 7

Я только что обнаружил, что nx.edge_disjoint_paths работает для подсчета треугольника, содержащего определенные ребра. быстрее, чем nx.enumerate_all_cliques и nx.cycle_basis. Он возвращает непересекающиеся пути ребер между источником и целью. Непересекающиеся пути ребер - это пути, которые не имеют общего ребра.
И результат-1 - это количество треугольников, которые содержат определенные ребра или между исходным узлом и целевым узлом.

edge_triangle_dict = {}
for i in g.edges:
    edge_triangle_dict[i] = len(list(nx.edge_disjoint_paths(g, i[0], i[1]))-1)

Answer 8

Это более эффективная версия Ajay M answer (я бы прокомментировал это, но у меня недостаточно репутации).

Действительно, метод enumerate_all_cliques для networkx вернет все клики на графике, независимо от их длины;следовательно, выполнение цикла может занять много времени (особенно с очень плотными графиками).

Более того, однажды определенная для треугольников, это просто вопрос параметризации, чтобы обобщить метод для каждой длины клики, поэтому вот функция:

import networkx as nx

def get_cliques_by_length(G, length_clique):
    """ Return the list of all cliques in an undirected graph G with length 
    equal to length_clique. """
    cliques = []
    for c in nx.enumerate_all_cliques(G) :
        if len(c) <= length_clique:
            if len(c) == length_clique:
                cliques.append(c)            
        else:
            return cliques
    # return empty list if nothing is found
    return cliques

Чтобы получить треугольники, просто используйте get_cliques_by_length(G, 3).

Предостережение : этот метод работает только для неориентированных графов.Алгоритм клик в ориентированных графах не приведен в networkx

Answer 9

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

from itertools import combinations as combos
[(n,nbr,nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2]]

Логика здесь состоит в том, чтобы проверять каждую пару соседей каждого узла, чтобы видеть, связаны ли они. G[n] - это быстрый способ перебора или поиска соседей.

Если вы хотите избавиться от переупорядочений, превратите каждую тройку в морозилку и сделайте набор из морозозонца:

set(frozenset([n,nbr,nbr2]) for n in G for nbr, nbr2 in combos(G[n]) if nbr in G[nbr2])

Если вам не нравится frozenset и вы хотите список наборов, то:

triple_iter = ((n, nbr, nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2])
triangles = set(frozenset(tri) for tri in triple_iter)
nice_triangles = [set(tri) for tri in triangles]

Answer 10

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

nx.triangles(G) # list of how many triangles each node is part of
sum(nx.triangles(G).values())/3 # total number of triangles

Альтернативный способ вернуть комки узлов будет что-то вроде ...

for u,v,d in G.edges(data=True):
    u_array = adj_m.getrow(u).nonzero()[1] # get lists of all adjacent nodes
    v_array = adj_m.getrow(v).nonzero()[1]
    # find the intersection of the two sets - these are the third node of the triangle
    np.intersect1d(v_array,u_array)