Ricerca del ciclo di 3 nodi (o triangoli) in un grafico

Question

Sto lavorando con reti complesse. Voglio trovare un gruppo di nodi che forma un ciclo di 3 nodi (o triangoli) in un dato grafico. Poiché il mio grafico contiene circa milioni di spigoli, l'uso di una soluzione iterativa semplice (più cicli "for") non è molto efficiente.

Sto usando python per la mia programmazione, se si tratta di alcuni moduli incorporati per la gestione di questi problemi, fatemelo sapere.

Se qualcuno conosce un algoritmo che può essere utilizzato per trovare triangoli nei grafici, rispondi gentilmente.

Answer 1

Anche se non è efficiente, è possibile implementare una soluzione, quindi utilizzare i loop. Scrivi un test in modo da avere un'idea di quanto tempo ci vuole.

Quindi, mentre provi nuovi approcci puoi fare due cose: 1) Assicurati che la risposta rimanga la stessa. 2) Scopri qual è il miglioramento.

Avere un algoritmo più veloce che manca qualcosa è probabilmente peggio che avere uno più lento.

Una volta eseguito il test lento, è possibile vedere se è possibile farlo in parallelo e vedere qual è l'aumento delle prestazioni.

Quindi, è possibile vedere se è possibile contrassegnare tutti i nodi con meno di 3 vertici.

Idealmente, si consiglia di ridurlo a circa 100 prima, in modo da poterlo disegnare e vedere cosa sta succedendo graficamente.

A volte il tuo cervello vedrà uno schema che non è così ovvio quando si osservano gli algoritmi.

Answer 2

Hai bisogno di trovare "tutti" i "triangoli", o solo "alcuni"/"qualsiasi"? O forse hai solo bisogno di testare se un nodo particolare fa parte di un triangolo?

Il test è semplice - dato un nodo A, ci sono due nodi collegati B & C che sono anche collegati direttamente.

Se è necessario trovare tutti i triangoli - in particolare, tutti i gruppi di 3 nodi in cui ogni nodo è unito agli altri due - allora è necessario controllare ogni gruppo possibile in un ciclo molto lungo 'per ogni' .

L'unica ottimizzazione è garantire che non si verifichi lo stesso "gruppo" due volte, ad es. se avete già provato che B & C non sono in un gruppo con A, allora non controllare se un & C sono in un gruppo con B.

Answer 3

Io non voglio sembrare duro, ma hai provato a Google? Il primo collegamento è un piuttosto veloce algoritmo per farlo: http://www.mail-archive.com/algogeeks@googlegroups.com/msg05642.html

E poi c'è questo articolo su ACM (che si può avere accesso a): http://portal.acm.org/citation.cfm?id=244866 (e se non si ha accesso, io sono certo se chiedi gentilmente alla signora che lo ha scritto, ne riceverai una copia)

Inoltre, posso immaginare un metodo di enumerazione triangolare basato sulla scomposizione di cricche, ma non so se è stato descritto da qualche parte.

Answer 4

Un milione di bordi è piuttosto piccolo.A meno che tu non lo stia facendo migliaia di volte, usa solo un'implementazione ingenua.

Suppongo che tu abbia un dizionario di node_ids, che puntano a una sequenza dei loro vicini e che il grafico è diretto.

Ad esempio:

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

La mia soluzione:

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 

prestazioni Controllo:

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) 

Quando ho provato, ci sono voluti più per costruire il grafo casuale che a contare i cicli.

Si potrebbe voler testarlo però;) Non garantisco che sia corretto.

Si potrebbe anche esaminare networkx, che è la grande libreria di grafi python.

Answer 5

Sto lavorando allo stesso problema del conteggio del numero di triangoli sul grafico non orientato e la soluzione di Wisty funziona molto bene nel mio caso. L'ho modificato un po 'quindi vengono contati solo i triangoli non orientati.

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

Naturalmente, è necessario utilizzare un dizionario per esempio

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

Utilizzando il codice di Wisty, i triangoli trovati saranno [(0, 1, 2), (0, 2 , 1), (0, 3, 1), (1, 2, 3)]

che ha contato il triangolo (0, 1, 2) e (0, 2, 1) come due triangoli diversi. Con il codice che ho modificato, questi sono contati come un solo triangolo.

L'ho usato con un dizionario relativamente piccolo con meno di 100 chiavi e ogni chiave ha in media 50 valori.

Answer 6

modo piuttosto semplice e chiaro da fare è utilizzare NetworkX:

Con NetworkX è possibile ottenere i cicli di un grafo non orientato da nx.cycle_basis(G) e quindi selezionare quelli con 3 nodi

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

o voi puoi trovare tutte le clique per find_cliques(G) e quindi selezionare quelle che desideri (con 3 nodi). le clique sono sezioni del grafico in cui tutti i nodi sono collegati tra loro che avviene in cicli/cicli con 3 nodi.

Answer 7

Sorpreso di non vedere la funzione dei triangoli Networkx. So che non restituisce necessariamente i gruppi di nodi che formano un triangolo, ma dovrebbe essere abbastanza rilevante per molti che si trovano su questa pagina.

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

Un modo alternativo per tornare ciuffi di nodi sarebbe qualcosa di simile ...

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

Assumendo la sua un grafo non orientato, la risposta sta nella libreria NetworkX di pitone. se avete solo bisogno di contare triangoli, utilizzare:

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

Ma se avete bisogno di conoscere l'elenco bordo con il triangolo rapporto (triadico), utilizzare

all_cliques= nx.enumerate_all_cliques(g) 

Questo vi darà tutte le cricche (k = 1,2,3 ... max gradi - 1)

Così, per filtrare solo triangoli cioè k = 3,

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

Le triad_cliques daranno una lista di bordo con solo triangoli.

Answer 9

Se non si cura di più copie dello stesso triangolo in modo diverso poi un elenco di 3-tuple funziona:

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

La logica qui è quello di verificare ogni coppia di vicini di casa di ogni nodo vedere se sono collegati. G[n] è un modo rapido per scorrere o cercare i vicini.

Se si vuole sbarazzarsi di reorderings, trasformare ogni tripla in un frozenset e fare una serie di frozensets:

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

Se non ti piace frozenset e volete un elenco di gruppi poi:

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

Questa è una versione più efficiente delle Ajay M answer (avrei commentato, ma non ho abbastanza reputazione).

Infatti il ​​metodo di networkxenumerate_all_cliques restituirà tutti cricche nel grafico, indipendentemente dal loro lunghezza; di conseguenza, il passaggio in sequenza potrebbe richiedere molto tempo (soprattutto con grafici molto densi).

Inoltre, una volta definita per triangoli, è solo una questione di parametrizzazione di generalizzare il metodo per ogni lunghezza di cricca ecco una funzione:

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 

Per ottenere triangoli basta usare get_cliques_by_length(G, 3).

Caveat: questo metodo funziona solo per i grafici non orientati. Algoritmo per cricche nei grafici diretti non sono forniti in networkx