Qu'est ce qu'un algorithme efficace pour compter le nombre de triangles dans un graphique?

vous aurez besoin de la première recherche de profondeur. L'algorithme sera:

1) pour le noeud courant, demander à tous les noeuds adjacents non visités

2) pour chacun de ces noeuds, Lancez depth two, vérifiez si un noeud de depth 2 est votre noeud actuel de l'étape 1

3) marque nœud visité

4) sur chaque non visités nœud adjacent votre noeud en cours (1 par 1) et exécutent le même algorithme

Dépend de la façon dont vos graphiques sont représentés.

si vous avez une matrice de contiguïté A le nombre de triangles doit être tr(a^3)/6, en d'autres termes, 1/6 fois la somme des éléments diagonaux (la division prend soin de l'orientation et de la rotation).

si vous avez des listes de contiguïté, commencez à chaque noeud et effectuez une recherche en profondeur-3. Comptez combien de fois vous atteignez ce noeud -> divisez par 6 encore.

le comptage en Triangle est en effet difficile et coûteux sur le plan informatique. C'est peut-être un bon point de départ pour comprendre pourquoi: comptage en Triangle efficace dans les grands graphes par le biais d'un partitionnement de Vertex basé sur le degré.

la boucle appropriée devrait vérifier pour chacun des noeuds n par rapport à chacun de leurs voisins (n*(n-1)) et continuer le cycle pour voir si les voisins du voisin de n sont n: (n*(n-1))(n-1)(N-1), ce qui est presque 10^16 pour 10000 N. Avec un million noeuds ces boucles deviennent stupides, mais pour vos 10000 vous ne devriez pas avoir de problème du tout si vous voulez la forcer:)

Vous avez mentionné que vous codez en C#, et graph (qui est disponible pour C) a un excellent algorithme pour compter les triangles écrit par Gabor Csardi. Il a compté 1,3 millions de triangles dans mon graphique aléatoire de 10000 noeuds et un million de bords en 1,3 secondes sur un ordinateur portable de cinq ans :) Gabor Csardi serait le gars à demander :)

en termes de différences approches programmatiques, peut-être que vous devriez regarder les données dans lesquelles vous stockez votre réseau. S'il est stocké dans une matrice de contiguïté, le nombre de boucles est fixe, mais dans une liste d'un réseau de trois arêtes, le nombre de boucles est un multiple de trois indépendants du nombre de nœuds. Vous pouvez demander la liste des bordures pour les voisins d'un noeud sans avoir à tester chaque combinaison de i - >J.

j'ai écrit un scénario pédagogique en R pour illustrer les approches et mesurer les différentes la vitesse des algorithmes est très basique. Il y a beaucoup de problèmes de vitesse inhérents à L'utilisation de R ici (la version de bord-liste est complètement submergée par trop de bords), mais je pense que l'exemple de code devrait faire couler quelques idées sur la façon de penser à la vitesse de brute-forçant triangle-compte. C'est en R, et pas très soigné, mais bien commenté. J'espère que vous pouvez briser la barrière de la langue.

Tout le meilleur.

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

si vous ne vous souciez pas du nombre exact de triangles, il y a un algorithme de streaming très simple qui fournit un estimateur non biaisé. Voir, par exemple,ici pour une explication.

tel que cité ici:https://math.stackexchange.com/a/117030

l'algorithme le plus rapide connu pour trouver et compter les triangles s'appuie sur le produit de matrice rapide et a une complexité de temps O(nw), Où ω<2.376 est l'exposant de produit de matrice rapide. Cette approche conduit toutefois à une complexité de l'espace θ(n2).