3.4 TP – Modèle de loi de puissance des degrés

Dans ce TP nous allons mettre en oeuvre les différents algorithmes pour simuler un graphe dont la suite de degrés suit une loi de puissance.

Fixons d’abord les paramètres :

gamma <- 2.5    
n <- 150

On calcule les probabilités élémentaires de la loi de puissance :

prob.puissance <- (1:(n-1))^(-gamma)
prob.puissance <- prob.puissance/sum(prob.puissance)

Notons que la loi de puissance n’admet pas de degré nul, et \(n-1\) est le nombre maximal de voisins dans un graphe d’ordre \(n\).

On simule une suite de degrés en tirant \(n\) degrés dans \(\{1,\dots,n-1\}\) avec les probabilités données par prob.puissance :

degs <- sample(1:(n-1), size=n, replace=TRUE, prob=prob.puissance)

Notons que pour la fonction sample() il n’est pas indispensable que le vecteur prob.puissance est normalisé.

Comme la somme des degrés de noeuds est toujours un nombre pair, on fait \(+1\) pour un noeud si nécessaire

sum(degs)
## [1] 341
degs[7] <- degs[1] + 1

La fonction is_degseq() d’igraph vérifie si la suite est une suite de degrés de noeuds possible. Mais l’aide n’est pas très claire, et on ne sait pas très bien ce que fait cette fonction. A priori elle devrait vérifier la condition d’Erdös-Gallai, mais ça ne doit pas être exactement ce qu’elle vérifie puisque is_degseq() fonctionne aussi pour des graphes avec des boucles.

is_degseq(degs)
## [1] TRUE

Si la réponse est FALSE, il faut générer une nouvelle suite de degrés. Si elle est TRUE on continue et on simule un graphe qui a cette suite de degrés à l’aide de la fonction sample_degseq() :

graph.power <- sample_degseq(degs, method="vl")

Cela ne marche pas toujours. Cela est probablement dû à un problème algorithmique lié à la méthode vl pour simuler un graphe de séquence donné. C’est un problème difficile !

Typiquement, il faut simuler plein de suite de degrés afin d’obtenir un résultat positif.

Exercice 1

  1. Ecrire une fonction de simulation de graphe du modèle de loi de puissance des degrés qui prend en entrée l’ordre \(n\) du graphe et l’exposant \(\gamma\) de la loi de puissance.
  2. Utilisez la fonction fit_power_law pour ajuster une loi de puissance sur le graphe simulé. Faites une représentation graphique de la suite de degrés du graphe simulé et superposer la loi de puissance ajustée. Que constatez vous ?
  3. Faites de même pour un de vos graphes réels : ajuster une lois de puissance aux degrés observés et tracer le diagramme en bâtons correspondant. Interprétez le résultat.

Exercice 2

  1. Ecrivez deux fonctions de simulation de graphes sous le modèle à degrés fixés avec les algorithmes de matching et de re-branchement.
  2. Reprenez un de vos exemples réels : utilisez les deux fonctions pour générer des graphes qui ont la même suite de degrés que votre graphe réel. On pourra comparer le nombre de triangles dans les deux graphes. Commentez.
  3. Pour tester si un graphe observé est une réalisation d’un graphe \(F\!D\), on peut analyser le nombre d’occurrences du triangle dans le modèle \(F\!D\) et le comparer au nombre de triangles observé. Ceci est fait par des simulations de Monte-Carlo. Plus précisément, on génère un grand nombre de graphes ayant la même suite de degrés et on compte le nombre de triangles pour chacun d’eux. Pour générer ces graphes, est-il raisonnable d’utiliser les algorithmes de matching et de re-branchement que vous avez codé ? Si non utilisez directement le package igraph. Tracez un histogramme de cette distribution. Que pensez-vous de la valeur observée dans votre graphe réel?