6.1 Modèles exponentiels de graphes aléatoires

Il s’agit d’un modèle qui s’inspire naturellement de la famille de modèles exponentiels.

Definition 6.1 Soit \(n\ge 1\) un entier. On note \(\mathcal{A}_n\) l’ensemble des matrices d’adjacence binaires (symétriques ou non) de taille \(n\times n\) et pour tout \(A\in \mathcal{A}_n\), soit \(S(A)\in \mathbb{R}^p\) un vecteur de statistiques du graphe associé. Le modèle exponentiel de graphe associé au vecteur de statistiques \(S\) et noté ERGM(\(S\)) est défini par la famille de lois de probabilités \(\{\mathbb P_\theta\}_{\theta\in \mathbb R^p}\) définies sur l’ensemble \(\mathcal{A}_n\) par \[ \forall \theta \in \mathbb R^p, \forall A\in \mathcal{A}_n, \quad \mathbb P_\theta(A) = \frac 1 {c(\theta)} \exp\Big(\theta^\intercal S(A)\Big), \] avec \(c(\theta)=\sum_{A\in \mathcal{A}_n} \exp(\theta^\intercal S(A))\) une constante de normalisation.

Dans ce modèle, \(S(A)\) devient automatiquement un vecteur de statistiques exhaustives du modèle. Tous les graphes ayant la même valeur observée de \(S\) ont la même probabilité d’occurrence sour ERGM(\(S\)). En pratique, \(S(A)\) peut contenir le nombre d’arêtes, de triangles, de \(k\)-stars, \(\dots\) ou encore des covariables du modèle.

Dans la suite, on utilise des notations de graphe non dirigé mais tout est généralisable au cas des graphes dirigés.

Exemple.

Soit \(S_0(A)=vec(A)=vec((A_{ij})_{1\le i<j\le n})\) alors le ERGM(\(S_0\)) correspondant vérifie \[ \mathbb P_\theta(A)\propto \exp\left\{\sum_{i<j}\theta_{ij}A_{ij}\right\} , \] où \(\propto\) signifie ‘proportionnel à’.
C’est un modèle de variables aléatoires \(A_{ij}\) indépendantes non identiquement distribuées avec \(A_{i,j} \sim \mathcal{B}(p_{ij})\) et \(p_{ij}=\exp(\theta_{ij})/(1+\exp(\theta_{ij}))\). C’est un modèle qui a autant de paramètres que d’observations, donc pas très pratique.

Si on impose la contrainte \(\theta_{ij}=\theta\) pour tout \(i,j\), alors on obtient le modèle d’Erdös-Rényi \[ \mathbb P_\theta(A)\propto \exp(\theta S_1(A)), \] où \(S_1(A)=\sum_{i,j}A_{ij}\) est le nombre d’arêtes du modèle et \(\hat p =S_1(A)/[n(n-1)/2]\).

Si \(S(A)= (S_1(A),S_2(A))\) avec \(S_1\) comme ci-dessus et \(S_2(A)=\sum_{i,j,k} A_{ij}A_{ik}\) alors les variables \((A_{ij})_{i<j}\) sont non indépendantes et on n’a pas d’expression analytique pour l’EMV.

Soit \(k\ge 1\) et \(S_k(A)\) le nombre de \(k\)-stars du graphe \(A\) et \(T(A)=\sum_{ijk}A_{ij}A_{ik}A_{jk}\) le nombre de triangles. Dans les Markov random graph, on utilise \(S=(S_1,\dots, S_{n-1},T)\). En pratique, aller jusque \(k=n-1\) est beaucoup trop grand et on se contente de \(k\ll n-1\) pour la plupart des ERGM courants. On remarque que le nombre de \(k\)-étoiles \(S_k\) correspond au nombre de noeuds de degré au moins \(k\). Connaitre la suite \(S_1,\dots,S_{n-1}\) est équivalent à connaitre le nombre de noeuds à degré \(l\) pour \(0\le l\le n-1\), autrement dit, on connait la suite de degré des noeuds.

Problèmes du ERGM.

• La constante \(c(\theta)\) n’est pas calculable. Les méthodes d’estimation sont basées sur des méthodes MCMC avec par exemple un échantillonneur de Gibbs pour supprimer le problème de la constante inconnue.

• La maximisation de la vraisemblance reste un problème difficile, et en fait mal posé: ces modèles sont souvent ‘dégénérés’ au sens où cette loi concentre sa masse sur le graphe complet ou le graphe vide, ou un mélange des deux. Voir Chatterjee and Diaconis (2013), Schweinberger and Handcock (2015) pour plus de détails.

Dans ce cours, je déconseille fortement l’usage des ERGMs.

References

Chatterjee, Sourav, and Persi Diaconis. 2013. “Estimating and Understanding Exponential Random Graph Models.” The Annals of Statistics 41 (5): 2428–61.

Schweinberger, Michael, and Mark S. Handcock. 2015. “Local Dependence in Random Graph Models: Characterization, Properties and Statistical Inference.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 77 (3): 647–76.