Che cos'è un algoritmo efficiente per il conteggio del numero di triangoli in un grafico?

Question

Che cos'è un algoritmo efficiente per il conteggio del numero di triangoli in un grafico non orientato) (dove un grafico è un insieme di vertici e spigoli)? Ho cercato su Google e leggendo il mio scaffale di libri di testo per alcune ore al giorno per tre giorni di fila.

Questo è per un compito a casa in cui ho bisogno di un tale algoritmo, ma lo sviluppo non conta nulla per l'assegnazione. Ci si aspetta che possiamo semplicemente trovare un tale algoritmo da risorse esterne, ma sono alla fine della mia corda.

Per un chiarimento, un triangolo in un grafico è un ciclo di lunghezza tre. Il trucco è che ha bisogno di lavorare su set di vertici con un massimo di 10.000 nodi.

Attualmente sto lavorando in C#, ma mi interessa più dell'approccio generale alla risoluzione di questo problema rispetto al codice da copiare e incollare.

A di alto livello, i miei tentativi finora inclusi:

• Una ricerca in ampiezza che rintracciato tutti i cicli unici di lunghezza tre. Mi è sembrata un'ottima idea, ma non sono riuscita a renderla funzionale
• Un ciclo su tutti i nodi nel grafico per vedere se tre vertici condividevano un bordo. Questo è troppo lento di un tempo di esecuzione per i set di dati più grandi. O (n^3).

L'algoritmo stesso è parte del calcolo del coefficiente di clustering.

Answer 1

Questo problema è difficile come la moltiplicazione della matrice. Vedi questo per reference.

Sai qualcosa sui grafici? Sono sparse? Altrimenti, non penso che farai molto meglio di O (n^3).

Answer 2

Dipende da come sono rappresentati i grafici.

Se si dispone di una matrice di adiacenza A il numero di triangoli deve essere tr (A^3)/6, in altre parole, 1/6 volte la somma degli elementi diagonali (la divisione si occupa dell'orientamento e della rotazione).

Se si dispone di elenchi di adiacenze, iniziare su ogni nodo ed eseguire una ricerca in profondità 3. Conta quante volte raggiungi quel nodo -> dividi per 6 di nuovo.

Answer 3

Se non ti interessa il numero esatto di triangoli, c'è un algoritmo di streaming molto semplice che fornisce uno stimatore non distorto. Si veda ad esempio here per una spiegazione.

Answer 4

Avrete bisogno prima della ricerca di profondità.L'algoritmo sarà:

1) Per il nodo corrente chiedono tutti i nodi adiacenti non visitati

2) per ciascuno di detti nodi eseguire profondità due controllo per vedere se un nodo in profondità 2 è il nodo corrente dal punto uno

3) segnano nodo corrente come visitato

4) sul make ogni nodo adiacente non visitato il vostro nodo corrente (1 da 1) ed eseguire lo stesso algoritmo

Answer 5

come citato qui: https://math.stackexchange.com/a/117030

L'algoritmo più veloce noto per la ricerca e il conteggio dei triangoli si basa sul prodotto a matrice veloce e ha una complessità di tempo O (nω), dove ω < 2.376 è l'esponente del prodotto a matrice veloce. Questo approccio porta tuttavia a una complessità dello spazio θ (n2).

Answer 6

Il conteggio dei triangoli è davvero difficile, e computazionalmente costoso. Forse questo è un buon punto di partenza per capire perché: Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning.

Il ciclo appropriato deve verificare per ognuno dei n nodi contro ciascuno dei loro vicini (n * (n-1)) e continuare il ciclo per vedere se i vicini di un vicino di casa di n sono n: (n * (n-1)) (n-1) (n-1), che è quasi 10^16 per 10000 n. Con un milione di nodi questi loop diventano sciocchi, ma per il tuo 10000 non dovresti avere alcun problema se vuoi forzarlo bruscamente :)

Hai detto che il codice in C# e il grafico (che è disponibile per C) ha un algoritmo eccellente per contare i triangoli scritti da Gabor Csardi. Conteggiava 1,3 milioni di triangoli nel mio grafico casuale di 10000 nodi e un milione di bordi in 1,3 secondi su un laptop di 5 anni :) Gabor Csardi sarebbe il tipo da chiedere :)

In termini di diversi approcci programmatici, forse tu dovrebbe guardare i dati in cui si memorizza la rete. Se memorizzato in una matrice di adiacenza, il numero di cicli è fisso, ma in un elenco di bordi di una rete di tre spigoli, il numero di cicli è un multiplo di tre indipendente dal numero di nodi. Potresti chiedere alla lista degli edge per i vicini di un nodo senza dover testare ogni combinazione di i-> j.

Ho scritto una sceneggiatura pedagogica in R per illustrare gli approcci e misurare la velocità dei diversi algoritmi in modo molto semplice. Ci sono molti problemi di velocità inerenti all'uso di R qui (la versione di bordo-elenco è completamente sommersa da troppi spigoli), ma penso che l'esempio di codice dovrebbe avere alcune idee che fluiscono su come pensare alla velocità della brutalità. forzare i conteggi dei triangoli. Questo è in R, e non estremamente pulito, ma ben commentato. Spero che tu possa rompere la barriera linguistica.

Tutto il meglio.

# Counting triangles in a random graph using igraph and two different 
# and almost equally stupid approaches looping through the 1) adjacency 
# matrix and 2) the edge-list in R. 

# Use igraph and these configs 
library(igraph) 
V <- 100 
E <- 1700 

# This is the random graph that we will use 
g <- erdos.renyi.game(type="gnm", n=V, p=E, directed=FALSE, loops=FALSE) 

