DM2 Sujet 2 : Communication dans une grille non fiable

Question 1 - Algorithme de génération :

library(ggplot2)
set.seed(1234)
link = function(p){
  runif(1)<p
}
bigRow = function(N,p,i){
  gap1 = N-2
  gap2 = N^2-N
  c(F,i%%N!=0 && link(p),logical(gap1),i<=N*(N-1) && link(p),logical(gap2))
}
newGrid = function(N,p){
  PsR = logical()
  for(i in 1:(N^2-1))
    PsR = c(PsR,bigRow(N,p,i))
  A = matrix(data = c(PsR,F), nrow = N^2)
  A | t(A)
}

Question 2 - Connectivité : Mon intuition serait d’avoir un “plateau” pour le nombre de noeuds connectés au-delà d’une certaine probabilité p, à cause de la présence de plus en plus de liens redondants ne permettant pas de connecter plus de noeuds. On aurait donc une probabilité qu’un lien connecte un nouveau noeud qui descend plus le nombre de noeuds déjà connectés augmente. On étudiera le cas d’une grille de 21x21, soit [-10,10]x[-10,10], donc possédant 441 noeuds.

simulation = function(n,p){
  N = 2*n+1
  A = newGrid(N,p)
  stp = c(logical((N^2)%/%2),c(T,logical((N^2)%/%2)))
  connected = stp
  connectedCount = sum(connected)
  oldCount = 0
  while(connectedCount!=oldCount){
    oldCount = connectedCount
    stp = as.vector((A %*% stp) != 0)
    connected = connected | stp
    connectedCount = sum(connected)
  }
  connectedCount 
}

n = 10
netSize = numeric()
prob = double()
for(i in 0:25)
  for(k in 0:50){
    netSize = c(netSize,simulation(n,0.04*i))
    prob = c(prob,0.04*i)
  }
df = data.frame(netSize, prob)
ggplot(df, aes(prob,netSize)) +
  geom_point() + geom_smooth()

On obtient bien un plateau à partir d’une probabilité p assez grande, mais aussi un plateau pour un faible probabilité, car si la probabilité d’un lien est inférieure à 0.25, on aura un nombre moyen de lien partant de l’origine inférieur à 1, ce qui réduit fortement la possibilité d’avoir un réseau étendu.