Pour anonymiser des routages, des algorithmes construisent des arbres aléatoires sur un ensemble de n noeuds. Pour etre difficile à casser, l'idée est de générer des arbres aléatoires uniformément parmi tous les arbres possible couvrant les n noeuds
L'objectif de ce sujet est d'evaluer la complexité du routage sur une telle construction aléatoire
Pour générer aléatoirement un arbre de noeuds N, on utilise le codage de PRUFER qui creer un arbre à partir d'une séquence de mots:
1) on construit une séquence des prufer(ps) de taille N-2 qui suit la loi uniforme avec la fonction “Sample()”.
2) on affecte une dégrée de 1 à chaque noeuds.
3) pour les noeuds qui apparaissent dans la sequence, on incremente son dégrée par un.
4) pour chaque noeuds dans ps, on cherche le plus petit noeud m qui a une dégrée de 1, ajouter une arete de m vers j dont son dégrée = 1, decrementer le dégrée de ces 2 derniers par 1, puis on reboucle avec le prochain m dans ps.
5) enfin des boucles dans 4), il restera 2 noeuds de degrée 1. on ajoute un arete entre ces 2.
library(igraph)
set.seed(10)
N <- 10
s = N - 2
T <- graph.empty(N, directed = FALSE)
# prufer sequence(ps)
ps <- sample(1:N, s, replace = TRUE)
degree = c()
for (i in 1:N) {
degree[i] = 1
}
for (i in 1:s) {
degree[ps[i]] = degree[ps[i]] + 1
}
for (i in 1:s) {
for (j in 1:N) {
if (degree[j] == 1) {
T <- add.edges(T, c(ps[i], j))
degree[ps[i]] = degree[ps[i]] - 1
degree[j] = degree[j] - 1
break
}
}
}
u = 0
v = 0
for (i in 1:N) {
if (degree[i] == 1) {
if (u == 0) {
u = i
} else v = i
}
}
T <- add.edges(T, c(u, v))
degree[u] <- degree[u] - 1
degree[v] <- degree[v] - 1
plot(T)
Remarque : Nous avons fait un set.seed(10) sur le generateur aléatoire
Dans l'exemple, on a defini le nombre de noeuds N = 10, donc la taille de sequence = 8.
Etant donné que la codage de prufer permet de représenter un arbre numéroté de n sommets avec une suite P de n-2 termes. Une suite P donnée correspond à un et un seul arbre numéroté de 1 à n.
En général, pour chaque terme de la liste, la probabilité de ps[i]=i est 1/N sur la loi uniforme, donc il y a N-2 nombres dans ce liste, la probabilité de génération deux même arbres est 1/nn-2. c'est à dire N noeuds peuvent générer nn-2 arbres differents.
Par la théorème de “Formule de Cayley”, on sait que “Le nombre d'arbres que l'on peut construire sur n sommets numérotés, avec n > 1 est égal à nn-2.” C'est bien égale à notre algorithme.
En conclusion, la génération de notre arbre est bien sur la loi uniforme.
Tree <- function(N) {
s = N - 2
T <- graph.empty(N, directed = FALSE)
# prufer sequence(ps)
ps <- sample(1:N, s, replace = TRUE)
degree = c()
for (i in 1:N) {
degree[i] = 1
}
for (i in 1:s) {
degree[ps[i]] = degree[ps[i]] + 1
}
for (i in 1:s) {
for (j in 1:N) {
if (degree[j] == 1) {
T <- add.edges(T, c(ps[i], j))
degree[ps[i]] = degree[ps[i]] - 1
degree[j] = degree[j] - 1
break
}
}
}
u = 0
v = 0
for (i in 1:N) {
if (degree[i] == 1) {
if (u == 0) {
u = i
} else v = i
}
}
T <- add.edges(T, c(u, v))
degree[u] <- degree[u] - 1
degree[v] <- degree[v] - 1
# plot(T)
diam <- diameter(T)
}
statDiam <- function(n, nbtest) {
nbdiam <- c()
for (i in 1:nbtest) {
nbdiam[i] <- Tree(n)
}
nbdiam
}
hist(statDiam(10, 100))
hist(statDiam(100, 100))
hist(statDiam(1000, 100))
On a bien testé le 3 situations 200 fois chaqun. Etant donné que N sommets peuvent générer nn-2 arbres différents selon la loi uniforme, il y a des arbres isomorphes et non-isomorphes dans ce nn-2 arbres, pour les arbres isomorphes, le diamètre est pareil, et pour les arbres non-isomorphes, certains des arbres non-isomorphes ont la même diamètre.
Par example : Quand N = 5
Il y a 125 arbres différrents et 3 arbres non-isomorphes existants. On peut bien trouver que le nombre de arbres qui ont le Diamètre = 2 est 5(N) ; Diamètre = 3 est 60 (4!*5) ; Diamètre = 4 est 60 (5!).
Quand N = 6
Il existe 1296 arbres différents et 6 arbres non-isomorphes, mais il y a deux arbres non-isomorphes ont diamètre=3 et deux autres ont diamètre=4, les nombre des arbres qui ont diamètre 2 et 5 sont beaucoup moins que les devants. C'est pourquoi les histogrames affichent comme ça. On n'a pas trouvé un bon algorithme pour calculer le nombre des arbres isomorphes, sinon on peut calculer la probabilité de chaque diamètre pour N directement.
Pour l'hauteur d'un arbre binaire généré uniformément:
height(tree) = 1 + max(height(tree.left), height(tree.right)) ≈ sqrt(n)
nbtest <- 100
proba <- 0.95
nbsom <- c(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
moyen <- c()
intervalle <- c()
for (i in 1:10) {
res <- statDiam(nbsom[i], nbtest)
variance <- var(res)
DL <- nbtest - 1
m <- qt(proba, DL)
moyen[i] <- mean(res)
intervalle[i] <- m * sqrt(variance/nbtest)
}
plot(nbsom, moyen, type = "l", col = "blue", ylim = c(1, 30))
lines(nbsom, (moyen - intervalle), col = "red")
lines(nbsom, (moyen + intervalle), col = "red")
lines(nbsom, sqrt(nbsom), col = "green")
La courbe bleu : Le diamètre moyen d'un arbre avec n sommet
Les courbes rouges: L'intervalle de confiance.
La courbe verte : La hauteur moyenne d'un arbre binaire avec n sommet
Evidemment, l'arbre généré par prufer voir est mieux que celle des arbres binaires dans le cadre d'un routage anonyme.