Finding Zyklus von 3 Knoten (oder Dreiecke) in einem Diagramm

Question

Ich arbeite mit komplexen Netzwerken. Ich möchte eine Gruppe von Knoten finden, die einen Zyklus von 3 Knoten (oder Dreiecken) in einem gegebenen Graph bildet. Da mein Graph ungefähr Millionen Kanten enthält, ist die Verwendung einer einfachen iterativen Lösung (mehrere "for" -Schleifen) nicht sehr effizient.

Ich benutze Python für meine Programmierung, wenn dies einige eingebaute Module für die Behandlung dieser Probleme sind, lass es mich wissen.

Wenn jemand einen Algorithmus kennt, der zum Finden von Dreiecken in Graphen verwendet werden kann, bitte zurücksenden.

Answer 1

Auch wenn es nicht effizient ist, möchten Sie vielleicht eine Lösung implementieren, also verwenden Sie die Schleifen. Schreiben Sie einen Test, damit Sie eine Vorstellung davon bekommen, wie lange es dauert. Wenn Sie neue Ansätze ausprobieren, können Sie zwei Dinge tun: 1) Stellen Sie sicher, dass die Antwort gleich bleibt. 2) Sehen Sie, was die Verbesserung ist.

Einen schnelleren Algorithmus zu haben, der etwas vermisst, wird wahrscheinlich schlimmer sein als ein langsamer.

Sobald Sie den langsamen Test haben, können Sie sehen, ob Sie dies parallel tun können und sehen, was die Leistungssteigerung ist.

Dann können Sie sehen, ob Sie alle Knoten mit weniger als 3 Scheitelpunkte markieren können.

Im Idealfall möchten Sie es vielleicht zuerst auf 100 reduzieren, damit Sie es zeichnen und sehen können, was grafisch passiert.

Manchmal sieht Ihr Gehirn ein Muster, das bei der Betrachtung von Algorithmen nicht so offensichtlich ist.

Answer 2

Müssen Sie "alle" Dreiecke oder nur "einige"/"irgendwelche" finden? Oder vielleicht müssen Sie nur testen, ob ein bestimmter Knoten Teil eines Dreiecks ist?

Der Test ist einfach - bei einem Knoten A gibt es zwei verbundene Knoten B & C, die auch direkt verbunden sind.

Wenn Sie alle Dreiecke finden müssen - speziell alle Gruppen von 3 Knoten, in denen jeder Knoten mit den anderen zwei verbunden ist - dann müssen Sie jede mögliche Gruppe in einer sehr langen Ausführung 'für jede' Schleife überprüfen .

Die einzige Optimierung besteht darin sicherzustellen, dass Sie die gleiche 'Gruppe' nicht zweimal überprüfen, z. wenn Sie bereits getestet haben, dass B & C mit A nicht in einer Gruppe sind, prüft dann nicht, ob A & C in einer Gruppe ist mit B.

Answer 3

Ich will nicht hart klingen, aber Sie haben versucht, Google es? Der erste Link ist ein ziemlich schneller Algorithmus zu tun, dass: http://www.mail-archive.com/algogeeks@googlegroups.com/msg05642.html

Und dann gibt es in diesem Artikel auf ACM (die Sie Zugriff haben können): http://portal.acm.org/citation.cfm?id=244866 (und wenn Sie keinen Zugriff haben, ich bin sicher, wenn Sie die Dame bitten, die es schrieb, erhalten Sie eine Kopie.)

Auch kann ich mir eine Dreieckaufzählungsmethode vorstellen, die auf clique-Zersetzung basiert, aber ich weiß nicht, ob es irgendwo beschrieben wurde.

Answer 4

Eine Million Kanten ist ziemlich klein.Wenn Sie es nicht tausende Male tun, verwenden Sie einfach eine naive Implementierung.

Ich nehme an, dass Sie ein Wörterbuch von node_ids haben, die auf eine Sequenz ihrer Nachbarn zeigen, und dass das Diagramm gerichtet ist.

Zum Beispiel:

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

Meine Lösung:

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 

prüfen Leistung:

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) 

Als ich es versucht, es dauerte länger die Zufallsgraphen zu bauen, als zu zählen die Zyklen.

Sie möchten es vielleicht testen;) Ich kann nicht garantieren, dass es korrekt ist.