# igraph has such a fast algorythm. Long live Gabor Csardi! 
benchmark <- proc.time()["elapsed"] 
     triangle.count <- sum(count_triangles(g)/3) 
gabor.Csardi.benchmark <- proc.time()["elapsed"] - benchmark 

# For not to big networks we can plot them to get a basic feel 
if(length(V(g)) < 100){ 
     V(g)$size <- 5 
     plot(g) 
} 

# The adjacency matrix approach will have to deal with a crazy 
# ammount of looping through pairs of matrix combinations to 
# find links: 

# We'll loop through each node to check it's participation in triangles 
# notice that a triangle ijk will be participated in by nodes 
# i, j, and k, and that each of those nodes have two triangular counts. 
# All in all the structures ijk, ikj, jik, jki, kij, kji are each counted 
# but shall be returned as 1 triangle. We will therefore devide our 
# search-result by 6 later on. 

# Store our progess in this matrix to look at how we did later on 
progress <- matrix(0, nrow=length(V(g)), ncol=8) 

# Loop through all nodes to find triangles in an adjacency matrix 
benchmark <- proc.time()["elapsed"] # Measure time for this loop 
for(i in 1:length(V(g))){ 
     # Node i has connections to these nodes: 
     i.neighbors <- as.vector(neighborhood(g, 1, nodes=i)[[1]]) 
     i.neighbors <- setdiff(i.neighbors, c(i)) # i should not be part of its own neighborhood 

     # for each i, tri is the number of triangles that i is involved in 
     # using any j or any k. For a triangle {1,2,3}, tri will be 2 for 
     # i==1, since i is part of both triangles {1,2,3} and {1,3,2}: 
     tri <- 0 

     for(j in i.neighbors) 
     { 
       # Node j has connections to these nodes: 
       j.neighbors <- as.vector(neighborhood(g, 1, nodes=j)[[1]]) 
       j.neighbors <- setdiff(j.neighbors, c(j)) # j should not be part of its own neighborhood 

       # Were any of j's neighbors also a neighbor of i? 
       k <- intersect(i.neighbors, j.neighbors) 

       tri <- tri + length(k) 
     } 

     # Save our findings to the progress matrix 
     progress[i,1] <- tri 
     progress[i,7] <- proc.time()["elapsed"] - benchmark 
} 
progress[,2] <- sapply(1:length(progress[,1]), function(x) sum(progress[,1][1:x])) 
progress[,3] <- round(progress[,2]/6, digits=2) 

# The edge-list approach uses a list of all edges in the network to loop through instead 
# Here, I suppose, a lot of the extra speed could arise from R being better at looping 
# with lapply() and at finding data in a data.frame that the brute-force loop above is. 
el <- as.data.frame(as.matrix(get.edgelist(g,))) 

# This is ugly. Make the edgelist contain all edges as both i->j and j->i. In 
# the igraph object, they are only given as low i to high j by get.edgelist() 
    el.rev <- data.frame(el[,2], el[,1]) 
    names(el) <- names(el.rev) <- c("i","j") 
    el <- rbind(el, el.rev) 

# these nodes are connected (we'd only need to bother abouth non isolates) 
nodes <- sort(unique(c(el$i, el$j))) 
tri <- 0 

# Loop through connected nodes to find triangles in edge-list 
benchmark <- proc.time()["elapsed"] # Measure time for this loop 
for(i in nodes){ 
     i.neighbors <- el[el$i==i,]$j 
     # i's neighbors are the $j:s of the edgelist where $i:s are i. 

     k.list <- unlist(lapply(i.neighbors, function(x) intersect(i.neighbors,el[el$i==x, ]$j))) 
     # lists nodes that can be a k in an ijk-triangle for each of i's neighboring j:s 
     # If 1 has neighbors 2 and 3, el[el$i==x, ]$j) will be first, the neighbors of 2 and then 
     # the neighbors of 3. When intersected with the neighbors of i, k:s will be found. If 
     # {1,2,3} is a triangle one k will be 3 for {i=1, j=2}, and another k will be 2 for {i=1, j=3} 

     # k.list might be NULL 
     tri.for.this.i <- (as.numeric(length(k.list))/2) 
     # Here we devide by two since i can be in a triangle with j and k lik {ijk} and {ikj} 
     # We will later have to devide by 3 more, since each triangle will be counted for 
     # each node i that we loop through 

     # Save the counting to the progress 
     tri <- tri.for.this.i + tri 
     progress[i,4] <- as.numeric(tri.for.this.i) 
     mm <- c(mm, i) 
     progress[i,8] <- proc.time()["elapsed"] - benchmark 
} 
progress[,5] <- sapply(1:length(progress[,4]), function(x) sum(progress[,4][1:x])) 
progress[,6] <- round(progress[,5]/3, digits=2) 

# Fix the results into a usable format 
results <- data.frame(c("igraph", "adjacency-loop", "edge-loop"), 
         c(triangle.count, max(progress[,3]), max(progress[,6])), 
         c(gabor.Csardi.benchmark, (max(progress[,7]) - min(progress[,7])), (max(progress[,8]) - min(progress[,8])))) 
row.names(results) <- c("igraph", "Adjacensy-loop", "Edge-loop") 
names(results) <- c("Routine", "Triangle count", "Execution-time") 

# Now we have run two approaches of more or less the same thing. 
# Not only should the igraph triangle.count, and the two loops 
# be identical, but the progress of the two methods should too. 
progress[,3] == progress[,6] 
plot(progress[,6], type="l", col="blue") 
lines(progress[,7], col="green") 

# Look at the result: 
View(results)