0% ont trouvé ce document utile (0 vote)

52 vues54 pages

Analyse statistique des graphes

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

52 vues54 pages

Analyse statistique des graphes

Transféré par

nay851875

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Notes de cours : Analyse statistique de graphes

M2 Université Pierre et Marie Curie

Catherine Matias

Warning : ce document contient certainement des erreurs et des imprécisions.

N’hésitez pas à me les signaler.

1
Table des matières

1 Introduction aux graphes 4

1.1 Les réseaux / Les graphes . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Représentation visuelle . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Stockage informatique . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Les matrices d’adjacence . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Les listes d’arêtes . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Le modèle G(n, p) et graphes remarquables . . . . . . . . . . . . . . . 9

2 Statistiques descriptives sur les graphes 11

2.1 Degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Distribution marginale des degrés . . . . . . . . . . . . . . . . 11
2.1.2 Modèles de configuration . . . . . . . . . . . . . . . . . . . . . 12
2.1.3 Corrélations entre degrés . . . . . . . . . . . . . . . . . . . . . 14
2.2 Densité, clustering, transitivité . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Motifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Distance, diamètre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Autres descripteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Échantillonnage dans les graphes . . . . . . . . . . . . . . . . . . . . 19
2.6.1 Exemples d’échantillonnages dans les graphes . . . . . . . . . 19
2.6.2 Exemple d’impact de l’échantillonnage : estimation des degrés 21

3 Spectral Clustering : détection de communautés 22

3.1 Graphes de similarité . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Différents graphes de similarité . . . . . . . . . . . . . . . . . 23
3.2 Matrices laplaciennes de graphe . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Laplacien non normalisé . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Laplaciens normalisés . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Algorithmes de clustering spectral . . . . . . . . . . . . . . . . . . . . 29

2
3.4 Exemples jouets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Commentaires pratiques . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Modèles de graphes aléatoires et classification des nœuds 34

4.1 Deux modèles de graphes (sans liens avec la classification) . . . . . . 34
4.1.1 Les modèles exponentiels de graphes aléatoires . . . . . . . . . 34
4.1.2 Attachement préférentiel . . . . . . . . . . . . . . . . . . . . . 36
4.2 Généralités sur les modèles à variables latentes . . . . . . . . . . . . . 36
4.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.2 Estimation des paramètres . . . . . . . . . . . . . . . . . . . . 37
4.3 Espaces latents continus (pour graphes binaires) . . . . . . . . . . . . 39
4.3.1 Modèle à positions latentes et al. . . . . . . . . . . . . . . . . 39
4.3.2 Version classifiante du modèle . . . . . . . . . . . . . . . . . . 40
4.3.3 Choix de la dimension de l’espace latent . . . . . . . . . . . . 40
4.4 Espaces latents discrets : Modèles à blocs stochastiques (stochastic
block model) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4.1 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4.2 L’algorithme EM . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4.3 Estimation des paramètres par approximation variationnelle
de EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4.4 Sélection de modèles . . . . . . . . . . . . . . . . . . . . . . . 51

3
Chapitre 1

Introduction aux graphes

Quelques références bibliographiques (ces notes en font un usage immodéré)

• Générales : Kolaczyk (2009); Kolaczyk and Csárdi (2014) ;

• Chapitres 1 et 2 : Albert and Barabási (2002) ;

• Chapitre 3 sur le spectral clustering : von Luxburg (2007).

1.1 Les réseaux / Les graphes

Définition. Réseau = ensemble d’entités en interaction versus graphe = représentation
mathématique du réseau.

Exemple de réseaux ’physiques’. Internet (routeurs et ordinateurs connectés par

des câbles ethernet ou des liaisons wifi) ; réseau électrique ; réseau routier ; réseau
aérien ; . . .
Exemple de réseaux virtuels. World wide web (nœuds sont les pages html et les
arêtes sont les hyperliens) ; réseau d’amis Facebook ; réseau de co-publications de
chercheurs ; food-web en écologie ; . . .

Dans la suite, on s’intéresse uniquement aux graphes simples : un ensemble de

nœuds (ou sommets), liés par des arêtes (ou arcs), sans liens doubles ni boucles.

Vocabulaire. Un graphe G = (V, E) est composé d’un ensemble V = {1, . . . , n}

de nœuds (vertices en anglais) et d’un ensemble E d’arêtes (edges en anglais) avec
{i, j} ∈ E s’il y a une arête entre les nœuds i et j dans le graphe. On dit que l’arête
e = {i, j} ∈ E est issue de i (ou de j).
Le nombre de nœuds n est l’ordre du graphe tandis que son nombre d’arêtes |E| est
appelé taille du graphe.

4
Un graphe est dirigé (ou orienté) lorsque ses arêtes le sont i.e. lorsque l’arête (i, j)
est différente de l’arête (j, i). Il est non dirigé sinon.
Les graphes simples n’ont pas de boucles (i.e. (i, i) n’est jamais une arête). Ils
peuvent être binaires : une arête est présente (1) ou absente (0), ou valués : les
arêtes présentes sont alors munies d’une valeur (poids). Noter qu’un graphe binaire
est un cas particulier de graphe valué où toutes les arêtes présentes ont le poids 1.
Remarques. • Un graphe simple sur n nœuds possède au plus n(n − 1)/2

arêtes s’il est non dirigé et n(n − 1) arêtes s’il est dirigé.
• Les graphes biparties sont tels que V = V1 ∪ V2 avec V1 ∩ V2 = ∅ et les arêtes

e = {u, v} ∈ E sont telles que u ∈ V1 , v ∈ V2 . Tout ce qui suit se généralise

facilement à ce cas. Les graphes simples que l’on considère ici sont parfois
dits uniparties.
À partir de mesures d’interactions {Cij }1≤i,j≤n entre individus, on peut définir
une valeur symétrisée et normalisée des interactions à partir du coefficient de Jac-
card.
Définition. (Jaccard coefficient ou index de Jaccard). Il s’agit d’une mesure de
similarité symétrique et normalisée entre éléments, définie à partir de valeurs d’in-
teractions Cij entre les individus, par
Cij + Cji
JACij = JACji = P P .
k6=j Cik + k6=i Cjk

Cet index sert parfois à construire des graphes valués et non dirigés entre un
ensemble d’entités.
Définition (Chemins, connexité, cycles). Un chemin dans G = (V, E) (non orienté)
entre i, j ∈ V est une suite d’arêtes e1 , . . . , ek ∈ E telle que
• pour tout 1 ≤ t ≤ k − 1, les arêtes et et et+1 partagent un nœud dans V ;

• e1 est issue de i ;

• et est issue de j.

Un cycle est un chemin d’un nœud i à lui même (dans G).

Une composante connexe de G = (V, E) est un sous-ensemble C = {v1 , . . . , vk } ⊂ V
tel que pour tous vi , vj ∈ C, il existe un chemin dans G de vi à vj .
Un graphe G = (V, E) est dit connexe s’il possède une unique composante connexe
(i.e. pour tous i, j ∈ V , il existe un chemin de i à j dans G).
Remarques. • Dans un graphe orienté, on peut définir la notion de chemin

orienté entre i et j. Il se peut alors qu’il existe un chemin orienté de i vers j

sans chemin orienté de j vers i. De même il peut exister un chemin de i vers
j sans chemin orient de i vers j.

5
• La connexité d’un graphe dirigé est définie à partir des chemins non dirigés.

Proposition 1.1. Tout graphe peut être décomposé en un unique ensemble de com-
posantes connexes (maximales). Le nombre de composantes connexes d’un graphe
est supérieur ou égal à n − |E|.

Preuve. On vérifie facilement que si |E| = 0 alors il y a n composantes connexes.

De même si |E| = 1 on a exactement n − 1 composantes connexes. Par induction sur
le nombre d’arêtes : supposons que G = (V, E) est un graphe avec c composantes
connexes tel que c ≥ n − |E|. On ajoute une arête à G pour fabriquer G0 = (V, E 0 ) et
on note c0 le nombre de composantes connexes de G0 . Alors soit c0 = c (l’arête ajoutée
relie deux nœuds qui sont déjà dans la même composante connexe), soit c0 = c − 1
(l’arête ajoutée relie deux composantes connexes entre elles pour n’en créer plus
qu’une). Dans le premier cas on a c0 = c ≥ n − |E| ≥ n − |E| − 1 = n − |E 0 |. Dans
le second cas, on a c0 = c − 1 ≥ n − |E| − 1 = n − (|E| + 1) = n − |E 0 |. La relation
est toujours vérifiée.

Définition (Voisinage, degrés). Les voisins de i ∈ V sont les nœuds j ∈ V tels que
{i, j} ∈ E. On note
V(i) = {j ∈ V ; {i, j} ∈ E}.
Le degré di d’un nœud i du graphe G est le nombre de voisins de i dans G. C’est
donc le cardinal |V(i)| du voisinage de i dans G.
Si G est un graphe dirigé, on peut définir le degré sortant dout
i et le degré entrant
in
di du nœud i.
Le degré moyen d’un graphe est défini par
1 X
d¯ = di .
|V | i∈V

Dans un graphe orienté, les degrés moyens sortants et entrants sont nécessairement
égaux
1 X in 1 X out
d¯in := di = d¯out := d .
|V | i∈V |V | i∈V i
P
Proposition 1.2. Dans un graphe G = (V, E) on a i∈V di = 2|E|. En particulier,
la somme des degrés d’un graphe est toujours paire.

Remarque. La suite des degrés (d1 , . . . , dn ) d’un graphe est très contrainte. En
fait Erdős and Gallai (1961) ont montré la propriété suivante (voir aussi Berge,
1976, Chapitre 6, Théorème 4). Quitte à ré-ordonner (d1 , . . . , dn ) de sorte que d1 ≥
d2 ≥ · · · ≥ dn , une condition nécessaire et suffisante pour que (d1 , . . . , dn ) soit la

6
réalisation de la séquence des degrés d’un graphe est que pour tout 1 ≤ k ≤ n − 1
on ait
X k Xn
di ≤ k(k − 1) + min(k, di ).
i=1 i=k+1

1.2 Représentation visuelle

On représente les nœuds et les arêtes sans accorder d’importance à la position
d’un nœud dans l’espace. Les nœuds ont des labels qui peuvent ou non être spécifiés
sur la représentation.
Attention, la représentation visuelle d’un graphe est très trompeuse ! Les exemples
de la Figure 1.1 sont tirés du livre Kolaczyk and Csárdi (2014).
La question de la visualisation et de la représentation d’un graphe est donc très
importante. Il faut garder à l’esprit que pour les grands graphes, la représentation
est toujours biaisée.
Remarque. Un graphe est dit planaire lorsque l’on peut le représenter dans le plan
sans qu’aucune arête n’en croise une autre. Dans ce cours, on ne s’intéresse pas à
cette propriété.

1.3 Stockage informatique

1.3.1 Les matrices d’adjacence
Définition. Un graphe G = (V, E) binaire sur un ensemble V = {1, . . . , n} de
nœuds peut-être représenté par sa matrice d’adjacence (binaire) A = (Aij )1≤i,j≤n
où
1 si {i, j} ∈ E,
Aij =
0 sinon.
Lorsque le graphe est non dirigé, la matrice A est symétrique. Si le graphe est simple
on pose Aii = 0 pour tout i. Si le graphe est valué, on peut considérer une matrice
d’adjacence valuée

wij si l’arête est présente entre i et j et de poids wij ,
Aij =
0 sinon.
Proposition 1.3. Les degrés s’obtiennent à partir de la matrice d’adjacence via des
sommes en ligne ou en colonne
X X X
di = Aij (cas non dirigé) ; dout
i = A ij ; d in
i = Aji .
j;j6=i j;j6=i j;j6=i