Sie könnten auch in NetworkX, das ist die große Python-Graph-Bibliothek.

Answer 5

Ich arbeite an dem gleichen Problem des Zählens der Anzahl der Dreiecke auf ungerichtet Graph und Wisty's Lösung funktioniert wirklich gut in meinem Fall. Ich habe es ein wenig modifiziert, so dass nur ungerichtete Dreiecke gezählt werden.

#### 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) 

Natürlich müssen Sie zum Beispiel ein Wörterbuch verwenden

#### 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 

den Code Wisty Verwendung fanden die Dreiecke [(0, 1, 2) sein, (0, 2 , 1), (0, 3, 1), (1, 2, 3)]

, die das Dreieck (0, 1, 2) und (0, 2, 1) als zwei verschiedene Dreiecke zählte. Mit dem Code, den ich modifiziert habe, werden diese als nur ein Dreieck gezählt.

Ich benutzte dies mit einem relativ kleinen Wörterbuch von weniger als 100 Tasten und jede Taste hat durchschnittlich 50 Werte.

Answer 6

Ziemlich einfach und übersichtlich zu tun ist, NetworkX zu verwenden:

Mit NetworkX Sie die Schlaufen eines ungerichteten Graphen von nx.cycle_basis(G) erhalten können und wählen Sie dann die, die mit 3 Knoten

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

oder Sie finden Sie alle Cliquen von find_cliques(G) und wählen Sie dann die gewünschten (mit 3 Knoten). Cliquen sind Abschnitte des Graphen, wo alle Knoten miteinander verbunden sind, was in Zyklen/Schleifen mit 3 Knoten geschieht.

Answer 7

Überrascht, keine Erwähnung der Netzwerkx Dreiecke Funktion zu sehen. Ich weiß, dass es nicht unbedingt die Gruppen von Knoten zurückgibt, die ein Dreieck bilden, sondern für viele, die sich auf dieser Seite befinden, ziemlich relevant sein sollte.

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

Eine alternative Möglichkeit, Klumpen von Knoten zurückzukehren wäre so etwas wie ...

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) 

Answer 8

sein ein ungerichteten Graphen Unter der Annahme, liegt die Antwort in NetworkX Bibliothek von Python. wenn Sie nur Dreiecke zählen müssen, verwenden:

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

Aber wenn man die Kantenliste mit Dreieck (Triade) Beziehung wissen müssen, finden Sie dieses

all_cliques= nx.enumerate_all_cliques(g) 

verwenden geben alle Cliquen (k = 1,2,3 ... max Grad - 1)

Also, Dreiecke zu filtern, dass nur das heißt k = 3,

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

Die triad_cliques ergeben eine Kantenliste mit nur Dreiecken.

Answer 9

Wenn Sie nicht über mehrere Kopien desselben Dreiecks in unterschiedlicher Reihenfolge kümmern sich dann eine Liste von 3-Tupeln funktioniert:

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]] 

Die Logik hier ist jedes Paar von Nachbarn von jedem Knoten zu überprüfen, sehen Sie, ob sie verbunden sind. G[n] ist eine schnelle Möglichkeit, über Nachbarn zu iterieren oder nachzuschlagen.

Wenn Sie loswerden Umordnungen bekommen, drehen sich dreifach in eine frozenset und einen Satz der frozensets machen:

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

Wenn Sie frozenset nicht mögen und wollen eine Liste von Sätzen dann:

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

Dies ist eine effizientere Version von Ajay M answer (ich hätte es kommentiert, aber ich habe nicht genug Ruf).

der Tat die enumerate_all_cliques Methode der networkx wird alle Cliquen in der Grafik zurückkehren, und zwar unabhängig von ihrer Länge; daher kann das Überschleifen viel Zeit in Anspruch nehmen (besonders bei sehr dichten Graphen).

Außerdem einmal für Dreiecken definiert, es ist nur eine Frage der Parametrisierung das Verfahren für jede Clique Länge zu verallgemeinern, so ist hier eine Funktion:

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 

Um Dreiecke nur get_cliques_by_length(G, 3) verwenden.

Vorbehalt: Diese Methode funktioniert nur für ungerichtete Graphen. Algorithmus für Cliquen in gerichteten Graphen sind nicht in networkx