algorithm - tiene - triangulacion delaunay c++

¿Qué es un algoritmo eficiente para contar la cantidad de triángulos en un gráfico?

Question

¿Qué es un algoritmo eficiente para contar el número de triángulos en un gráfico no dirigido) (donde un gráfico es un conjunto de vértices y bordes)? He estado buscando en Google y leyendo mi estante de libros de texto durante unas horas cada día durante tres días seguidos.

Esto es para una tarea que requiera tal algoritmo, pero su desarrollo no cuenta para nada en la tarea. Se espera que simplemente podamos encontrar tal algoritmo de recursos externos, pero estoy al final de mi cuerda.

Para aclarar, un triángulo en un gráfico es un ciclo de longitud tres. El truco es que necesita trabajar en conjuntos de vértices con un máximo de 10.000 nodos.

Actualmente estoy trabajando en C #, pero me importa más el enfoque general para resolver este problema que el código para copiar y pegar.

En el alto nivel, mis intentos hasta ahora incluyen:

• Una primera búsqueda de ancho que rastreó todos los ciclos únicos de longitud tres. Esto me pareció una buena idea, pero no pude hacerlo funcional
• Un bucle sobre todos los nodos en el gráfico para ver si tres vértices comparten un borde. Esto es demasiado lento para los conjuntos de datos más grandes. O (n ^ 3).

El algoritmo en sí es parte del cálculo del coeficiente de agrupamiento.

Answer 1

Como se cita aquí: https://math.stackexchange.com/a/117030

El algoritmo más rápido conocido para encontrar y contar triángulos se basa en el producto de matriz rápida y tiene una complejidad de tiempo O (nω), donde ω <2.376 es el exponente de producto de matriz rápida. Sin embargo, este enfoque lleva a una complejidad de espacio θ (n2).

Answer 2

Depende de cómo se representan tus gráficos.

Si tiene una matriz de adyacencia A, el número de triángulos debe ser tr (A ^ 3) / 6, en otras palabras, 1/6 veces la suma de los elementos diagonales (la división se ocupa de la orientación y la rotación).

SI tiene listas de adyacencia solo comience en cada nodo y realice una búsqueda de profundidad-3. Cuente con qué frecuencia alcanza ese nodo -> divida por 6 nuevamente.

Answer 3

El recuento de triángulos es de hecho difícil y computacionalmente costoso. Tal vez este sea un buen punto de partida para entender por qué: Contaje de triángulos eficiente en gráficos grandes a través de particiones de vértices basadas en grados .

El ciclo apropiado debería verificar para cada uno de los n nodos contra cada uno de sus vecinos (n * (n-1)) y continuar el ciclo para ver si el vecino del vecino de n es n: (n * (n-1)) (n- 1) (n-1), que es casi 10 ^ 16 para 10000 n. Con un millón de nodos estos bucles se vuelven tontos, pero para tu 10000 no deberías tener ningún problema si quieres usar la fuerza bruta :)

Usted mencionó que codifica en C #, y el gráfico (que está disponible para C) tiene un algoritmo excelente para contar triángulos escritos por Gabor Csardi. Contó 1.3 millones de triángulos en mi gráfico aleatorio de 10000 nodos y un millón de bordes en 1.3 segundos en una computadora portátil de cinco años :) Gabor Csardi sería el tipo que preguntaría :)

En términos de diferentes enfoques programáticos, tal vez debería mirar los datos en los que almacena su red. Si se almacena en una matriz de adyacencia, el número de bucles es fijo, pero en una lista de bordes de una red de tres aristas, el número de bucles es un múltiplo de tres, independientemente del número de bucles. Puede preguntar a la lista de bordes de los vecinos de un nodo sin tener que probar cada combinación de i-> j.

Escribí un guión pedagógico en R para ilustrar los enfoques y medir la velocidad de los diferentes algoritmos de una manera muy básica. Hay muchos problemas de velocidad inherentes al uso de R aquí (la versión de la lista de bordes está completamente saturada por demasiados bordes), pero creo que el ejemplo del código debería hacer que fluyan algunas ideas sobre cómo pensar acerca de la velocidad de la velocidad bruta. forzando recuentos de triángulos. Esto está en R, y no extremadamente limpio, pero bien comentado. Espero que puedas romper la barrera del idioma.

Todo lo mejor.

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

Answer 4

Este problema es tan difícil como la multiplicación de la matriz. Ver esto para reference .

¿Sabes algo sobre los gráficos? ¿Están dispersos? Si no, no creo que vayas a hacer mucho mejor que O (n ^ 3).

Answer 5

Necesitará una primera búsqueda de profundidad. El algoritmo será:

1) Para el nodo actual, pregunte todos los nodos adyacentes no visitados

2) para cada uno de esos nodos ejecute la profundidad dos, compruebe si un nodo en la profundidad 2 es su nodo actual desde el paso uno

3) marcar el nodo actual como visitado

4) haga que cada nodo adyacente no visitado sea su nodo actual (1 por 1) y ejecute el mismo algoritmo

Answer 6

Si no te importa la cantidad exacta de triángulos, existe un algoritmo de transmisión muy simple que proporciona un estimador insesgado. Ver por ejemplo here para una explicación.