7
ching some of the springs and compressing
2 > title("5x5x5 others, upon being let go it will
Lattice")
er
n tohas5almost
its twice
state. as
> title("5x5x5
natural many edges
So-called 3 > asplot(aidsblog,
Lattice") the latter methods
spring-embedder (300 layout=layout.fru
of graph drawing de-
aer, is6by>of
notion definition
force forhighly
each uniform
plot(aidsblog, in>inthe
itsgraph
connectivity
vertex4layout=layout.circle)
title("Blogdepending, at the very least, on
Network")
og network is not.of vertices Network")
7 >oftitle("Blog
ositions pairs and the distances between them, and seek to iter-
as shown inarranged
Fig. 3.2, (usu-
we see that substantially more
cular the wherein
layout,
ly update placement theofvertices
verticesare until a vector of net forces across vertices
network is now
ircumference of a circle. The edges are then drawn visible.
erges.
outs
he of theoflattice
method and blog
Fruchterman networks
and Reingoldare shown
[60] in
is a commonly used example of
5x5x5 Lattice Blog Network
ype. Applied to the lattice and blog networks, 5x5x5 Lattice
ertex.size=3,
1 > plot(g.l, vertex.label=NA,
layout=layout.fruchterman.reingold)
e=0.5)
2 > title("5x5x5 Lattice")
))
3 > plot(aidsblog, layout=layout.fruchterman.reingold)
=layout.circle)
4 > title("Blog Network")
tice")
own in Fig. 3.2, we see that substantially more of the structure inherent to each
ayout=layout.circle)
ork is now visible.
ork")

5x5x5 Lattice Blog Network

Blog Network
Fig. 3.1 Circular layouts Fig. 3.2 Layouts using the method of Fruchterman and Rein

Alternatively, motivated by the fact that it is poss

The visualization of forces the lattice is much more pleasing to the eye
in spring systems with an overall system en
he blog network, largely to due to the layouts
generating low level of edge-crossings
is that of energy-placement throu
m
f the circle. Ordering of of the vertices
vertex positions, around the circle
ostensibly is defined is important
using exprew
f layout—a random re-ordering in physics. of the vertices
A vertex placement in the lattice,which
is chosen for exa
mi
ield a picture much more like thatsystem
A physical of thewith blogminimum
network.energy Common ver
is typica
.2 Layouts using the method of Fruchterman and Reingold
or circularFigurelayouts henceordering
include the assertion by here
degree is that
anda graph grouping drawnbyaccor
co
1.1 – Chaque ligne contient deux représentations différentes d’un même
beand
ttributes. réseau (tiré de Kolaczyk visually appealing.
Csárdi (2014)). 3
En haut : Cube {1, . . . , 5} , en bas un

Often more
lternatively,
réseau de blogs.
effective
motivated by the Methods
forfact that it based
creating isuseful ondrawings
possible multidimensional
to associate arethe scaling
layouts (MD
based
collection of
tice is much more withpleasing
anthe to the system
social eye than
network that of
literature, areand of this
snalogies
in springbetween
systems the relational
overall structure in graphs
energy, another thetype.
common Theam
forces
approach m
o the lowlayouts
nerating level of is edge-crossings
that One through
is a popular
of energy-placement the
variant. center
Using An
methods. thisenergy,
layout,as a function
n physical
vertices around
systems.
the circle is
approach
important
in
with
this
this
area,
type
and the earliest propo
rtex positions,
roduce ostensibly
attractive and is#3.5
defined
repulsive 1 >using
forces expressions
plot(g.l, by motivated
associating by those
vertices
layout=layout.kamada.k found
with ba
ng of the vertices in the lattice, for example, would
ysics. A vertex placement is chosen2 > which minimizes Lattice")
title("5x5x5
8 the total system energy.
that ofsystem
ysical the blog network.
with minimum Common3 > vertex
energy orderings
is typically
plot(aidsblog,in its most relaxed state, and
layout=layout.kam
edering by degree
the assertion hereand grouping
is that 4 by
a graph > common
title("Blog
drawn vertex
according toNetwork")
similar principles should
sually appealing.
ating useful
ethods baseddrawings are layouts based
on multidimensional on(MDS),
scaling exploiting
which have a long history in
Exemple . Reconstruire le graphe encodé par
 
0 1 1 0 0
1 0 1 1 0
 
A = 1 1 0 1 0 .
 
 
0 1 1 0 0
0 0 0 0 0

Remarque. Redondance de l’information dans le cas d’un graphe non dirigé (ma-
trice symétrique).

Il peut s’avérer que cette représentation ne soit pas adaptée au stockage infor-
matique
• si trop grand nombre de nœuds (matrice de taille n × n),

• si le graphe est très creux (on peut éventuellement utiliser des outils spécifiques

pour manipuler les matrices creuses).

1.3.2 Les listes d’arêtes

Lorsque la liste des nœuds est déjà connue, on peut se contenter de stocker les
arêtes du graphe. Attention, il est nécessaire d’indiquer le nombre total de nœuds
du graphe, sinon on ne connaı̂t pas les nœuds isolés.
Exemple . Reconstruire le graphe encodé comme indiqué ci-dessous
n = 5 et (1,2),(1,3),(2,3),(2,4),(3,4)
C’est le codage de loin le plus efficace !

1.4 Le modèle G(n, p) et graphes remarquables

Un modèle de graphes aléatoires est une collection (finie ou dénombrable) G de
graphes et une loi de probabilité P sur cette collection G.

Le modèle de graphe aléatoire le plus simple est le modèle introduit dans les
années 1950 par Erdös et Rényi. Il s’agit de la collection G(n, M ) de tous les graphes
simples non dirigés d’ordre n et de taille M , munie de la loi uniforme P sur cette
N

collection. Ainsi, la collection G(n, M ) contient M graphes différents, où N =
N

n(n − 1)/2 et la probabilité de chacun d’eux est 1/ M .
Une variante plus commune consiste à considérer la collection G(n, p) de graphes
simples non dirigés générés selon un modèle à deux paramètres : n le nombre de
nœuds du graphe et p ∈ (0, 1) la probabilité de connection de deux nœuds pris au

9
hasard. C’est un graphe dont toutes les arêtes Aij , 1 ≤ i < j ≤ n sont des variables
i.i.d. de loi de Bernoulli B(p).
Un réseau observé peut être considéré comme une réalisation de la variable
aléatoire G(n, p) ou de la variable G(n, M ) de loi comme ci-dessus.
Souvent, on considère que p = pn peut varier avec n. (Sinon on a des graphes
trop denses pour modéliser les grands graphes réels). Lorsque M ∼ n2 pn , les deux

modèles sont équivalents pour n grand.

C’est un modèle mathématique très étudié, mais qui s’ajuste mal aux réseaux
observés. Dans la suite, on décrira ses propriétés au regard de celles des réseaux
réels.

Simulation de graphes G(n, p). En principe, il suffit de générer n(n − 1)/2

variables aléatoires de Bernoulli de paramètre p. Lorsque n est grand et p = pn de
l’ordre de 1/n, cette procédure est très inefficace : l’espérance du degré d’un nœud
est finie et donc la plupart des variables valent 0.
Voir Kolaczyk (2009), section 6.2.3 pour une alternative en O(n + |E|) au lieu
de O(n2 ).

Définition. Le graphe complet (ou clique) Kn est le graphe (non dirigé) sur n
sommets qui contient toutes les arêtes possibles entre ces sommets.

Ainsi, K2 est une simple arête entre 2 nœuds, K3 est un triangle. Les sous-graphes
complets d’un graphe sont plus communément appelés cliques.

Définition. Un graphe dont tous les nœuds ont le même degré d est un graphe
régulier ou encore d-régulier.

Exemple de graphes réguliers. Grille Z2 , le graphe complet Kn est un graphe

(n − 1)-régulier.
Les graphes réels sont rarement réguliers.

10
Chapitre 2

Statistiques descriptives sur les

graphes

Les statistiques permettent de résumer l’information contenue dans un graphe,

de le décrire, d’en extraire ses caractéristiques. Elles sont une vision partielle du
graphe.
Dans ce chapitre, on présente des statistiques usuelles, ainsi que leurs propriétés
dans le cas du graphe aléatoire G(n, p). On verra ainsi pourquoi le modèle G(n, p)
s’ajuste mal aux réseaux observés. Au passage, on présente d’autres modèles pour
lesquels ces statistiques s’ajustent mieux aux observations.
Dans toute la suite, G est un graphe aléatoire.

2.1 Degrés
2.1.1 Distribution marginale des degrés
Rappel : pour un graphe simple binaire et non dirigé, le degré Di du nœud i
(pour i = 1, . . . , n) et le degré moyen D̄ du graphe vérifient la relation suivante
n n
X 1X 1 XX 2|E|
Di = Aij , et D̄ = Di = Aij = .
j6=i
n i=1 n i=1 j6=i n

Les degrés {Di }i=1,...,n des nœuds d’un graphe sont des variables aléatoires, non
indépendantes en général. On s’intéresse d’abord à la distribution marginale de ces
variables.
Notons tout d’abord que le degré moyen D̄ n’est pas une variable très informative
car dans les réseaux observés, les degrés des nœuds varient beaucoup. La distribu-
tion des degrés contient plus d’information que le degré moyen. Il faut cependant

11
garder en tête que des graphes très différents peuvent avoir la même distribution des
degrés des nœuds (voire la même suite des degrés observés !). De la même façon, si
les variables aléatoires D̄in et D̄out sont toujours égales entre elles, la suite des degrés
observés entrants (Diin )1≤i≤n et sortants (Diout )1≤i≤n peuvent être très différents.

Commençons par considérer le cas (facile) du graphe G(n, p). Dans le cas de
G(n, p), les variables Aij sont i.i.d. de loi B(p).
Proposition 2.1. Le degré Di du nœud i du graphe aléatoire G(n, p) vérifie
Di ∼ B(n − 1, p).
Par la loi des grands nombres, la variable D̄/(n − 1) converge vers E(Aij ) = p.
En particulier, l’espérance du degré d’un nœud vérifie E(Di ) = (n − 1)p = pn(1 +
o(1)) (lorsque n grand, p petit).
En pratique, la loi Binomiale est une loi à queue ’légères’ : on observe très peu
de valeurs extrêmes. Or dans les réseaux réels, la distribution des degrés est plus
communément ’à queue lourde’ : un petit nombre de nœuds ont un degré très fort
(les hubs).

Lorsque n → +∞ et p → 0 avec np → λ > 0 alors la loi B(n−1, p) est approchée

par une loi de Poisson P(λ). Là encore, ce n’est pas une distribution à queues lourdes.

Beaucoup de graphes réels ont une distribution des degrés des nœuds qui s’ajuste
correctement sur une loi de puissance, i.e.
c
fDi (k) := P(Di = k) = γ ,
k
où c est une constante de normalisation et γ > 0 est l’exposant de la loi puissance.
Dans les années 2000, beaucoup de publications se sont concentrées sur ce phénomène
de loi de puissance de la distribution des degrés, caractérisant par exemple l’expo-
sant de la loi de puissance de réseaux observés. Le mauvais ajustement du modèle
G(n, p) sur la loi des degrés a donné lieu à de nouveaux modèles, fondés uniquement
sur cette distribution des degrés. Ces modèles peuvent être vus comme des modèles
de graphe aléatoires (au sens d’Erdös-Rényi) généralisés : on défini une collection
de graphes et la loi uniforme sur tous les éléments de cette collection.

2.1.2 Modèles de configuration

On peut définir des modèles de graphes aléatoires en utilisant uniquement la
distribution des degrés des nœuds. Ainsi, on peut considérer les modèles suivants

12
1. Loi de puissance des degrés : On considère des graphes aléatoires sur n nœuds
tels que les variables aléatoires D1 , . . . , Dn sont i.i.d selon une loi de puissance
(pour un certain γ).
2. Modèle à degrés fixés : Soient d = (d1 , . . . , dn ) une suite (possible) de degrés
de nœuds et F D(d) la collection de tous les graphes sur n nœuds qui possèdent
exactement la suite des degrés d, munis de la probabilité uniforme.
3. Modèle à degrés variables : Soient d = (d1 , . . . , dn ) une suite (possible) de
degrés de nœuds et RD(d) le modèle de graphe aléatoire sur n nœuds tel que
toutes les arêtes Aij sont indépendantes, de loi B(pij ) avec pij = di dj /C où
C constante positive telle que 0 ≤ pij ≤ 1 (par exemple C = maxi6=j di dj ).
Dans le modèle F D(d), tous les graphes ont exactement la suite de degrés d.
Dans le modèle de loi de puissance, on commence par tirer une suite d de degrés
selon cette loi de puissance, puis on considère un graphe qui a cette suite de degrés
fixés. Enfin dans le modèle RD(d), les degrés sont seulement approchés par la suite
d. En effet dans ce cas
X X di X di (2|E| − di )
E(Di ) = E(Aij ) = pij = dj = .
j6=i j6=i
C j6=i C

En prenant di pas trop grand et C ' 2|E| on obtient E(Di ) ' di .

Remarques. • Le modèle de loi de puissance des degrés n’est pas constructif

ni simplement simulable : si on tire une suite de Di comme indiqué, on a peu

de chances que la réalisation satisfasse les conditions du théorème d’Erdös-
Gallai et donc soit réalisable en tant que suite de degrés d’un graphe.
• Par contre, lorsque l’on trace un histogramme des di observés et qu’on ajuste

une loi de puissance sur cette distribution empirique, on est bien en train de
travailler sous ce modèle !
• La simulation de graphes dans le modèle à degrés variables est directe puis-

qu’il suffit de tirer les Aij de façon indépendante (non identiquement dis-
tribués).
• Pour générer des graphes dans F D(d), on utilise soit un algorithme de mat-

ching (voir Algorithme 2.1) soit un algorithme re-branchement (rewiring ou

switching algorithm, voir Algorithme 2.2).
L’algorithme de matching ne crée pas nécessairement un graphe simple (avant le
test final, car possibilité de boucles et d’arcs multiples). Si le graphe produit n’est
pas simple, il doit être jeté et on en tire un nouveau. Algorithme très peu efficace !
Attention, une correction naı̈ve de cet algorithme, qui vérifie que i 6= j ou que
l’arête {i, j} n’existe pas encore peut soit ne pas converger, soit donner des tirages

13
Algorithm 2.1: Algorithme de matching
//Entrée : d = (d1 , . . . , dn )
//Sortie : liste d’arêtes
//Initialisation : Edge.List ← () ; Node.List ← ()
// Créer fake Node.List :
for i ∈ {1, . . . , n} do
while di ≥ 1 do
Node.list ← concatenate(Node.List,i)
di ← di − 1

// Créer Edge.List :
while Node.List is not empty do
Tirer i, j uniformément dans Node.List et sans remise
Edge.List ← concatenate(Edge.List, {i, j})

// Test graphe simple :

Si Edge.List contient des boucles ou des arêtes multiples, la sortie est non
valide. On recommence.

biaisés de l’ensemble des graphes possibles.

L’algorithme de re-branchement est plus efficace mais il fonctionne uniquement

à partir d’un graphe déjà existant qui possède la suite de degrés qu’on s’est fixée.
De plus, il nécessite un paramètre : le nombre d’itérations. Empiriquement, on fixe
ce nombre à environ 100 fois le nombre d’arêtes du graphe.
Le comportement du modèle F D(d) peut être étudié à l’aide de simulations
numériques (coûteuses).

Remarque. Il faut garder à l’esprit que les degrés des nœuds sont une caractérisation
très partielle du réseau et que des réseaux très différents peuvent avoir des suites de
degrés de nœuds très similaires.

2.1.3 Corrélations entre degrés

Jusqu’à présent, on a considéré la distribution du degré Di d’un nœud i. Mais
lorsque i, j sont voisins dans le graphe, les variables Di et Dj ne sont bien sûr pas
indépendantes a priori.
On cherche ici à répondre à la question : quels types de nœuds partagent une

14
Algorithm 2.2: Algorithme de re-branchement
//Entrée : Edge.List ; Nb.iter
//Sortie : Edge.List
while Nb.iter ≥ 1 do
Choisir e1 = {u1 , v1 } et e2 = {u2 , v2 } uniformément dans Edge.List
Proposer la création de e01 = {u1 , v2 }, e02 = {u2 , v1 }
Si aucune boucle ni arête multiple créée : remplacer e1 , e2 par e01 , e02
Nb.iter ← Nb.iter -1

arête ? Par exemple, les nœuds de fort degrés sont-ils reliés entre eux ou sont-ils
reliés à des nœuds de faible degré ?
On considère la distribution des variables (Di , Dj ) lorsque {i, j} ∈ E. Lorsque le
graphe est non dirigé, il faut faire attention car {i, j} et {j, i} représentent la même
arête.
Définition. (Distribution empirique de (Di , Dj ) pour {i, j} ∈ E). Soit G = (V, E)
un graphe non dirigé. Pour tout 1 ≤ k ≤ l, soit N (k, l) le nombre d’arêtes de
e = {i, j} ∈ E telles que di = k, dj = l ou di = l, dj = k. Alors la distribution
empirique de (Di , Dj ) pour {i, j} ∈ E ou fréquence de paire de degrés est donnée
par 
 N (k, l)/(2|E|) si k < l,
∀(k, l) ≥ 1, fkl = N (l, k)/(2|E|) si k > l,

N (kk)/|E| si k = l.
C’est une distribution symétrique.
Exemple de fréquence de paires de degrés.. Le graphe de la Figure 2.1 a
pour suite de degrés (4, 2, 3, 1, 0, 1, 1) soit une distribution empirique des degrés
f0 = 1/7, f1 = 3/7, f2 = f3 = f4 = 1/7. La fréquence empirique des paires de degrés
est donnée par f1,4 = f4,1 = 1/6, f1,3 = f3,1 = 1/12 = f2,3 = f3,2 = f4,2 = f2,4 =
f3,4 = f4,3 et tous les autres fk,l valent 0.
On peut représenter cette distribution par un carré de taille dmax où dmax =
max(di ) et la cellule (k, l) indique la valeur fk,l (en niveaux de couleur par exemple).

2.2 Densité, clustering, transitivité

Les amis de mes amis sont mes amis. L’organisation des réseaux en cliques ou
quasi-cliques est une caractéristique intéressante. Elle est capturée par les coefficients

15
5

1
7

Figure 2.1 – Exemple de graphe.

définis dans cette section. Comme pour les degrés, il s’agit de regarder l’environne-
ment local, en incluant cette fois les voisins à distance 2.

Définition. La densité d’un graphe G = (V, E) est définie par

|E| D̄
den(G) = = .
|V |(|V | − 1)/2 (|V | − 1)

Cette quantité, comprise entre 0 et 1, traduit à quel point le graphe G ressemble

ou pas à une clique. Il s’agit du degré moyen D̄ à constante multiplicative près.
On peut définir une densité locale en considérant un sous-graphe H ⊂ G. Un cas
intéressant est obtenu pour Hi , le sous-graphe induit construit à partir des voisins
d’un nœud i ∈ V , i.e. le sous-graphe Hi = (Vi , Ei ) où Vi est l’ensemble des voisins
de i dans G et Ei l’ensemble des arêtes {j, k} ∈ E telles que j, k ∈ Vi .

Définition. On note Di le degré du nœud i et |Ei | le nombre d’arêtes qui connectent

les voisins de i entre eux (i.e. Ei est l’ensemble des arêtes du sous-graphe construit sur
les voisins de i). On définit le coefficient Ci de clustering du nœud i et le coefficient
C̄ de clustering global par
(
2|Ei |
Di (Di −1)
si Di ≥ 2 1 X
Ci = , C̄ = Ci .
0 sinon |V | i∈V

On fixe un nœud i avec Di voisins. Si toutes les arêtes possibles entre ces voisins
existent, on obtient Di (Di − 1)/2 arêtes. Dans ce cas, le rapport 2Ei /Di (Di − 1)
vaut 1. Sinon, ce rapport est positif, mais inférieur à 1.
Ainsi, on a
0 ≤ C̄ ≤ 1,

16
avec C̄ = 0 ssi chaque nœud est tel qu’aucun de ses voisins ne sont reliés par une
arête (le graphe ne contient aucun triangle, mais peut contenir des cycles de longueur
supérieure ou égale à 4) et C̄ = 1 ssi deux arêtes adjacentes dans le graphe forment
toujours un triangle.
Le coefficient de clustering global est relié à la densité des triangles parmi les
paires de relations dans le graphe. Les triangles traduisent les relations de transiti-
vité : importance par exemple dans les réseaux sociaux, etc. On peut aussi mesurer
directement cette densité des triangles par le coefficient de transitivité.

Définition (transitivité). On définit le coefficient de transitivité par

] triangles
T = .
] triplets de nœuds connectés

Remarque. Dans la définition précédente, par triplet de nœuds connectés, on en-

tend un ensemble de 3 nœuds tels que le sous-graphe induit par ces 3 nœuds est
connexe. Pour un arbre, on a C̄ = 0 = T . Mais on peut avoir des petites valeurs de
C̄ ou T et contenir des cycles (donc ne pas être un arbre).

Dans G(n, p), puisque toutes les arêtes sont indépendantes, la probabilité que
deux voisins d’un nœud i soient connectés vaut p. Donc en moyenne, E(2|Ei | Di ) =
¯ En conséquence,
pDi (Di −1) ce qui donne E(Ci ) = p et E(C̄) = p ' E(Di )/n ' d/n.
dans G(n, p), le rapport c̄/d¯ doit être de l’ordre de 1/n. Dans les graphes réels, on
observe plutôt un rapport constant.

2.3 Motifs
Définition. Soient G = (V, E) et G0 = (V 0 , E 0 ) deux graphes. On dit que
0 0 0 0
• G est un sous-graphe de G (et on note G ⊂ G) si V ⊂ V et E ⊂ E.
0 0 0
• G est un sous-graphe induit de G lorsque G ⊂ G et E contient toutes les

arêtes {i, j} ∈ E telles que i, j ∈ V 0 .

0 0
• G et G sont isomorphes si il existe une bijection φ : V → V telle que
0
{i, j} ∈ E ssi {φ(i), φ(j)} ∈ E .

Un motif m d’un graphe G est un sous-graphe induit de G. Chercher les oc-

currences de m dans G c’est chercher tous les sous-graphes induits de G qui sont
isomorphes à m.
Exemple de motifs. Triangles K3 , cliques Kk , k-stars, cycles de longueur k, . . . .
On peut ensuite chercher à caractériser le nombre d’occurrences d’un motif ob-
servé par rapport au nombre attendu sous une hypothèse nulle H0 (le modèle nul

17
est obtenu par simulations ou par un modèle défini analytiquement). Et répondre
ainsi à la question : le nombre d’occurrences de ce motif est-il trop faible ou trop
grand dans ce graphe ? (par rapport au modèle attendu).

2.4 Distance, diamètre

Définition. La longueur d’un chemin e1 , . . . , ek ∈ E dans G = (V, E) est le nombre
d’arêtes qui le composent (ici k).
Si deux nœuds i, j sont connectés dans G, alors la distance ìj entre i et j est la
longueur du plus court chemin qui les relie dans le graphe. Si les deux nœuds ne
sont pas connectés dans G alors ìj = +∞.
La longueur moyenne des chemins est définie par
n X n
1 X 2 X
`¯ = ìj = ìj .
n(n − 1) i=1 j=1 n(n − 1) i,j;i<j

Le diamètre d’un graphe G est la plus grande distance entre deux nœuds du graphe

diam(G) = max{`ij ; i, j ∈ V }.

Cette quantité n’est finie que pour les graphes connexes.

Propriété petit monde (small-world property). La propriété petit monde tra-

duit le fait que dans certains réseaux même très grands, la distance entre deux nœuds
pris au hasard reste relativement petite. Ainsi, Stanley Milgram (1967) étudie un
réseau social de connaissances entre personnes aux USA et conclu au phénomène
des six degrees of separation à savoir la valeur typique de `ij dans ce réseau est
égale à 6. D’autres réseaux exhibent cette propriété de petit monde : le réseau des
acteurs Holywoodiens reliés par leur co-apparition dans un film est caractérisé par
`¯ = 3.
Pour G(n, p), on peut montrer que la valeur typique de `ij est de l’ordre de
log(n), donc les graphes G(n, p) sont des graphes petit monde.

2.5 Autres descripteurs

Composante connexe géante. Soit G = (V, E) un graphe et C une composante
connexe de ce graphe. La taille relative de C est définie par |C|/|V | (nombre de
nœuds de la composante sur nombre de nœuds total). Soit (Gn )n≥1 une suite de
graphes telle que Gn est un graphe à n nœuds et (Cn )n≥1 suite croissante (Cn ⊂ Cn+1 )

18
telle que Cn est une composante connexe de Gn . Alors Cn est dite géante si sa taille
relative |Cn |/n ne tend pas vers 0 lorsque n devient grand.
Dans G(n, p), il existe des phénomènes de transition de phase que nous n’abor-
derons pas dans ce cours.

Représentations visuelles avancées. Souvent, les données ne sont pas unique-

ment de type relationnelles, et on peut disposer de covariables sur les individus qui
composent le graphe. Ces covariables peuvent être incluses dans la représentation,
par exemple en jouant sur la couleur (covariable catégorielle) ou la taille (covariable
quantitative) des nœuds.
Par contre, si on travaille sur des graphes simples, on n’introduit pas différents
types de liens (à part dans l’orientation) entre les nœuds.

2.6 Échantillonnage dans les graphes

Le graphe observé G est souvent un échantillon d’un graphe plus grand, non
observé, noté G? . Deux types de questions peuvent apparaı̂tre :
1. Dans quelle mesure les caractéristiques de G sont-elles une bonne approxi-
mation des caractéristiques de G? lorsque la taille de G grandit ?
2. Lorsque l’on peut choisir le mode d’échantillonnage, quel type d’échantillonnage
est à privilégier ?
La questions 1 est difficile et peu de réponses existent. Quant à la question
2, cela dépend du problème que l’on se pose. Il convient de sélectionner un mode
d’échantillonnage qui soit en adéquation avec la question de recherche sous-jacente.

2.6.1 Exemples d’échantillonnages dans les graphes

Il existe différents types d’échantillonnage, on décrit ici uniquement les plus
utilisés et leurs principales caractéristiques. Dans la suite, on note G = (V, E) un
graphe observé qui est un échantillon d’un graphe plus grand et inconnu noté G? =
(V ? , E ? ), possédant |V ? | = n? nœuds.

Échantillonnages par sous-graphe induit et sous-graphe incident. L’échan-

tillonnage par sous-graphe induit est obtenu comme suit : on tire n individus au
hasard et sans remise parmi les n? nœuds existants et on observe les liens entre ces
nœuds.

19
Exemples. Réseaux sociaux ’classiques’ où on sélectionne des individus (au sein
d’un groupe) et on les interroge sur leurs relations (amitiés, . . . ).
L’inconvénient majeur est que si l’on échantillonne ainsi dans un grand graphe
(ex Facebook) on obtient un graphe essentiellement vide !
L’échantillonnage par sous-graphe incident consiste en : on tire m arêtes au
hasard et sans remise parmi les m? arêtes existantes, chaque nœud incident à une
arête est inclus dans le graphe.

Exemples. On a une base de données d’échanges d’email ou d’appels téléphoniques

entre individus dont on extrait des entrées.
Avantages et inconvénients de l’échantillonnage incident :
• aucun nœud isolé dans ce graphe ;

• potentiellement les degrés obtenus sont très faibles car on tire peu d’arêtes

incidentes aux mêmes nœuds.

Échantillonnages ’link tracing’. Le principe général est le suivant : on tire n

individus au hasard et sans remise parmi les n? nœuds existants, puis on suit un
sous-ensemble d’arêtes à partir de ces nœuds.
Dans l’échantillonnage égocentrique : on observe tous les liens incidents aux
nœuds initiaux. Puis 2 variantes sont possibles : inclusion ou pas des nœuds supplémentaires
incidents. (En général, on ne les inclue pas).

Exemples. On réalise un sondage dans une population où on demande aux indi-
vidus de dire avec combien de personnes ils sont amis. On note ou pas le nom des
amis (version avec ou sans inclusion des nœuds supplémentaires incidents).

L’échantillonnage Boule de neige (Snowball sampling) est un échantillonnage

égocentrique itéré. Initialement, on a un ensemble V0 de nœuds dont on observe les
arêtes incidentes. Les nouveaux nœuds incidents à ces arêtes sont notés V1 , puis on
observe toutes les arêtes incidentes à V1 ∪ V0 . Les nouveaux nœuds incidents sont
notés V2 , etc . . . . On arrête soit lorsque le nouvel ensemble Vk est vide, soit après
un nombre K d’itérations. Le graphe final est tel que V = V0 ∪ V1 ∪ · · · ∪ VK et les
arêtes sont toutes les arêtes de G? incidentes à des nœuds de V .

Exemples. Certains sondages en sciences sociales ; Web crawling ; . . .

Échantillonnages ’Traceroute sampling’. On tire un ensemble de nœuds ’sour-

ces’ S et un ensemble de nœuds ’cibles’ T dans V ? \ S. Pour chaque paire (si , tj ),
on sélectionne un chemin dans G? de si à tj : tous les nœuds et toutes les arêtes sur
ces chemins sont inclus.

20
Exemples. Sondages de la topologie d’internet.
Ce type d’échantillonnage nécessite d’être capable de sélectionner (efficacement)
les chemins entre 2 nœuds.

2.6.2 Exemple d’impact de l’échantillonnage : estimation

des degrés
On va voir l’impact du type d’échantillonnage sur une statistique très simple du
graphe : la suite des degrés.
Supposons que l’on connaı̂t le nombre total de nœuds n? de G? (hypothèse sou-
vent satisfaite). On s’intéresse à la distribution des degrés dans le graphe à travers
?
le vecteur N? = (N0? , N1? , . . . , NM ) où Nk? est le nombre de nœuds de degré k et M
le degré maximal dans G? . (On a M ≤ n? − 1 mais en pratique M n? ).
On observe un échantillon G du vrai graphe G? avec n nœuds et les comptages
N = (N0 , N1 , . . . , NM ). Quel est le lien entre N et N? ? Pour un échantillonnage
égocentrique, on peut dire : chaque nœud de G? a la probabilité p = n/n? d’être
présent dans G. Dans ce cas, on a la relation

E(N) = pN?

et le vrai nombre Nk? de nœuds de degré k s’estime par N̂k = Nk n? /n

Dans les autres cas, les comptages observés N sont également biaisés mais pas de
façon aussi simple. Par exemple, dans l’échantillonnage boule de neige, dans V1 il y
a plus de nœuds de grand degré que pris au hasard. Dans certains cas, si on connaı̂t
M , on peut corriger les comptages observés N. Voir Zhang et al. (2015) pour plus
de détails.

21
Chapitre 3

Spectral Clustering : détection de

communautés

Ce chapitre utilise en grande partie l’article de von Luxburg (2007).

L’analyse de grands graphes passe souvent par un résumé de l’information, par
exemple à travers un partitionnement (clustering) des nœuds du graphe : on va alors
chercher à grouper les individus en classes homogènes , i.e. les individus dans la
même classe se comportent de façon similaire au sein du graphe.
Nous verrons plusieurs façons de faire du partitionnement des nœuds d’un graphe
dans ce cours. Ce chapitre s’intéresse au clustering spectral, qui est une technique
de partitionnement qui détecte des nœuds très connectés entre eux. En ce sens, le
clustering spectral est adapté à la recherche de communautés dans des graphes (une
communauté est un groupe de nœuds qui forme une quasi-clique, i.e. qui sont très
connectés entre eux).
L’heuristique du spectral clustering est simple : si le graphe est composé de
communautés, alors il existe une permutation des lignes et des colonnes de la matrice
d’adjacence pour laquelle cette matrice est presque diagonale par blocs. Il suffit donc
de chercher à diagonaliser la matrice d’adjacence pour trouver cette permutation.
Le spectral clustering est une technique de partitionnement utilisée de façon plus
large que dans la simple analyse de graphes : on va voir qu’il peut-être utilisé sur
un tableau de données classique, par exemple comme une alternative à l’algorithme
de k-means, à partir du graphe de similarité des données.
Les caractéristiques du spectral clustering sont
• classification adaptée à la recherche de communautés (exclusivement) ;

• qui n’est pas fondée sur un modèle probabiliste ;

• mais qui a l’avantage de fonctionner sur de très grands graphes.

Dans tout ce chapitre, on ne considère que des graphes non dirigés (les arêtes

22
représentent des similarités ou des distances et sont donc symétriques).

3.1 Graphes de similarité

3.1.1 Introduction
On dispose d’un tableau de données classique de taille n × p, i.e. n observa-
tions x1 , . . . , xn avec xi ∈ Rp de dimension p. On va faire de la classification (non
supervisée) de cet ensemble de n points. Les techniques les plus classiquement uti-
lisées sont les k-means ou la classification hiérarchique. Elles sont souvent fondées
sur une notion de similarité sij ≥ 0 (inversement proportionnelle à la distance)
entre chaque paire d’observations xi , xj . À partir d’une notion de similarité entre
les vecteurs {xi }i≤n , on peut définir un graphe G = (V, E) avec V = {v1 , . . . , vn }
ensemble des nœuds du graphe et e = {vi , vj } est une arête du graphe si la simi-
larité sij entre xi , xj est plus grande qu’un certain seuil. Le graphe G peut être
binaire (sij ≥ s =⇒ {vi , vj } ∈ E et sij < s =⇒ {vi , vj } ∈ / E) ou valué
(sij ≥ s =⇒ {vi , vj } ∈ E et l’arête porte la valeur sij , sinon l’arête n’est pas
présente).
Le problème de clustering des points x1 , . . . , xn peut être reformulé comme un
problème de partitionnement du graphe de similarité où l’on cherche des groupes
de nœuds tels que les connections intra-groupes sont importantes (les vecteurs qui
correspondent aux nœuds du groupe sont très similaires entre eux) et tels que les
connections inter-groupes sont faibles (peu de similarité entre les vecteurs qui cor-
respondent à des nœuds de groupes différents).
Il y a différentes façons de définir un graphe de similarité comme on le verra dans
la prochaine section.

3.1.2 Différents graphes de similarité

On considère un ensemble de n observations x1 , . . . , xn avec xi ∈ Rp et on dispose
d’une mesure de similarité sij ≥ 0 (l’inverse d’une distance dij ) entre chaque paire
d’observations xi , xj . On va construire différents graphes de similarité G = (V, E)
avec V = {v1 , . . . , vn }.

Définition (Graphe de similarité dense.). On peut définir la similarité entre les

vecteurs {xj } à travers les voisinages dans Rp (et donc la distance entre les points),
par exemple ∀i 6= j on pose sij = exp(−kxi − xj k2 /(2σ 2 )) pour un certain σ 2 > 0
qui contrôle la taille des voisinages dans Rp et sii = 0. Dans le cas de similarités
strictement positives, on peut construire un graphe valué dense (toutes les arêtes

23
sont présentes) à partir des sij . Ainsi, tous les nœuds vi , vj avec i 6= j sont connectés
et le poids de l’arête {vi , vj } est sij > 0. Le graphe ainsi construit est dense.

Définition (Graphe de -voisinage.). On fixe un seuil > 0 et on connecte tous les

nœuds vi , vj tels que sij ≥ (distance entre les vecteurs xi , xj en-dessous du seuil).
Le graphe ainsi construit est binaire.

Définition (Graphe des k plus proches voisins.). On commence par définir un

graphe orienté G̃ = (V, Ẽ). Si xj est l’un des k plus proches voisins de xi (i.e.
dij est parmi les k plus petits éléments de {dil ; l 6= i} ou sij est parmi les k plus
grands éléments de {sil ; l 6= i}) alors on crée une arête (orientée) de vi vers vj , i.e.
(vi , vj ) ∈ Ẽ.
À partir de ce graphe orienté G̃, on peut définir G = (V, E) non orienté de deux
façons différentes :
• Soit {vi , vj } ∈ E dès que (vi , vj ) ∈ Ẽ ou (vj , vi ) ∈ Ẽ (graphe des k plus

proches voisins) ;
• Soit {vi , vj } ∈ E dès que (vi , vj ) ∈ Ẽ et (vj , vi ) ∈ Ẽ (graphe des k plus

proches voisins mutuels).

Les arêtes sont ensuite munies de leur poids sij pour former un graphe valué.

Remarques. • Le graphe des k plus proches voisins est une sorte de com-

promis entre le graphe dense et le graphe de -voisinage : étape de seuillage

qui réduit le bruit (comme pour le -voisinage) mais on garde les valeurs des
arêtes sij les plus grandes (contrairement au -voisinage).
• Le choix du graphe de similarité entre les vecteurs xi influe sur le résultat

du partitionnement que l’on obtient sur les points. Mais on ne sait pas quel
choix est meilleur a priori.
• Dans le cadre de ce cours, on dispose d’un graphe (binaire ou valué), qui est

déjà construit et qui définit les relations entre nos entités. On appliquera le
spectral clustering sur ce graphe.

3.2 Matrices laplaciennes de graphe

Pour des raisons de robustesse, le clustering spectral ne diagonalise pas la matrice
d’adajcence du graphe mais plutôt une version normalisée de celui-ci : une matrice
laplacienne du graphe (de similarité) G. Il y a plusieurs définitions de matrices
laplaciennes d’un graphe, ici nous n’en considérerons certaines.
Dans la suite, G est un graphe valué et non dirigé, de matrice d’adjacence valuée
A (taille n × n) dont les entrées sont positives Aij ≥ 0 (il faut penser que les Aij sont

24
des similarités). On note D la matrice diagonale (de taille n) dont la diagonale vaut
P P
(d1 , . . . , dn ), avec di est le degré valué du nœud i dans G, i.e. di = j Aij = j Aji
est la somme des poids des arêtes issues de i. (Le cas d’un graphe binaire est un cas
particulier du cas général que l’on décrit ici).
Pour tout vecteur (colonne) u ∈ Rn , on note u| le vecteur (ligne) transposé de u.
On note 1 le vecteur dont toutes les coordonnées valent 1 et I la matrice identité. Les
valeurs propres d’une matrice seront ordonnées de façon croissante (en respectant
les multiplicités). Ainsi, les ’k premiers vecteurs propres’ désignent les k vecteurs
propres associés aux k plus petites valeurs propres.
Rappels : une matrice L symétrique réelle est diagonalisable dans une base or-
thogonale de vecteurs propres et possède n valeurs propres réelles. Si la matrice est
en plus positive (i.e. pour tout u ∈ Rn , on a u| Lu ≥ 0) alors les valeurs propres sont
positives.
Nous commençons par définir la matrice laplacienne de graphe la plus simple et
par donner ses propriétés spectrales (i.e. valeurs propres et vecteurs propres associés).

3.2.1 Laplacien non normalisé

Définition. On définit la matrice laplacienne non normalisée L d’un graphe par

L = D − A.

Proposition 3.1 (Spectre de L). La matrice L vérifie les propriétés suivantes

1. Pour tout vecteur u ∈ Rn on a
n
1X
|
u Lu = Aij (ui − uj )2 . (3.1)
2 i,j=1

2. L est une matrice symétrique et positive.

3. La plus petite valeur propre de L est 0 de vecteur propre associé 1.
4. L possède n valeurs propres réelles positives, notées 0 = λ1 ≤ λ2 ≤ · · · ≤ λn .
Démonstration. Par définition de L = D − A et de la matrice D on a ∀u ∈ Rn ,
n
X X
| |
u Lu = u Du − u Au = |
u2i di − ui Aij uj
i=1 i,j
n n
1 X 2
X X
2

= di ui − 2 ui uj Aij + dj uj
2 i=1 i,j j=1
1X
= Aij (ui − uj )2 ,
2 i,j

25
P P
(car j Aij = di et i Aij = dj ). Ceci prouve le point 1.
Comme D et A sont symétriques, la matrice L = D −A l’est aussi. D’après (3.1),
on a pour tout u ∈ Rn , u| Lu ≥ 0, donc L est positive. En conséquence, ses valeurs
propres sont réelles et positives, on les note λ1 ≤ λ2 ≤ · · · ≤ λn . Enfin, par définition
de L, on voit que 1 est un vecteur propre, associé à la valeur propre 0 (puisque
P
i Aij = di ).

Remarques. 1. La définition de L est inchangée si on modifie la diagonale de A

(tant que D est toujours défini comme la matrice diagonale dont les entrées
sont la somme des lignes de A). On peut le voir à partir de la définition
L = D − A ou à partir de l’équation (3.1). En particulier si on a oublié de
mettre une diagonale nulle sur A (par exemple à partir de la fonction de
similarité exp vue plus haut), cela n’aura pas d’impact sur L (ni sur son
spectre).
2. Attention : cette remarque n’est pas du tout valable pour les laplaciens qui
vont suivre ! Donc il est préférable de bien faire attention à la diagonale de
A.

Proposition 3.2 (Nombre de composantes connexes de G et spectre de L). Soit

G un graphe valué dont les poids des arêtes sont positifs et L la matrice lapla-
cienne non normalisée associée. Alors la multiplicité de 0 en tant que valeur propre
de L est exactement le nombre de composantes connexes du graphe G. Si on note
C1 , . . . , Ck ⊂ {v1 , . . . , vn } ces composantes connexes et 1C1 , . . . , 1Ck les vecteurs in-
dicatrices des composantes (définis par 1Cl (i) = 1 si vi ∈ Cl et 1Cl (i) = 0 sinon),
alors l’espace propre associé à la valeur propre 0 est engendré par 1C1 , . . . , 1Ck .

Démonstration. On commence par considérer le cas k = 1 d’une seule composante

connexe dans le graphe. Si u ∈ Rn est un vecteur propre de L associé à la valeur
propre 0, on a Lu = 0 et d’après (3.1),
X
u| Lu = 0 = Aij (ui − uj )2 .
i,j

Puisque Ai,j ≥ 0, la somme est nulle seulement si tous ses termes sont nuls, ie
seulement si pour tout 1 ≤ i, j ≤ n on a Aij (ui −uj )2 = 0. Si l’arête {vi , vj } ∈ E alors
le poids Aij est non nul et nécessairement ui = uj . Donc le vecteur propre u ∈ Rn est
constant sur les coordonnées correspondant à des nœuds connectés dans le graphe.
Par définition d’une composante connexe (tous les nœuds dans la composante sont
connectés), et puisqu’on a une seule composante connexe (cas k = 1), on a ui = cte
pour tout i ∈ {1, . . . , n}. Donc u est proportionnel à 1, i.e. le vecteur 1 engendre
l’espace propre associé à la valeur propre 0.

26
Si k ≥ 2. Soient C1 , . . . , Ck ⊂ {v1 , . . . , vn } les composantes connexes du graphe
G. Sans perte de généralité, on peut supposer que les nœuds de V sont ordonnés
selon la composante à laquelle ils appartiennent. Alors, la matrice d’adjacence A a
une forme diagonale par blocs (puisque si vi , vj ne sont pas dans la même composante
connexe, alors Aij = 0). En conséquence, L = D − A a aussi une forme diagonale
par blocs
 
L1
 L2 
L= .
 
. .
 . 
Lk
Chacun des blocs Li (de taille ni × ni ) est une matrice laplacienne, associé au sous-
graphe Gi = (Ci , Ei ) ⊂ G induit par la i-ème composante connexe Ci (de cardinal
ni ) de G. L’ensemble des valeurs propres de L (= spectre de L) est la réunion des
spectres de chaque Li et les vecteurs propres correspondants sont formés par les
vecteurs propres de Li , augmentés de coordonnées nulles aux positions des autres
blocs. Comme pour chaque sous-graphe Gi , on a une seule composante connexe, le
résultat précédent nous dit que l’espace propre associé à la valeur propre 0 de Li est
engendré par 1Ci (dans Rni ). On obtient donc que l’espace propre associé à la valeur
propre 0 de L est engendré par les vecteurs 1C1 , . . . , 1Ck (en tant que vecteurs de
Rn cette fois).

Remarque. L’étude du spectre du laplacien d’un graphe permet donc de déterminer

simplement le nombre de composantes connexes de ce graphe.

Le laplacien L est intéressant car on peut faire facilement des calculs de spectre
et comprendre ce qui se passe. Cependant pour le clustering il ne donne pas les
meilleurs résultats numériques possibles et on lui préfère des versions normalisées.

3.2.2 Laplaciens normalisés

Définition. On considère une matrice laplacienne normalisée définie par

LN = I − D−1/2 AD−1/2 .

NB : dans la littérature, il existe d’autres définitions de laplacien normalisé.

−1/2
Rappels. • Comme D est une matrice diagonale, la matrice D est une
√
matrice dont les éléments diagonaux valent 1/ di (ce n’est pas vrai si D
n’est pas diagonale !).

27
• La multiplication à gauche par une matrice diagonale revient à multiplier les
vecteurs lignes de la matrice, tandis qu’une multiplication à droite multiplie
les vecteurs colonnes. Ainsi, D−1/2 AD−1/2 est la matrice dont chaque entrée
p
i, j vaut Aij / di dj . Ainsi,
 
1
 ..
. − √Aij  .

LN = 
 di dj 
1

C’est une matrice symétrique (puisque A l’est et D est diagonale).

Proposition 3.3 (Spectre de LN ). La matrice laplacienne normalisée vérifie les

propriétés suivantes :
1. Pour tout u ∈ Rn ,
1 X u
i uj 2
u| LN u = Aij √ − p .
2 1≤i,j≤n di dj

2. 0 est valeur propre de LN , de vecteur propre associé D1/2 1.

3. La matrice LN est une matrice positive qui possède n valeurs propres réelles
positives.

Démonstration. Soit u ∈ Rn , on a
n
−1/2 −1/2
X X Aij
| |
u LN u = u (I − D AD )u = u2i − ui uj p
i=1 1≤i,j≤n
di dj
n n
1 X Aij X
= u2i − 2ui uj p + u2j
2 i=1
di dj j=1
1 X u
i uj 2
= Aij √ − p ,
2 1≤i,j≤n di dj
P P
car j A ij = d i et i Aij = di . On a donc prouvé le point 1.
On a LN D 1 = D1/2 1−D−1/2 A1 = D1/2 1−D−1/2 (d1 , . . . , dn )| = D1/2 (1−1) =
1/2

0, donc 0 est valeur propre de LN associé au vecteur propre D1/2 1.

D’après le point 1, LN est positive donc ses valeurs propres sont réelles et posi-
tives.

La multiplicité de la valeur propre 0 du laplacien normalisé est reliée au nombre

de composantes connexes du graphe.

28
Proposition 3.4 (Nombre de composantes connexes de G et spectre de LN ). Soit
G un graphe valué dont les poids des arêtes sont positifs et LN la matrice laplacienne
normalisée définie ci-dessus. Alors la multiplicité de la valeur propre 0 de LN est
égale au nombre de composantes connexes du graphe G. Si on note C1 , . . . , Ck ⊂
{v1 , . . . , vn } ces composantes connexes et 1C1 , . . . , 1Ck les vecteurs indicatrices des
composantes (définis par 1Cl (i) = 1 si vi ∈ Cl et 1Cl (i) = 0 sinon), alors l’espace
propre associé à la valeur propre 0 est engendré par D1/2 1C1 , . . . , D1/2 1Ck .

Démonstration. En exercice.

Remarques. • En pratique, on s’intéresse couramment à des graphes qui n’ont

qu’une seule composante connexe (s’il y en a plusieurs, autant les étudier

séparément). Dans ce cas, on sait que 0 est valeur propre de multiplicité 1
et que l’espace propre associé est engendré par le vecteur D1/2 1 : pas très
intéressant. L’étude du spectre n’apporte rien de plus sur cette question.
• On utilise le spectre du laplacien de la façon suivante : on s’intéresse aux

k premiers vecteurs propres de LN : c’est similaire à une ACP (analyse en

composantes principales) ou du MDS (multi-dimensional scaling). Dans ce
nouvel espace, les points initiaux (nœuds du graphe) sont mieux séparés et
un simple clustering (type k-means) donne de bons résultats.

Enfin, on définit également

Labs = D−1/2 AD−1/2 = I − LN .

Cette matrice Labs a exactement les mêmes vecteurs propres que LN . Si on note
0 = λ1 ≤ λ2 ≤ · · · ≤ λn les valeurs propres de LN alors les valeurs propres de Labs
sont 1 − λn ≤ . . . ≤ 1 − λ2 ≤ 1 − λ1 = 1. Attention : dans L, LN ce sont les petites
valeurs propres qui contiennent l’information intéressante alors que pour Labs on va
voir que ce sont les grandes valeurs propres, en valeur absolue !

3.3 Algorithmes de clustering spectral

Tout comme il existe de nombreuses définitions de la matrice laplacienne d’un
graphe, il existe de nombreux algorithmes de clustering spectral. Nous en verrons
uniquement 2 : l’algorithme de spectral clustering normalisé qui utilise LN (Algo-
rithme 3.1) et l’absolute spectral clustering fondé sur Labs (Algorithme 3.2).
Le principe du spectral clustering est donc de transformer les observations de
départ xi ∈ Rp , 1 ≤ i ≤ n en un nouvel ensemble de points yi ∈ Rk , 1 ≤ i ≤ n (=les

29
Algorithm 3.1: Spectral clustering normalisé de Ng et al. (2001)

//Entrée : A de taille n × n d’entrées positives, nombre k de clusters

//Sortie : Clusters C1 , . . . , Ck qui partitionnent {1, . . . , n}
Calculer la matrice laplacienne normalisée LN
Calculer les k vecteurs propres u1 , . . . , uk associés aux plus petites valeurs
propres de LN
Former la matrice U de taille n × k dont les colonnes sont u1 , . . . , uk
Former la matrice T de taille n × k en normalisantples lignes de U
P 2
pour avoir une norme euclidienne 1 (i.e. tij = uij / k uik )
Créer des clusters C1 , . . . , Ck sur les n lignes de T par k-means

Algorithm 3.2: Absolute Spectral clustering de Rohe et al. (2011).

//Entrée : A de taille n × n d’entrées positives, nombre k de clusters

//Sortie : Clusters C1 , . . . , Ck qui partitionnent {1, . . . , n}
Calculer la matrice laplacienne Labs
Calculer les k vecteurs propres u1 , . . . , uk de Labs associés aux k plus
grandes valeurs propres en valeur absolue
Former la matrice U de taille n × k dont les colonnes sont u1 , . . . , uk
Créer des clusters C1 , . . . , Ck sur les n lignes de U par k-means

lignes de la matrice U ), via un graphe de similarité, la matrice laplacienne associée et

ses k premiers vecteurs propres. Les propriétés de ces matrices laplaciennes font que
ce nouvel ensemble de points yi est facilement classifiable en k groupes (un simple
algorithme k-means suffit à bien séparer ces nouveaux points).
Si le graphe de départ a k composantes connexes, les k premiers vecteurs propres
u1 , . . . , uk engendrent l’espace propre associé à la valeur propre 0, et on a vu que cet
espace est engendré par les vecteurs indicatrices 1C1 , . . . , 1Ck . Si on applique l’algo-
rithme des k-means sur les lignes de U avec k groupes, on retrouve exactement les
composantes connexes C1 , . . . , Ck . Par analogie, lorsqu’on a une seule composante
connexe, les algorithmes de spectral clustering vont donner un partitionnement des
nœuds du graphe en un ensemble de ’presque composantes connexes’ ou plus exac-
tement, de communautés.
Le spectral clustering en valeur absolue a une propriété supplémentaire : il va
chercher des structures de type biparties dans le graphe. Il tend à mettre dans le
même groupe des nœuds qui partagent beaucoup de voisins.

30
3.4 Exemples jouets
On considère ici le cas de quelques graphes remarquables : on étudie leur spectre
(avec L au lieu de LN ou de Labs car les calculs sont plus simples) et on essaye de
voir l’impact sur le principe du clustering.

Proposition 3.5. 1. Soit Kn le graphe complet sur n nœuds, alors les valeurs
propres du laplacien L associé sont : 0 de multiplicité 1 et n de multiplicité
n − 1.
2. Soient i, j deux nœuds de degré 1 qui partagent le même voisin k dans le
graphe G. Alors le vecteur u ∈ Rn défini par ui = 1, uj = −1 et ul = 0 pour
tout l ∈ {1, . . . , n} \ {i, j} est un vecteur propre du laplacien L associé à la
valeur propre 1.
3. Soit Sn le graphe en étoile sur n nœuds, alors les valeurs propres du laplacien
L associé sont : 0 de multiplicité 1, 1 de multiplicité n − 2 et n de multiplicité
1.

Démonstration. 1. Kn est connexe donc 0 est valeur propre de multiplicité 1, associée

au vecteur propre 1. Soit u ∈ Rn un vecteur propre associé à une valeur propre
λ > 0, alors u est orthogonal à 1, i.e. ni=1 ui = 0. Sans perte de généralité, on peut
P

supposer u1 6= 0 et on a u1 = − ni=2 ui 6= 0. De plus, le laplacien L de Kn vérifie

Lij = −1 si i 6= j et Lii = n − 1. On obtient alors

n
X n
X
(Lu)1 = L1i ui = (n − 1)u1 − ui = nu1 .
i=1 i=2

Donc si u est un vecteur propre pour la valeur propre λ, on a λu1 = (Lu)1 = nu1 .
Donc n est la seule autre valeur propre (elle a la multiplicité n − 1 et est associé à
n’importe quel vecteur orthogonal à 1).
2. Quitte à réordonner les nœuds du graphe, on peut écrire le laplacien sous la forme
 
1 0 −1 0 . . . 0
0 1 −1 0 . . . 0
 
−1 −1 dk ? ? ? 
 
L= 0
.
0 ? 
 .. ..
 
 . . ? ?? 

0 0 ?

Alors, le vecteur u| = (1, −1, 0, . . . , 0) est un vecteur propre associé à la valeur

propre 1.

31
3. On considère à présent le graphe en étoile Sn . Il est connexe donc 0 est valeur
propre de multiplicité 1, associée au vecteur propre 1. On numérote 1 le nœud au
centre de l’étoile et de 2 à n les nœuds au bout des branches. En appliquant le
résultat du point 2 pour les noeuds (i, i + 1) pour i allant de 2 à n − 1 (ce sont des
nœuds de degré 1 qui partagent le nœud 1 en commun), on obtient (n-2) vecteurs
u(i) associés à la valeur propre 1. On vérifie qu’ils sont linéairement indépendants
(écrire n−1 (i)
P
i=2 αi u = 0 et voir que nécessairement αi = 0).
Enfin pour trouver la dernière valeur propre λ, on utilise T r(L) = ni=1 λi =
P

λ+0+(n−2). Or T r(L) = (n−1)+1×(n−1) = 2n−2, donc λ = T r(L)−n+2 = n.

(Le vecteur propre correspondant est nécessairement constant sur les indices i allant
de 2 à n et orthogonal à 1, on peut déduire facilement sa forme).

Conséquences.
• Le résultat pour Kn indique que si on fait un clustering des lignes de U avec

k > 1 groupes, on n’obtient rien qui fasse du sens. C’est normal puisqu’il n’y
a qu’une seule communauté dans Kn .
• Pour Sn , le clustering spectral trouve soit une seule communauté, soit n − 1

communautés : le nœud central associé à un nœud au hasard, puis chaque

autre nœud tout seul.
Proposition 3.6. 1. Un graphe est bipartie si et seulement si le spectre de Labs
est symétrique.
2. Un graphe connexe est bipartie si et seulement si λmin (Labs ) = −λmax (Labs ).
Démonstration. Admis.

Conséquences. On comprend que l’absolute spectral clustering qui regarde les

plus grandes valeurs propres en valeur absolue va capturer les structures de type
bipartie.

3.5 Commentaires pratiques

• Le choix de la fonction de similarité (quand on part de données non graphe)
doit dépendre du type de données.
• Une différence importante entre le graphe d’-voisinage et les graphes des k
plus proches voisins (simple ou mutuel) est l’adaptation locale du voisinage
des seconds : les tailles de voisinage sont différentes en fonction des régions
de l’espace (plus grandes dans les régions peu denses, plus petites dans les
régions plus denses).

32
• Le graphe des k plus proches voisins mutuel tend à connecter entre eux des
points dans des régions de densité constante (comme la version simple) mais
ne connecte pas entre elles des régions proches mais de densité différente. En
ce sens, c’est un compromis entre -voisinage et k plus proches voisins simple.
• Les graphes des k plus proches voisins sont plus faciles à manipuler que le
graphe construit avec une similarité gaussienne (qui lui est dense). Il peuvent
donc être préférables ; mais attention à la perte d’information : on peut par
exemple avoir plus de composantes connexes dans ces graphes que de clusters
désirés !
• Recommandations empiriques pour les choix des paramètres :
— prendre k de l’ordre de log(n) pour le graphe des k-plus proches voi-
sins simple et plus grand (sans règle explicite) pour le graphe des k-plus
proches voisins mutuel. Il faut de toute façon regarder le nombre de com-
posantes connexes obtenues, le comparer au nombre de clusters voulus et
ajuster en conséquence.
— prendre tel que le graphe résultant soit connecté.
— pas de bonne règle pour le choix de σ dans la similarité gaussienne.
• On a vu que si le graphe a p composantes connexes, alors l’espace propre
associé à la valeur propre 0 a pour dimension p et est engendré par les indi-
catrices des clusters. Cependant, la sortie d’un algorithme de décomposition
spectrale est n’importe quelle base orthogonale de vecteurs propres de cet
espace (i.e. pas forcément la base des vecteurs d’indicatrices mais une base
issue d’une combinaison linéaire de celle-ci). Par contre, le k-means sur ces
vecteurs permet d’obtenir simplement les clusters. (En fait, la matrice U n’a
que k lignes différentes, on peut faire le clustering visuellement).
• Le choix du nombre de clusters k est un problème récurrent du clustering. Ici,
pas de modèle probabiliste donc pas de critère type BIC ou reposant sur une
vraisemblance mais on peut utiliser d’autres critères ad-hoc type ’similarité
intra-groupes et inter-groupes’. Une technique courante consiste à utiliser
l’heuristique du ’trou des valeurs propres’ (eigengap) : on choisit le nombre
de clusters k par
k̂ = Argmax λj+1 (LN ) − λj (LN ).
1≤j≤n−1

Rem : il n’y a pas d’équivalent pour Labs .

33
Chapitre 4

Modèles de graphes aléatoires et

classification des nœuds

Nous avons déjà vu le modèle G(n, p) et constaté qu’il s’ajustait mal sur les
réseaux réels observés (hypothèses d’indépendance entre les arêtes et uniformité de
la probabilité de connection dans le graphe trop restrictives).
On commence par présenter 2 modèles qui apparaissent souvent dans la littérature
et qui ne sont pas liés à un point de vue type classification des nœuds. Le reste de ce
chapitre sera consacré aux modèles probabilistes de classification des noeuds d’un
graphe.

4.1 Deux modèles de graphes (sans liens avec la

classification)
4.1.1 Les modèles exponentiels de graphes aléatoires
Il s’agit d’un modèle qui s’inspire naturellement de la famille de modèles expo-
nentiels.
Définition. Soit n ≥ 1 un entier. On note An l’ensemble des matrices d’adjacence
binaires (symétriques ou non) de taille n×n et pour tout A ∈ An , soit S(A) ∈ Rp un
vecteur de statistiques du graphe associé. Le modèle exponentiel de graphe associé
au vecteur de statistiques S et noté ERGM(S) est défini par la famille de lois de
probabilités {Pθ }θ∈Rp définies sur l’ensemble An par
p 1
|

∀θ ∈ R , ∀A ∈ An , Pθ (A) = exp θ S(A) ,
c(θ)
avec c(θ) = A∈An exp(θ| S(A)) une constante de normalisation.
P

34
Dans ce modèle, S(A) devient automatiquement un vecteur de statistiques ex-
haustives du modèle. Tous les graphes ayant la même valeur observée de S ont la
même probabilité d’occurrence sour ERGM(S). En pratique, S(A) peut contenir le
nombre d’arêtes, de triangles, de k-stars, . . . ou encore des covariables du modèle.
Dans la suite, on utilise des notations de graphe non dirigé mais tout est généralisable
au cas des graphes dirigés.
Exemple . Soit S0 (A) = vec(A) = vec((Aij )1≤i<j≤n ) alors le ERGM(S0 ) correspon-
dant vérifie
X
Pθ (A) ∝ exp( θij Aij ),
i<j

où ∝ signifie ’proportionnel à’. C’est un modèle de variables aléatoires Aij indépendantes
non identiquement distribuées avec Ai,j ∼ B(pij ) et pij = exp(θij )/(1 + exp(θij )).
C’est un modèle qui a autant de paramètres que d’observations, donc pas très pra-
tique.
Si on impose la contrainte θij = θ pour tout i, j, alors on obtient le modèle d’Erdös-
Rényi
Pθ (A) ∝ exp(θS1 (A)),
P
où S1 (A) = i,j Aij est le nombre d’arêtes du modèle et p̂ = S1 (A)/[n(n − 1)/2].
P
Si S(A) = (S1 (A), S2 (A)) avec S1 comme ci-dessus et S2 (A) = i,j,k Aij Aik alors
les variables (Aij )i<j sont non indépendantes et on n’a pas d’expression analytique
pour l’EMV.
P
Soit k ≥ 1 et Sk (A) le nombre de k-stars du graphe A et T (A) = ijk Aij Aik Ajk le
nombre de triangles. Dans les Markov random graph, on utilise S = (S1 , . . . , Sn−1 , T ).
En pratique, aller jusque k = n − 1 est beaucoup trop grand et on se contente de
k << n − 1 pour la plupart des ERGM courants.

Problèmes du ERGM.
• La constante c(θ) n’est pas calculable. Les méthodes d’estimation sont basées

sur des méthodes MCMC avec par exemple un échantillonneur de Gibbs pour
supprimer le problème de la constante inconnue.
• La maximisation de la vraisemblance reste un pbm difficile, et en fait mal

posé : ces modèles sont souvent ’dégénérés’ au sens où cette loi concentre sa
masse sur le graphe complet ou le graphe vide, ou un mélange des deux. Voir
Chatterjee and Diaconis (2013); Schweinberger and Handcock (2015) pour
plus de détails.
Dans ce cours, je déconseille fortement l’usage des ERGMs.

35
4.1.2 Attachement préférentiel
Il s’agit d’un modèle dynamique d’évolution des graphes, qui illustre le concept
Rich get richer.
Principe : on commence avec un petit graphe initial G0 = (V0 , E0 ) et la suite de
degrés associés (d1,0 , . . . , d|V0 |,0 ) ; on fabrique une suite croissante de graphes Gt =
(Vt , Et ). Pour cela, on itère les étapes suivantes pour chaque t ≥ 1,
• un nouveau nœud it de degré m ≥ 1 est ajouté au réseau et Vt = Vt−1 ∪{it } =

V0 ∪ {i1 , . . . , it }.
• Ce nouveau nœud se connecte avec m nœuds existants qui sont choisis chacun

avec probabilité dj,t−1 /(2|Et−1 |) où dj,t est le degré du nœud j au temps t et
2|Et | la somme totale des degrés au temps t (attachement préférentiel aux
nœuds de degrés les plus élevés),
• On met à jour les degrés dj,t pour j ∈ Vt .

A l’itération T , le graphe possède donc |V0 | + T nœuds et |E0 | + T m arêtes.

Avantages et inconvénients.
• C’est un model génératif dynamique.

• Il permet d’expliquer la loi de puissance des degrés : à la limite (T → ∞) et

sous certaines conditions, la distribution des degrés du graphe suit une loi de
puissance.
• Problème du choix des paramètres G0 , m, Tf inal . Impact de ce choix sur le

graphe obtenu ?
• D’un point de vue statistique, ce n’est pas un modèle qu’on peut ajuster sur

les données.

4.2 Généralités sur les modèles à variables latentes

4.2.1 Définitions
Les modèles à variables latentes (ie non observées) supposent l’existence d’une
variable aléatoire (latente) associée à chaque observation et qui caractérise la distri-
bution de cette observation. Cette variable latente peut être soit à valeurs continues,
soit à valeurs discrètes (finies). Dans ce dernier cas, on obtient naturellement une
classification des observations en fonction de la valeur latente. Ainsi, dans un modèle
à variables latentes, on dispose d’une suite d’observations (Xi )1≤i≤n et on suppose
qu’il existe des variables latentes (non observées) (Zi )1≤i≤n telles que la loi de Xi
conditionnelle aux (Zj )1≤j≤n ne dépend que de Zi . Pour des raisons de commodité,
on suppose même le plus souvent que la loi des (Xi )1≤i≤n sachant les (Zi )1≤i≤n est

36
le produit des lois de chaque Xi conditionnelle à Zi uniquement. On fait ainsi une
hypothèse d’indépendance conditionnelle des observations.

n
Y
P((Xi )1≤i≤n |(Zi )1≤i≤n ) = P(Xi |Zi ).
i=1

Lorsque les (Zi )1≤i≤n sont indépendantes, on obtient alors que les (Xi )1≤i≤n sont
aussi des variables indépendantes (mais non identiquement distribuées). Il s’agit des
modèles de mélange (finis lorsque les Zi sont à valeurs finies). Lorsque les (Zi )1≤i≤n
forment une chaı̂ne de Markov, alors les (Xi )1≤i≤n ne sont plus indépendantes (seule-
ment conditionnellement indépendantes) et on obtient les chaı̂nes de Markov cachées.

Lorsqu’on observe un graphe aléatoire, on a vu que l’on dispose en fait d’un

ensemble de variables (Aij )1≤i,j≤n (binaires ou valuées). La modélisation par va-
riables latentes naı̈ve consisterait à supposer l’existence de variables non observées
(Zij )1≤i,j≤n qui caractérisent la distribution des (Aij )1≤i,j≤n . Cette approche est naı̈ve
car elle ne tient pas compte du fait que la donnée Aij est une caractérisation du lien
entre les individus i et j. Il est en fait plus naturel d’envisager qu’il existe des
variables latentes (Zi )1≤i≤n qui caractérisent les individus et que la variable Aij de
relation entre i et j a une distribution qui est caractérisée par la valeur de Zi et de Zj .

Dans toute la suite, on va donc supposer qu’il existe des variables (Zi )1≤i≤n
indépendantes et identiquement distribuées (iid), à valeurs continues ou discrètes et
finies, telles que la loi conditionnelle des (Aij )1≤i,j≤n sachant les (Zi )1≤i≤n vérifie
Y
P((Aij )1≤i,j≤n |(Zi )1≤i≤n ) = P(Aij |Zi , Zj ).
1≤i,j≤n

Il faut remarquer que même si les Zi sont indépendantes, les Aij ne le sont plus
du tout : la structure de dépendance entre les variables aléatoires est compliquée
par le fait que par exemple Aij et Aik dépendent tout les deux de la même variable
latente Zi (voir Figure 4.1).

4.2.2 Estimation des paramètres

Considérons la vraisemblance d’un modèle à variables latentes : la distribution
des (Aij )1≤i,j≤n n’est donnée que conditionnellement aux variables latentes (Zi )1≤i≤n ,

37
Z1 Z2 · · · Zi · · · Zj · · · Zn−1 Zn

A12 · · · A1n · · · Aij ··· An−2,n−1 An−1,n

Figure 4.1 – Dépendances entre les variables d’un modèle à variables latentes pour
graphes.

on écrit donc
Z Z
L(θ) =Pθ ((Aij )1≤i,j≤n ) = ... Pθ ((Aij )1≤i,j≤n , Z1 = z1 , . . . , Zn = zn )dz1 . . . dzn
z1 zn
Z n
Z Y Y
= ... Pθ (Zi = zi ) × Pθ (Aij |Zi = zi , Zj = zj )dz1 . . . dzn .
z1 zn i=1 i,j

En pratique, si les Zi sont à valeurs dans {1, . . . , Q}, les intégrales ci-dessus sont des
sommes et on a Qn termes à sommer. Lorsque n n’est pas très petit (n ≥ 10), cette
somme n’est pas accessible numériquement en un temps raisonnable. Si les Zi sont à
valeurs continues, on peut approcher les intégrales en les discrétisant (par exemple
sur Q points) et le problème reste exactement le même.
Dans un modèle à variables latentes, il n’est pas possible (en général) de faire un
calcul efficace de la vraisemblance. L’estimation des paramètres se fait généralement
en utilisant l’algorithme EM (expectation-maximization) qui approche l’estimateur
du maximum de vraisemblance.

L’algorithme EM. L’algorithme EM (expectation-maximization) est un algorithme

itératif qui permet de maximiser (localement) la vraisemblance dans des modèles à
données manquantes (typiquement, les modèles à variables latentes sont des modèles
à données manquantes).
Supposons que l’on ait un modèle avec données observées X1:n et données man-
quantes (ie non observées) S1:n . On appelle données complètes l’ensemble des va-
riables (S1:n , X1:n ).
Le principe de l’algorithme EM est le suivant :
0
• On part d’une valeur initiale θ du paramètre,

• À l’itération k, on effectue les deux étapes

— Expectation : on calcule Q(θ, θk ) := Eθk (log Pθ (S1:n , X1:n )|X1:n ).

— Maximization : on maximise θk+1 := Argmaxθ Q(θ, θk ).
k+1
• Arrêt lorsque δ := kθ − θk k/kθk k ≤ ou un nombre maximum d’itérations
est atteint.

38
À chaque itération, la vraisemblance (observée) augmente. En effet, par construc-
tion on sait que Q(θk+1 , θk ) ≥ Q(θk , θk ), i.e :

Pθk+1 (S1:n , X1:n ) Pθk+1 (S1:n , X1:n )
0 ≤Eθk log X1:n ≤ log Eθk X1:n
Pθk (S1:n , X1:n ) Ineg. Jensen Pθk (S1:n , X1:n )
Z
Pθk+1 (S1:n = s1:n , X1:n )
= log Pθk (S1:n = s1:n |X1:n )ds1 . . . dsn
S n Pθk (S1:n = s1:n , X1:n )
Z
Pθk+1 (s1:n , X1:n ) P k+1 (X1:n )
= log ds1 . . . dsn = log θ .
Sn Pθk (X1:n ) Pθk (X1:n )
Ainsi, Pθk+1 (X1:n ) ≥ Pθk (X1:n ).
Donc l’algorithme EM converge (quand le nombre d’itérations augmente) vers un
maximum local de la vraisemblance. En lançant l’algorithme avec plusieurs initiali-
sations, on devrait atteindre le maximum global.
L’algorithme EM est particulièrement adapté au cas où les variables latentes sont
à valeurs finies. Nous reviendrons sur son application dans le cadre du modèle à
blocs stochastiques.

4.3 Espaces latents continus (pour graphes binaires)

Les modèles à espaces latents continus n’ont été développés que pour les graphes
binaires.

4.3.1 Modèle à positions latentes et al.

Le modèle à positions latentes (latent position model) de Hoff et al. (2002) a été
proposé pour étudier des réseaux sociaux. Dans ce modèle, les variables latentes sont
i.i.d. à valeurs dans Rq qui représente un espace social. La proximité des individus
dans cet espace induit une plus grande probabilité de connexion dans le graphe.
Ainsi, seule la position relative des variables latentes entres elles est importante
pour le modèle (et pas leur position absolue).
On considère un graphe binaire non dirigé (Aij )1≤i,j≤n et (possiblement) des
vecteurs de covariables xij ∈ Rs sur chaque relation (i, j). On utilise un modèle de
régression logistique
P(Aij = 1|Zi , Zj , xij )
logit(P(Aij = 1|Zi , Zj , xij )) = = α + β | xij − kZi − Zj k,
1 − P(Aij = 1|Zi , Zj , xij )
où k · k est la norme euclidienne dans l’espace latent Rq . Les paramètres du modèle
sont (α, β) ∈ R × Rs . On peut remplacer norme euclidienne par n’importe quelle
distance.

39
Le paramètre α règle la densité du graphe. Il faut remarquer que les variables
{Zi }i ne peuvent être reconstituées qu’à rotation, symétrie axiale et translation près.
En effet, chacune de ces opérations laisse l’ensemble des distances (kZi − Zj k)i,j
inchangé et donc ne modifie pas le modèle. On appelle configurations équivalentes
deux ensembles {Zi }i et {Zi0 }i qui induisent les mêmes valeurs de distances (kZi −
Zj k)i,j = (kZi0 − Zj0 k)i,j .
Ainsi, pour des valeurs des paramètres (α, β) fixées, deux configurations équivalentes
{Zi }i et {Zi0 }i induisent la même distribution sur les observations, et réciproquement,
si α et β sont fixés alors si on a deux ensembles de configuration {Zi }i et {Zi0 }i qui
induisent la même loi alors les configurations sont équivalentes.

Estimation des paramètres et des variables latentes. Le package latentnet

propose une méthode d’estimation bayésienne des paramètres et des positions la-
tentes. Voir TP pour plus de détails.

4.3.2 Version classifiante du modèle

Dans le modèle précédent, les nœuds du graphe ne sont pas naturellement clas-
sifiés en groupes qui permettent de les interpréter. On peut obtenir une telle clas-
sification en combinant l’approche avec un modèle de mélange sur les variables
latentes (Handcock et al., 2007).
Ainsi, on suppose que les variables latentes Zi ∈ Rq sont en fait générées selon
un modèle de mélange de lois gaussiennes multi-dimensionnelles Nq (mk , σk2 Id) avec
1 ≤ k ≤ K, de proportions πk , 1 ≤ k ≤ K, de moyennes différentes (mk , 1 ≤ k ≤ K)
et des matrices de covariance sphériques (σk2 Id).
Le choix du nombre de clusters K se fait automatiquement dans ce cadre bayésien :
on place une loi a priori sur K et on estime par le maximum a posteriori. Il faut noter
que les groupes obtenus sont nécessairement des communautés : si deux variables
Zi , Zj sont dans la même composante gaussienne, alors elles sont proches dans Rq
et la probabilité que les nœuds i, j soient connectés est plus grande.

4.3.3 Choix de la dimension de l’espace latent

En pratique, il n’existe aucun méthode permettant de choisir la dimension q de
l’espace latent (attention, cette dimension n’est pas le nombre de clusters K de la
méthode de Handcock et al. (2007) !).
Les logiciels sont implémentés avec q = 2 (ou 3) mais rien ne permet d’affirmer
que ce choix est pertinent, ni qu’il n’a pas un impact majeur sur les résultats.

40
4.4 Espaces latents discrets : Modèles à blocs sto-
chastiques (stochastic block model)
4.4.1 Le modèle
Dans cette section, les variables latentes Z := {Z1 , . . . , Zn } sont i.i.d. à valeurs
finies dans {1, . . . , Q} et de loi π = (π1 , . . . , πQ ). Il sera parfois pratique de voir
plutôt Zi comme un vecteur de taille Q de la forme Zi = (Zi1 , . . . , ZiQ ) dont les
coordonnées sont dans {0, 1}, somment à 1 et tel que Zi est de loi multinomiale
M(1, π).
On va décrire le modèle à blocs stochatiques (SBM) dans le cadre d’un graphe
non dirigé mais les notations se généralisent facilement au cas dirigé. On considère
donc la matrice d’adjacence d’un graphe non dirigé A := {Aij }1≤i<j≤n constitué de
variables aléatoires Aij ∈ A (cas binaire ou valué), qui caractérisent les relations
entre les nœuds i et j.
Comme précédemment, conditionellement aux variables latentes Z = {Zi }1≤i≤n ,
les variables A = {Aij }i,j sont indépendantes et la distribution de chaque Aij ne
dépend que de Zi et Zj . On note F (·; γZi Zj ) cette distribution conditionnelle, où
γ = (γq` )1≤q,`≤Q est appelé paramètre de connectivité. C’est une matrice symétrique
dans le cas d’un graphe non dirigé puisque γq` = γ`q . Le paramètre γq` décrit la loi
des interactions entre des nœuds des groupes q et `.
Ainsi, le modèle à blocs stochastiques est caractérisé par

· Z = Z1 , . . . , Zn variables latentes i.i.d. de loi π sur {1, . . . , Q},

· A = {Aij }i,j ensemble d’observations à valeurs dans A,
Q
· P(A|Z) = i,j P(Aij |Zi , Zj ) (indépendance conditionnelle),
· ∀i, j et ∀1 ≤ q, ` ≤ Q, on a Aij |{Zi = q, Zj = `} ∼ F (·; γq` ).

On va distinguer à présent le SBM binaire (apparu dès le début des années 80

en Sciences Sociales) du cas valué (beaucoup plus récent).
Dans le cas binaire, la loi conditionnelle de Aij sachant Zi , Zj est simplement
une loi de Bernoulli B(γZi Zj ). Ainsi,

∀y ∈ {0, 1}, F (y; γ) = γ y (1 − γ)1−y .

Pour les graphes valués, on peut utiliser pour modéliser la loi conditionnelle de
Aij sachant Zi , Zj n’importe quelle loi paramétrique qui dépend seulement de Zi , Zj
(ex : Poisson, Gaussienne, Laplace, . . . ). Cependant, si cette loi est absolument
continue par rapport à la mesure de Lebesgue, on récupère un graphe valué dense,

41
ce qui n’est pas toujours adéquat. Pour pallier ce problème, on introduit un mélange
avec une masse de Dirac en 0 (notée δ0 (·)) qui modélise les arêtes absentes. Ainsi,
∀y ∈ A, F (y; γ) = αG(y, η) + (1 − α)δ0 (y),
où le paramètre de connectivité γ = (α, η) avec α ∈ [0, 1] et G(·, η) est la loi
conditionnelle sur les valeurs des arêtes présentes.
Pour des raisons d’identifiabilité, il est préférable de restreindre G à être une loi
absolument continue en 0. En effet, dans le cas contraire, on ne peut pas identifier
α. Si G est absolument continue en 0, alors on a αq` = 1 − P(Yij = 0|Zi = q, Zj = `).
Si on veut utiliser une loi de Poisson par exemple, on utilise pour G la loi de Poisson
tronquée en 0. Les valeurs nulles de Yij sont ainsi dues uniquement à la masse
de Dirac δ0 et on obtient une loi dite à inflation ou à déflation de zéros.
L’avantage étant que la densité du graphe n’est pas nécessairement liée à la valeur
moyenne des arêtes présentes.
Si tous les αq` valent 1, le graphe est dense (toutes les arêtes sont présentes).
Ainsi les αq` sont des paramètres de densité du graphe. Si tous les αq` valent 0, on
obtient un graphe vide (ie sans arêtes), ce qui n’est pas très intéressant.
Lorsque la loi G(·, η) est une masse de Dirac en 1 (indépendante de η), on re-
trouve le SBM binaire. Le seul paramètre de la loi conditionnelle est alors α. Les cas
classiques pour le choix de G sont : une loi de Poisson tronquée en 0, une gaussienne
(multivariée), etc.
Dans le cas non binaire, on peut (pour des raisons de parcimonie), supposer que
tous les αq` sont constants (égaux à un certain α fixé). Alors, la densité des arêtes
est homogène dans le graphe, seule leur intensité (ie la valeur de Aij ) va varier en
fonction des groupes (q, `).
Dans la suite, on note le paramètre global du modèle θ = (π, γ) = (π, α, η) =
((π1 , . . . , πQ ); (αq` )q,` ; (ηq` )q,` ). La vraisemblance du modèle s’écrit
Q Q
X X
Pθ (A) = ... Pθ (A, Z1 = z1 , . . . , Zn = zn )
z1 =1 zn =1
Q Q n Y
X X Y
= ... πz i × F (Aij ; γzi zj )
z1 =1 zn =1 i=1 i,j
Q Q Q n Y Y
X X YY
= ... πqziq × ziq zj`
F (Aij ; γq` ) ,
z1 =1 zn =1 q=1 i=1 1≤q,`≤Q i,j

et la log-vraisemblance des données complètes s’écrit simplement

Q n
X X X X
log Pθ (A, Z) = Ziq log πq + Ziq Zj` log F (Aij ; γq` ). (4.1)
q=1 i=1 1≤q,`≤Q i,j

42
Cas particulier : affiliation (planted partition model). Liens avec la détection
de communauté. Lorsque le paramètre de connectivité γ ne prend que deux va-
leurs différentes : une valeur intra-groupes et une valeur inter-groupes, on parle de
modèle d’affiliation (ou parfois, dans le cas binaire, de ’planted partition model’). Il
s’agit d’un sous-modèle où on contraint :

γin lorsque q = `,
∀1 ≤ q, ` ≤ Q, γq` = (4.2)
γout lorsque q 6= `.

Dans le cas d’un graphe binaire, sous un modèle d’affiliation, si on suppose en

plus que γin γout , la classification des nœuds induite par le modèle correspond
exactement à une détection de communautés : on cherche des groupes de nœuds
fortement connectés entre eux. Dans un modèle d’affiliation avec γout γin , on va
au contraire chercher des structures de type ’multi-parties’.
Dans le cas général (pas affiliation), on récupère avec SBM une classification des
nœuds en groupes de nœuds qui ’se connectent de la même façon’ aux autres groupes.
C’est un type de classification beaucoup moins contraint que la simple détection de
communautés. Ces différences sont illustrées sur l’exemple jouet de la Figure 4.2.

Figure 4.2 – Exemple jouet de structures de classification différentes (couleurs

gris/noir) obtenues à partir du même graphe. À gauche, le résultat d’une méthode
de détection de communautés ou d’une méthode SBM. À droite, une classifica-
tion qui pourrait également être obtenue à partir du SBM mais pas à partir de
la détection de communautés : les hubs forment un premier groupe tandis que les
nœuds ’périphériques’ forment le second. Cette seconde classification ne peut pas
s’obtenir avec du clustering spectral (ni normalisé ni absolu).

4.4.2 L’algorithme EM
Nous avons vu qu’une façon d’approcher le maximum de vraisemblance dans un
modèle à variables latentes est d’utiliser l’algorithme EM. Cependant, l’étape E de
l’algorithme requiert de pouvoir calculer facilement la loi des observations {Aij }i,j
sachant les variables latentes {Zi }i . C’est le cas par exemple pour des modèles de
mélange finis classiques (pas sur des graphes), ou dans les modèles de Markov cachés.

43
Dans le cas de variables latentes sur des graphes où chaque observation Aij dépend
de deux variables latentes Zi , Zj ce n’est plus possible.

Digression sur les modèles graphiques et les dépendances conditionnelles.

Un modèle graphique est un modèle probabiliste dans lequel un graphe représente
la structure de dépendance de la distribution d’un ensemble de variables aléatoires.
Il existe deux types de modèles graphiques : les modèles dirigés (où le graphe de
dépendances est dirigé) et les modèles non dirigés (ou le graphe de dépendances est
non dirigé). On pourra se référer à Lauritzen (1996) ou au chapitre 8 de Bishop (2006)
pour en savoir plus. On aura besoin également de deux définitions préliminaires.

Définition. Dans un graphe dirigé, les parents d’un nœud j ∈ V sont tous les
nœuds i ∈ V tels qu’il existe une arête orientée de i vers j. Les descendants du
nœud i ∈ V sont tous les nœuds j ∈ V tels qu’il existe un chemin orienté de i vers
j.

Soit P une distribution sur X V et G = (V, E) un graphe tel que

• l’ensemble V = {1, . . . , p} des nœuds indexe un ensemble de variables aléatoires

{Xi }i∈V à valeurs dans X p ,

• L’ensemble des arêtes E décrit les relations de dépendance entre les v.a.

{Xi }i∈V sous la loi P (plus de détails ci-dessous).

Dans un modèle graphique, on a
• Soit G est un graphe acyclique et dirigé (DAG), alors P se factorise selon G

ie on a Y
P({Xi }i∈V ) = P(Xi |pa(Xi , G)),
i∈V

où pa(Xi , G) sont les variables parents de Xi dans G.

• Soit G est non dirigé, alors pour tout {i, j} ∈/ E, on a Xi ⊥⊥ Xj XV \{i,j} où
XV \{i,j} représente toutes les autres variables sauf Xi , Xj ; ie

P(Xi , Xj |XV \{i,j} ) = P(Xi |XV \{i,j} )P(Xj |XV \{i,j} ).

Une formulation équivalente et que l’on utilise fréquemment est

P(Xi |Xj ; XV \{i,j} ) = P(Xi |XV \{i,j} ).

Exemples. • Réseaux bayésiens (modèle graphique dirigé). Ex : Chaı̂nes de

Markov, ou chaı̂nes de Markov cachées (voir Figure 4.3).

• Champs de Markov (modèle non dirigé).

• Modèles graphiques gaussiens (modèle non dirigé).

44
S1 ··· Sk−1 Sk Sk+1 ··· Sn

X1 ··· Xk−1 Xk Xk+1 ··· Xn

S1 ··· Sk−1 Sk Sk+1 ··· Sn

X1 ··· Xk−1 Xk Xk+1 ··· Xn

Figure 4.3 – Graphe acyclique dirigé (haut) et graphe moral (bas) correspondant
à un modèle de Markov caché.

Remarques. • Attention : la terminologie modèle graphique n’a rien à voir

avec des données organisées sous forme de graphes. Les variables aléatoires Xi
ne traduisent pas (a priori) des interactions entre des entités. Le graphe est
un objet abstrait qui structure la dépendance entre les variables aléatoires.
• Si P se factorise selon un DAG G, alors G n’est pas unique en général.

Ex : sans contrainte sur P, on a P(X1 , X2 , X3 ) = P(X3 |X1 , X2 )P(X2 |X1 )P(X1 ) =

P(Xσ(3) |Xσ(1) , Xσ(2) )P(Xσ(2) |Xσ(1) )P(Xσ(1) ), pour toute permutation σ (voir
Figure 4.4).

σ(1)

σ(2) σ(3)

Figure 4.4 – DAG qui factorise n’importe quelle distribution sur 3 variables. Ici σ
est n’importe quelle permutation de {1, 2, 3}.

Dans un modèle graphique, lorsque la structure de dépendance est représentée

par un graphe acyclique dirigé, on construit le graphe moral associé au DAG G.
C’est un graphe non dirigé, qui est obtenu à partir de G en mariant les parents
(i.e. on relie les parents par des arêtes) puis en retirant les directions des arêtes (voir
Figure 4.3 pour un exemple dans le cas des chaı̂nes de Markov cachées). Lorsque le
graphe G est non dirigé, il est égal à son graphe moral.

Proposition 4.1 (Propriétés d’indépendance). Dans un modèle graphique caractérisé

par un graphe G = (V, E), on a
• Si G est un DAG, alors conditionnellement à ses parents (dans G), une va-

riable est indépendante de ses non-descendants (dans G). Autrement dit, si

45
on note desc(Xi , G) l’ensemble des descendants de Xi dans G et si K est un
sous-ensemble de V tel que K ∩ desc(Xi , G) = ∅, alors

P(Xi |pa(Xi , G), {Xk }k∈K ) = P(Xi |pa(Xi , G)).

• Soient I, J, K des sous ensembles disjoints de V . Alors dans le graphe moral

associé à G, si tous les chemins de I à J passent par K, alors {Xi }i∈I ⊥⊥
{Xj }j∈J {Xk }k∈K .
Exemple . On considère le DAG et le graphe moral associé représentés à la Fi-
gure 4.5. On a par exemple
• X1 et X3 sont indépendantes ;

• Sachant X2 , les variables X1 et X3 ne sont pas indépendantes ;

• Sachant X2 , la variable X5 est indépendante de X1 , X3 , X4 ;

• X2 est indépendante de X6 sachant X5 ;

• Sachant X5 , la variable X6 est indépendante de X1 , X2 , X3 , X4 ;

• X1 est indépendante de X4 sachant X2 ;

• ...

X1 X4 X1 X4

X2 X2

X3 X5 X6 X3 X5 X6

Figure 4.5 – Exemple de DAG (gauche) et graphe moral associé (droite).

Exemple d’application. On se place dans le modèle de chaı̂ne de Markov caché

illustré à la Figure 4.3. Par conditionnement, on peut écrire

P(S1 , . . . , Sn |X1 , . . . , Xn ) = P(Sn |Sn−1 , . . . , S1 , X1 , . . . Xn )P(Sn−1 , . . . , S1 |X1 , . . . Xn ).

D’après le graphe moral (ou le DAG), on a

P(Sn |Sn−1 , . . . , S1 , X1 , . . . Xn ) = P(Sn |Sn−1 , Xn )

et ainsi

P(S1 , . . . , Sn |X1 , . . . , Xn ) = P(Sn |Sn−1 , Xn )P(Sn−1 , . . . , S1 |X1 , . . . Xn )

On procède récursivement en utilisant la propriété suivante (qui découle du graphe

moral ou du DAG)

P(Sk |Sk−1 , . . . , S1 , X1 , . . . Xn ) = P(Sk |Sk−1 , Xk , . . . Xn )

46
et on obtient au final
n
Y
P(S1 , . . . , Sn |X1 , . . . , Xn ) = P(Sk |Sk−1 , Xk , . . . Xn ) × P(S1 |X1 ).
k=2

Ainsi, la loi des variables latentes sachant les observations est celle d’une chaı̂ne de
Markov (inhomogène). La forme factorisée de cette loi la rend aisément manipulable.

Retour sur les modèles à variables latentes pour graphes. L’algorithme

EM requiert de pouvoir calculer facilement la loi des variables latentes sachant les
observations. Nous allons voir sur la Figure 4.6 pourquoi cette distribution n’a pas
une structure simple. En effet, la figure de gauche montre le DAG associé à un
modèle de graphes avec variables latentes et à droite, son graphe moral associé.
Dans ce dernier, on voit que sachant les observations, on a toujours des dépendances
entre les variables Zi (présence de chemins entre Zi et Zj que l’on ne peut pas
bloquer avec les variables observées). Ainsi, la distribution des Zi sachant les

Aij n’est pas factorisée ! (Alors que c’est le cas pour un modèle de mélange, pour les
HMMs, etc). C’est cette propriété qui empêche d’appliquer l’algorithme EM ici.

A12 A12

Z1 Z2 Z1 Z2

A13 Z3 A23 A13 Z3 A23

Figure 4.6 – À gauche : DAG d’un modèle à variable latentes pour un graphe
(n = 3). À droite : graphe moral associé.

Nous allons nous intéresser à une stratégie d’approximation variationnelle qui

permet de pallier ce problème.

4.4.3 Estimation des paramètres par approximation varia-

tionnelle de EM
La raison qui empêche l’utilisation de l’algorithme EM dans notre cadre est le
fait que la loi des variables latentes {Zi }i sachant les observations {Aij }ij n’est
pas factorisée. Une solution naturelle consiste à remplacer cette loi par la meilleure
approximation possible dans la classe des lois factorisées. C’est le principe de l’ap-
proximation variationnelle. Pour l’expliquer, nous allons d’abord revenir sur le prin-
cipe détaillé de l’algorithme EM, en le présentant avec un point de vue légèrement
différent.

47
La log-vraisemblance des observations peut se décomposer sous la forme
LA (θ) := log Pθ (A) = log Pθ (A, Z) − log Pθ (Z|A).
Si Q est une distribution de probabilité sur l’ensemble des variables {Zi }i , on peut
prendre l’espérance par rapport à Q de chaque côté de l’égalité précédente et on
obtient
LA (θ) = EQ (log Pθ (A, Z)) − EQ (log Pθ (Z|A)).
En notant H(Q) l’entropie de la loi Q et KL(QkPθ (Z|A)) la divergence de Kullback-
Leibler entre les lois Q et Pθ (Z|A), c’est-à-dire
X
H(Q) = − Q(z) log Q(z) = −EQ (log Q(Z))
z
X Q(z) Q(Z)
KL(QkPθ (Z|A)) = Q(z) log = EQ log ,
z
Pθ (z|A) Pθ (Z|A)
on obtient alors l’égalité suivante
LA (θ) = EQ (log Pθ (A, Z)) + H(Q) + KL(QkPθ (Z|A)). (4.3)
Partant de cette relation (4.3), l’algorithme EM (qui cherche à maximiser LA (θ))
consiste à itérer les deux étapes suivantes. À partir de la valeur courante du pa-
ramètre θ(t) , on effectue
• E-step : on maximise la quantité EQ (log P (t) (A, Z)) + H(Q) par rapport à
θ
Q. D’après (4.3), puisque LA (θ (t) ) ne dépend pas de Q, c’est équivalent à
minimiser KL(QkPθ(t) (Z|A)) par rapport à Q. La solution optimale est donc
la loi conditionnelle Pθ(t) (Z|A) pour la valeur courante du paramètre θ (t) ;
• M-step : on garde à présent Q fixé et on maximise la quantité EQ (log Pθ (A, Z))+

H(Q) par rapport à θ. Puisque Q ne dépend pas de θ, c’est équivalent à

maximiser l’espérance conditionnelle EQ (log Pθ (A, Z)) par rapport à θ. Avec
notre choix de Q, cette quantité est exactement l’espérance conditionnelle de
la log-vraisemblance des données complètes, sachant les observations, sous le
paramètre courant, ie Eθ(t) (log Pθ (A, Z)|A) que l’on maximise en θ. En effet,
on a
X X
EQ (log Pθ (A, Z)) = Q(Z) log Pθ (A, Z) = Pθ(t) (Z|A) log Pθ (A, Z)
Z Z

=Eθ(t) (log Pθ (A, Z)|A).

Comme on l’a vu précédemment, maximiser cette quantité par rapport à θ
va automatiquement accroı̂tre la log-vraisemblance des observations LA (θ)
parce que le terme de divergence de Kullback-Leibler est égal à 0 ici par
l’étape E !

48
Lorsque la vraie loi Pθ (Z|A) n’est pas manipulable (par exemple parce que ce
n’est pas une loi factorisée), la solution exacte du E-step ne peut pas être calculée.
Dans l’approximation variationnelle, au lieu de calculer la solution exacte à l’étape
E, on va chercher une solution optimale dans une classe restreinte de distributions,
par exemple dans la classe des lois factorisées (et l’étape M reste inchangée mais
utilise la solution approchée Q de l’étape dite VE pour variational-expectation).
Au final, on peut remarquer en reprenant (4.3) et en utilisant le fait qu’une
divergence de Kullback-Leibler est toujours positive (par l’inégalité de Jensen), qu’on
a la borne inférieure suivante
LA (θ) ≥ EQ (log Pθ (A, Z)) + H(Q) := J (Q, θ). (4.4)
Ainsi, l’approximation variationnelle optimise une borne inférieure de la log-vraisemblance
(J (Q, θ) optimisée d’abord en Q puis en θ). On n’a aucune garantie d’approcher
l’estimateur de maximum de vraisemblance avec cette procédure. En général, on ne
l’approche d’ailleurs pas. Dans le cas particulier du SBM, cette procédure fonctionne
cependant très bien empiriquement et il existe également des résultats théoriques
qui justifient son utilisation.
Ainsi, dans le cas du modèle à blocs stochastiques, on prend donc pour Q une
loi factorisée (i.e. marginales indépendantes)
n Q
n Y
Z
Y Y
Q(Z) = Qi (Zi ) = τiq iq ,
i=1 i=1 q=1
P
où τiq = Qi (Zi = q) = EQ (Ziq ), avec q τiq = 1 pour tout i.
L’approximation variationnelle est parfois appelée approximation champ moyen
parce que tout se passe comme si dans l’approximation de la loi conditionnelle de Zi
sachant les observations, toutes les autres variables {Zjq }j6=i,q étaient fixées à leur
moyennes (conditionnelles) τjq . Les paramètres τiq sont appelés paramètres variation-
nels. Ils représentent l’approximation de la probabilité que le nœud i appartienne au
groupe q. À la fin de l’algorithme VEM (pour variational expectation maximization),
on peut utiliser un maximum a posteriori pour retrouver les groupes latents et faire
la classification
∀1 ≤ i ≤ n, Ẑi = Argmax τiq .
1≤q≤Q

Calculs dans le cas SBM. On va entrer dans les détails de l’implémentation de

VEM dans le cas du SBM. On reprend l’expression (4.1) de la log-vraisemblance des
données complètes
Q n
X X X X
log Pθ (A, Z) = Ziq log πq + Ziq Zj` log F (Aij ; γq` ).
q=1 i=1 1≤q,`≤Q i,j

49
En prenant l’espérance par rapport à la loi Q de cette quantité, puisque EQ (Ziq Zj` ) =
τiq τj` (propriété d’indépendance sous la loi Q) et EQ (Ziq ) = τiq (par définition), on
obtient l’expression suivante
Q n
X X X X
EQ (log Pθ (A, Z)) = τiq log πq + τiq τj` log F (Aij ; γq` ).
q=1 i=1 1≤q,`≤Q i,j

Ainsi, la quantité qui nous intéresse est

J (Q, θ) = EQ (log Pθ (A, Z)) + H(Q)

Q n π
X X q
X X
= τiq log + τiq τj` log F (Aij ; γq` ),
q=1 i=1
τiq
1≤q,`≤Q i,j

et on alterne une maximisation de J par rapport aux τiq avec une maximisation par
rapport aux paramètres θ = (π, γ).
Ainsi, à l’étape E, on maximise cette quantité par rapport aux paramètres varia-
tionnels τiq pour une valeur θ fixée. En cherchant les points critiques (ne pas oublier
P
les contraintes ∀i, q τiq = 1), on obtient que la solution τ̂ = {τ̂iq }i,q vérifie une
équation de point fixe
Q
YY
∀1 ≤ i ≤ n, ∀1 ≤ q ≤ Q, τ̂iq ∝ πq [F (Aij ; γq` )]τ̂j` ,
j `=1

où ∝ signifie ’proportionnel à’ (la constante est obtenue à partir de la contrainte de
oi de probabilité !).
À l’étape M, on doit maximiser en θ = (π, γ) cette même quantité. Concernant
la maximisation par rapport aux πq , on obtient facilement
n
1X
∀1 ≤ q ≤ Q, π̂q = τiq .
n i=1
P
(Ne pas oublier la contrainte q π̂q = 1). Pour ce qui est de la maximisation en les
γq` , cela dépend de la famille de lois F (·; γ) que l’on considère. Prenons le cas simple
d’un graphe binaire (non dirigé) où F (·; γ) est une loi de Bernoulli de paramètre α.
Alors on doit maximiser par rapport aux αq` la quantité,
A
X X
τiq τj` log[αq`ij (1 − αq` )1−Aij ]
1≤q,`≤Q i<j
X X h i
= τiq τj` Aij log αq` + (1 − Aij ) log(1 − αq` ) .
1≤q,`≤Q i<j

50
La solution s’obtient simplement avec
P
i6=j τiq τj` Aij
α̂q` = P .
i6=j τiq τj`

Il s’agit de la fréquence moyenne des arêtes entre les groupes q, `. En fait, puisque
chaque τiq estime la probabilité que le nœud i appartienne au groupe q, on estime les
paramètres d’interaction γql en utilisant les interactions Aij pondérées par le poids
τiq τj` . Par exemple si on veut estimer la valeur moyenne de la loi conditionnelle
G(·; ηq` ), notée mq` on trouvera en cherchant les points critiques de la quantité à
maximiser P
i6=j τiq τj` Aij
m̂q` = P .
i6=j τiq τj` 1Aij 6=0

(Attention ici pour estimer la moyenne de la loi conditionnelle G(·; ηq` ), on ne prend
en compte que les arêtes présentes, c’est-à-dire Aij 6= 0).

4.4.4 Sélection de modèles

La plupart du temps le nombre de classes Q est inconnu et doit être estimé
à partir des données. À partir de l’algorithme VEM, on peut utiliser le critère ICL
(integrated classification likelihood). C’est un critère pénalisé, analogue du BIC mais
au lieu de prendre la log-vraisemblance des observations (qui est inconnue ici) on
utilise l’espérance de log-vraisemblance des données complètes sous l’approximation
variationelle. Ainsi, pour chaque valeur du nombre de groupes Q, on obtient via
l’algorithme VEM ajusté avec Q groupes, la quantité

EQ̂ (log P(A, Z; θ̂)).

Ici, Q̂, θ̂ sont les quantités obtenues à la fin des itérations de VEM (ou plus précisément
à la fin de la meilleure itération de VEM quand on a fait plusieurs initialisations, ce
qui est recommandé).
Là encore, l’expression de la pénalité va dépendre du choix de la famille de lois
F (·; γ) que l’on considère. La forme générale du critère est

1 1 n(n − 1)
ICL(Q) := EQ̂ (log P(A, Z; θ̂)) − (Q − 1) log n − dim(γ) log ,
2 2 2
où dim(γ) est la dimension du paramètre γ = (α, η).
Par exemple, dans le cas d’un graphe binaire, on a γ = (αql )q,` est de dimension
Q(Q + 1)/2. Si F (·; γ) est le mélange entre une Dirac en 0 et une loi de Poisson
(tronquée en 0), de paramètre η, on obtient γ = (αq` , ηq` )q,` qui est de dimension

51
Q(Q + 1). Si par souci de parcimonie on a imposé que les paramètres de densité du
graphe αq` sont constants pour tous les groupes q, ` alors on a γ = (α; (ηq` )q,` ) qui
est de dimension 1 + Q(Q + 1)/2.
Noter que dans l’expression de l’ICL, le premier terme de pénalité 1/2(Q−1) log n
pénalise pour le paramètre π = (πq )1≤q≤Q (de dimension Q − 1) et qui porte sur
n variables Z1 , . . . , Zn ; tandis que le second terme vient pénaliser le paramètre
d’interaction γ et se fonde lui sur n(n − 1)/2 observations, à savoir les {Ai,j }i<j .
Finalement, on va sélectionner le nombre de groupes Q en se fixant une borne
Qmax et en utilisant
Q̂ = Argmax ICL(Q).
1≤Q≤Qmax

Aucun résultat théorique n’existe sur les propriétés asymptotiques de ce critère, mais
ses performances empiriques sont très bonnes.

52
Bibliographie

Albert, R. and A.-L. Barabási (2002, Jan). Statistical mechanics of complex net-
works. Rev. Mod. Phys. 74, 47–97.

Berge, C. (1976). Graphs and hypergraphs (revised ed.). North-Holland Publishing

Co., Amsterdam-London ; American Elsevier Publishing Co., Inc., New York.
Translated from the French by Edward Minieka, North-Holland Mathematical
Library, Vol. 6.

Bishop, C. M. (2006). Pattern recognition and machine learning. Information Science

and Statistics. Springer, New York.

Chatterjee, S. and P. Diaconis (2013, 10). Estimating and understanding exponential

random graph models. Ann. Statist. 41 (5), 2428–2461.

Erdős, P. and T. Gallai (1961). Graphs with points of prescribed degree. (Graphen
mit Punkten vorgeschriebenen Grades.). Mat. Lapok 11, 264–274.

Handcock, M., A. Raftery, and J. Tantrum (2007). Model-based clustering for so-
cial networks. Journal of the Royal Statistical Society : Series A (Statistics in
Society) 170 (2), 301–54.

Hoff, P., A. Raftery, and M. Handcock (2002). Latent space approaches to social
network analysis. J. Amer. Statist. Assoc. 97 (460), 1090–98.

Kolaczyk, E. D. (2009). Statistical Analysis of Network Data : Methods and Models.

Springer.

Kolaczyk, E. D. and G. Csárdi (2014). Statistical analysis of network data with R.

Use R ! Springer, New York.

Lauritzen, S. L. (1996). Graphical models, Volume 17 of Oxford Statistical Science

Series. The Clarendon Press, Oxford University Press, New York. Oxford Science
Publications.

53
Ng, A. Y., M. I. Jordan, and Y. Weiss (2001). On spectral clustering : Analysis and
an algorithm. In Advances in neural information processing systems, pp. 849–856.
MIT Press.

Rohe, K., S. Chatterjee, and B. Yu (2011). Spectral clustering and the high-
dimensional stochastic blockmodel. Annals of Statistics 39 (4), 1878–1915.

Schweinberger, M. and M. 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–676.

von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Compu-

ting 17 (4), 395–416.

Zhang, Y., E. Kolaczyk, and B. Spencer (2015). Estimating network degree dis-
tributions under sampling : An inverse problem, with applications to monitoring
social media networks. The Annals of Applied Statistics 9 (1), 166–199.

Vous aimerez peut-être aussi

Analyse Statistique des Graphes
Pas encore d'évaluation
Analyse Statistique des Graphes
10 pages
Cours THG 2024 2025
Pas encore d'évaluation
Cours THG 2024 2025
20 pages
Exercices sur l'Optimisation des Graphes
Pas encore d'évaluation
Exercices sur l'Optimisation des Graphes
198 pages
Introduction aux graphes et terminologie
Pas encore d'évaluation
Introduction aux graphes et terminologie
39 pages
Cours TG LSTI
Pas encore d'évaluation
Cours TG LSTI
68 pages
Graphes: Théorie et Applications
Pas encore d'évaluation
Graphes: Théorie et Applications
19 pages
Introduction à l'algorithmique des graphes
Pas encore d'évaluation
Introduction à l'algorithmique des graphes
24 pages
Introduction à la théorie des graphes
100% (3)
Introduction à la théorie des graphes
47 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
47 pages
Chapitre 1 Introduction
Pas encore d'évaluation
Chapitre 1 Introduction
41 pages
Chapitre 2
Pas encore d'évaluation
Chapitre 2
37 pages
Théorie des Graphes: Cours et Concepts
100% (1)
Théorie des Graphes: Cours et Concepts
63 pages
Cours sur les graphes pour BTS SIO
Pas encore d'évaluation
Cours sur les graphes pour BTS SIO
40 pages
Introduction au graphe partiel
100% (1)
Introduction au graphe partiel
23 pages
Introduction aux Graphes et Coloration
Pas encore d'évaluation
Introduction aux Graphes et Coloration
57 pages
Theorie Graphe
Pas encore d'évaluation
Theorie Graphe
42 pages
Reconnaissance et Applications des Graphes Parfaits
Pas encore d'évaluation
Reconnaissance et Applications des Graphes Parfaits
25 pages
Théorie des Graphes : Concepts Clés
Pas encore d'évaluation
Théorie des Graphes : Concepts Clés
47 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
53 pages
Graphe 2022 - 2023
Pas encore d'évaluation
Graphe 2022 - 2023
70 pages
Introduction à la Théorie des Graphes
Pas encore d'évaluation
Introduction à la Théorie des Graphes
45 pages
Introduction aux Graphes en Algorithmique
Pas encore d'évaluation
Introduction aux Graphes en Algorithmique
77 pages
Cours THG Complet PDF
100% (2)
Cours THG Complet PDF
76 pages
Digraphe et Représentation de Graphes
Pas encore d'évaluation
Digraphe et Représentation de Graphes
6 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
18 pages
Théorie des graphes : Concepts et définitions
Pas encore d'évaluation
Théorie des graphes : Concepts et définitions
30 pages
Graphe
Pas encore d'évaluation
Graphe
76 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
5 pages
Introduction à la Théorie des Graphes
Pas encore d'évaluation
Introduction à la Théorie des Graphes
14 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
34 pages
Théorie des Graphes pour Étudiants L3
Pas encore d'évaluation
Théorie des Graphes pour Étudiants L3
52 pages
Concepts de Base en Théorie des Graphes
Pas encore d'évaluation
Concepts de Base en Théorie des Graphes
5 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
18 pages
Cours de Recherche Opérationnelle - 1
Pas encore d'évaluation
Cours de Recherche Opérationnelle - 1
110 pages
Optimisation des Graphes en Informatique
Pas encore d'évaluation
Optimisation des Graphes en Informatique
33 pages
Introduction aux graphes et algorithmes
Pas encore d'évaluation
Introduction aux graphes et algorithmes
24 pages
Chap2 TheorieDesGraphes
Pas encore d'évaluation
Chap2 TheorieDesGraphes
12 pages
Théorie des graphes et applications
Pas encore d'évaluation
Théorie des graphes et applications
37 pages
Introduction aux graphes et applications
Pas encore d'évaluation
Introduction aux graphes et applications
63 pages
Introduction aux graphes en informatique
Pas encore d'évaluation
Introduction aux graphes en informatique
12 pages
Introduction À La Théorie Des Graphes by Zekrifa Djabeur Mohamed Seifeddine
Pas encore d'évaluation
Introduction À La Théorie Des Graphes by Zekrifa Djabeur Mohamed Seifeddine
236 pages
Cour Theorie Des Graphes AIT ABDESSELAM
Pas encore d'évaluation
Cour Theorie Des Graphes AIT ABDESSELAM
68 pages
1 - Notions Fondamentales de La Théorie Des Graphes
100% (1)
1 - Notions Fondamentales de La Théorie Des Graphes
15 pages
Théorie des Graphes pour Étudiants
Pas encore d'évaluation
Théorie des Graphes pour Étudiants
28 pages
Chap1 - Theorie Des Graphes
Pas encore d'évaluation
Chap1 - Theorie Des Graphes
21 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
30 pages
Théorie Des Graphes L3 Maths 2019
Pas encore d'évaluation
Théorie Des Graphes L3 Maths 2019
64 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
35 pages
Cours Graphes 2022 2023
Pas encore d'évaluation
Cours Graphes 2022 2023
35 pages
Algorithmique II PDF
Pas encore d'évaluation
Algorithmique II PDF
61 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
57 pages
Méthodes d'Optimisation en Logistique
Pas encore d'évaluation
Méthodes d'Optimisation en Logistique
30 pages
Introduction aux graphes en algorithmique
Pas encore d'évaluation
Introduction aux graphes en algorithmique
8 pages
Concepts fondamentaux des graphes
Pas encore d'évaluation
Concepts fondamentaux des graphes
10 pages
Détection de communautés dans les graphes
Pas encore d'évaluation
Détection de communautés dans les graphes
17 pages
Cours 1
Pas encore d'évaluation
Cours 1
27 pages
COURS 02 - Les Placements
Pas encore d'évaluation
COURS 02 - Les Placements
52 pages
Examen 2016 01 20 - Rattrapage
Pas encore d'évaluation
Examen 2016 01 20 - Rattrapage
5 pages
COURS 05 - Assurance Non Vie
Pas encore d'évaluation
COURS 05 - Assurance Non Vie
64 pages
Schémas Comptables en Assurance Vie
Pas encore d'évaluation
Schémas Comptables en Assurance Vie
30 pages
Examen 2016 12 13
Pas encore d'évaluation
Examen 2016 12 13
10 pages
COURS 01 - Introduction
Pas encore d'évaluation
COURS 01 - Introduction
34 pages
Cours 04 - Paf PGG
Pas encore d'évaluation
Cours 04 - Paf PGG
51 pages
Examen 2016 01 06
Pas encore d'évaluation
Examen 2016 01 06
6 pages
COURS 02 - Les Placements
Pas encore d'évaluation
COURS 02 - Les Placements
52 pages
Structures de données : Graphes et Arbres
Pas encore d'évaluation
Structures de données : Graphes et Arbres
57 pages
Propriétés et algorithmes des arbres
Pas encore d'évaluation
Propriétés et algorithmes des arbres
17 pages
Theorie Des Graphes 3
100% (3)
Theorie Des Graphes 3
19 pages
Quelques Exemples de Graphes
Pas encore d'évaluation
Quelques Exemples de Graphes
6 pages
Houndete Alfred 2002 Memoire
Pas encore d'évaluation
Houndete Alfred 2002 Memoire
85 pages
5.les Graphes en Python - 2022 - Imprimerb
Pas encore d'évaluation
5.les Graphes en Python - 2022 - Imprimerb
62 pages
Exercices de théorie des graphes
Pas encore d'évaluation
Exercices de théorie des graphes
2 pages
CH4 Représentations Non Graphiques D'un Graphe
Pas encore d'évaluation
CH4 Représentations Non Graphiques D'un Graphe
32 pages
IX. Coloration
Pas encore d'évaluation
IX. Coloration
16 pages
NOTES DE COURS INTRO AUX RESEAUX INFOS UNILU - Corrigé
Pas encore d'évaluation
NOTES DE COURS INTRO AUX RESEAUX INFOS UNILU - Corrigé
164 pages
Optimisation des Réseaux de Graphes
Pas encore d'évaluation
Optimisation des Réseaux de Graphes
2 pages
Chap 8 23 24 Graphe
Pas encore d'évaluation
Chap 8 23 24 Graphe
15 pages
Chap3 - Theorie Des Graphes
Pas encore d'évaluation
Chap3 - Theorie Des Graphes
16 pages
TG L2FSI Chapitre4 2019
Pas encore d'évaluation
TG L2FSI Chapitre4 2019
14 pages
NotesDeCoursRO Partie 3
Pas encore d'évaluation
NotesDeCoursRO Partie 3
20 pages
Graphes et Arbres : Concepts Clés
Pas encore d'évaluation
Graphes et Arbres : Concepts Clés
20 pages
Modélisation de Réseaux Sociaux Simples
Pas encore d'évaluation
Modélisation de Réseaux Sociaux Simples
3 pages
Relations binaires et d'ordre expliquées
Pas encore d'évaluation
Relations binaires et d'ordre expliquées
11 pages
Slides Coloration
Pas encore d'évaluation
Slides Coloration
33 pages
Introduction à la théorie des graphes
Pas encore d'évaluation
Introduction à la théorie des graphes
14 pages
Management de Projet - MPM
Pas encore d'évaluation
Management de Projet - MPM
44 pages
Nomad Education
Pas encore d'évaluation
Nomad Education
1 page
PDF Cours Java FX Compress
Pas encore d'évaluation
PDF Cours Java FX Compress
126 pages
Graphe
Pas encore d'évaluation
Graphe
19 pages
Arbres Couvrants Minimaux et Algorithmes
Pas encore d'évaluation
Arbres Couvrants Minimaux et Algorithmes
19 pages
Théorèmes et Propriétés des Arbres
Pas encore d'évaluation
Théorèmes et Propriétés des Arbres
11 pages
Etud - Fiche de Travaux de Recherche
Pas encore d'évaluation
Etud - Fiche de Travaux de Recherche
12 pages
SRHC TD1
Pas encore d'évaluation
SRHC TD1
2 pages
Chap08 Les Graphes - Parcours
Pas encore d'évaluation
Chap08 Les Graphes - Parcours
12 pages
Concepts de graphes et arbres couvrants
Pas encore d'évaluation
Concepts de graphes et arbres couvrants
43 pages

Analyse statistique des graphes

Transféré par

Analyse statistique des graphes

Transféré par

Notes de cours : Analyse statistique de graphes

M2 Université Pierre et Marie Curie

Warning : ce document contient certainement des erreurs et des imprécisions.

1 Introduction aux graphes 4

2 Statistiques descriptives sur les graphes 11

3 Spectral Clustering : détection de communautés 22

4 Modèles de graphes aléatoires et classification des nœuds 34

Introduction aux graphes

Quelques références bibliographiques (ces notes en font un usage immodéré)

• Chapitres 1 et 2 : Albert and Barabási (2002) ;

• Chapitre 3 sur le spectral clustering : von Luxburg (2007).

1.1 Les réseaux / Les graphes

Exemple de réseaux ’physiques’. Internet (routeurs et ordinateurs connectés par

Dans la suite, on s’intéresse uniquement aux graphes simples : un ensemble de

Vocabulaire. Un graphe G = (V, E) est composé d’un ensemble V = {1, . . . , n}

e = {u, v} ∈ E sont telles que u ∈ V1 , v ∈ V2 . Tout ce qui suit se généralise

Un cycle est un chemin d’un nœud i à lui même (dans G).

orienté entre i et j. Il se peut alors qu’il existe un chemin orienté de i vers j

Preuve. On vérifie facilement que si |E| = 0 alors il y a n composantes connexes.

1.2 Représentation visuelle

1.3 Stockage informatique

5x5x5 Lattice Blog Network

Alternatively, motivated by the fact that it is poss

pour manipuler les matrices creuses).

1.3.2 Les listes d’arêtes

1.4 Le modèle G(n, p) et graphes remarquables

modèles sont équivalents pour n grand.

Simulation de graphes G(n, p). En principe, il suffit de générer n(n − 1)/2

Exemple de graphes réguliers. Grille Z2 , le graphe complet Kn est un graphe

Statistiques descriptives sur les

Les statistiques permettent de résumer l’information contenue dans un graphe,

Lorsque n → +∞ et p → 0 avec np → λ > 0 alors la loi B(n−1, p) est approchée

2.1.2 Modèles de configuration

En prenant di pas trop grand et C ' 2|E| on obtient E(Di ) ' di .

ni simplement simulable : si on tire une suite de Di comme indiqué, on a peu

ching (voir Algorithme 2.1) soit un algorithme re-branchement (rewiring ou

// Test graphe simple :

biaisés de l’ensemble des graphes possibles.

L’algorithme de re-branchement est plus efficace mais il fonctionne uniquement

2.1.3 Corrélations entre degrés

2.2 Densité, clustering, transitivité

Figure 2.1 – Exemple de graphe.

Définition. La densité d’un graphe G = (V, E) est définie par

Cette quantité, comprise entre 0 et 1, traduit à quel point le graphe G ressemble

Définition. On note Di le degré du nœud i et |Ei | le nombre d’arêtes qui connectent

Définition (transitivité). On définit le coefficient de transitivité par

Remarque. Dans la définition précédente, par triplet de nœuds connectés, on en-

arêtes {i, j} ∈ E telles que i, j ∈ V 0 .

Un motif m d’un graphe G est un sous-graphe induit de G. Chercher les oc-

2.4 Distance, diamètre

Cette quantité n’est finie que pour les graphes connexes.

Propriété petit monde (small-world property). La propriété  petit monde  tra-

2.5 Autres descripteurs

Représentations visuelles avancées. Souvent, les données ne sont pas unique-

2.6 Échantillonnage dans les graphes

2.6.1 Exemples d’échantillonnages dans les graphes

Échantillonnages par sous-graphe induit et sous-graphe incident. L’échan-

Exemples. On a une base de données d’échanges d’email ou d’appels téléphoniques

incidentes aux mêmes nœuds.

Échantillonnages ’link tracing’. Le principe général est le suivant : on tire n

L’échantillonnage Boule de neige (Snowball sampling) est un échantillonnage

Exemples. Certains sondages en sciences sociales ; Web crawling ; . . .

Échantillonnages ’Traceroute sampling’. On tire un ensemble de nœuds ’sour-

2.6.2 Exemple d’impact de l’échantillonnage : estimation

et le vrai nombre Nk? de nœuds de degré k s’estime par N̂k = Nk n? /n

Spectral Clustering : détection de

Ce chapitre utilise en grande partie l’article de von Luxburg (2007).

• qui n’est pas fondée sur un modèle probabiliste ;

• mais qui a l’avantage de fonctionner sur de très grands graphes.

3.1 Graphes de similarité

3.1.2 Différents graphes de similarité

Définition (Graphe de similarité dense.). On peut définir la similarité entre les

Définition (Graphe de -voisinage.). On fixe un seuil  > 0 et on connecte tous les

Définition (Graphe des k plus proches voisins.). On commence par définir un

proches voisins mutuels).

promis entre le graphe dense et le graphe de -voisinage : étape de seuillage

Propriété petit monde (small-world property). La propriété petit monde tra-

Définition (Graphe de -voisinage.). On fixe un seuil > 0 et on connecte tous les

promis entre le graphe dense et le graphe de -voisinage : étape de seuillage