Notes de cours : Analyse statistique de graphes

Chapitre 1

Catherine Matias
avec des ajouts de Tabea Rebafka

M2 de mathématiques
Sorbonne Université
2018

Warning : ce document contient certainement des erreurs et des imprécisions.

N’hésitez pas à me les signaler.
Table des matières

1 Introduction aux graphes 3

1.1 Graphes, réseaux et données d’interaction . . . . . . . . . . . . . . . . . . . 3
1.2 Représentation visuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Stockage informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Les matrices d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Les listes d’arêtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Le modèle G(n, p) et graphes remarquables . . . . . . . . . . . . . . . . . . 8

2
Chapitre 1

Introduction aux graphes

Quelques références bibliographiques (ces notes en font un usage immodéré)

• Générales : Kolaczyk (2009); Kolaczyk and Csárdi (2014) ;

• Chapitres 1 et 2 : Albert and Barabási (2002); Luke (2015) ;

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

1.1 Graphes, réseaux et données d’interaction

Tout au long de cours nous nous intéressons à l’analyse de données d’interaction entre
des individus, ou plus généralement entre des entités. Les entités qui interagissent ou
communiquent entre eux ainsi que ce qui est considéré comme une interaction varient
beaucoup et dépendent du contexte d’application. Par exemple, sur facebook les entités
sont les membres du site et une interaction est le fait que deux membres sont amis sur
facebook. Quant trafic aérien, les entités sont les aéroports et une interaction est un vol
direct d’un aéroport vers l’autre. L’ensemble d’entités en interaction est dit réseau. Sa
représentation mathématique est dite graphe.
Exemple de réseaux ’physiques’. Internet (routeurs et ordinateurs connectés par des
câbles ethernet ou des liaisons wifi) ; réseau électrique (câbles reliant des prises) ; réseau
routier entre des villes ; réseau aérien entre aéroports ; réseau métro. . .
Exemple de réseaux virtuels. World wide web (nœuds sont les pages html et les arêtes
sont les hyperliens) ; réseau d’amis Facebook, LinkedIn, Twitter ; réseau de co-publications
de chercheurs ; food-web en écologie ; réseau acheteur-produit chez Amazon (les entités sont
les utilisateurs et les produits, une interaction est l’achat d’un produit par un utilisateur)
...
Dans la suite, on s’intéresse uniquement aux graphes simples : un ensemble de nœuds
(ou sommets), liés par des arêtes (ou arcs), sans liens doubles ni boucles.

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

nœuds (vertices en anglais) et d’un ensemble E d’arêtes (edges en anglais) avec {i, j} ∈ E

3
s’il y a une arête entre les nœuds i et j dans le graphe. On dit que l’arê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’arêtes |E| est
appelé taille du graphe.
Un graphe est dirigé (ou orienté) lorsque ses arêtes le sont i.e. lorsque l’arête (i, j) est
différente de l’arête (j, i). Il est non dirigé sinon.
Les graphes simples n’ont pas de boucles (i.e. (i, i) n’est jamais une arête). Ils peuvent
être binaires : une arête est présente (1) ou absente (0), ou valués : les arêtes présentes
sont alors munies d’une valeur (poids). Noter qu’un graphe binaire est un cas particulier
de graphe valué où toutes les arêtes présentes ont le poids 1.
n


Remarques. • Un graphe simple sur n nœuds possède au plus
2 = n(n − 1)/2
n


arêtes s’il est non dirigé et 2 2 = n(n − 1) arêtes s’il est dirigé.
• Les graphes biparties sont tels que V = V1 ∪ V2 avec V1 ∩ V2 = ∅ et les arêtes

e = {u, v} ∈ E sont telles que u ∈ V1 , v ∈ V2 . P. ex. le réseau acheteur-produit chez

Amazon. Tout ce qui suit se généralise facilement à ce cas. Les graphes simples que
l’on considère ici sont parfois dits uniparties.

À partir de mesures d’interactions {Aij }1≤i,j≤n entre individus, on peut définir une
valeur symétrisée et normalisée des interactions à partir du coefficient de Jaccard.

Définition. (Jaccard coefficient ou index de Jaccard). Il s’agit d’une mesure de similarité

symétrique et normalisée entre éléments, définie à partir de valeurs d’interactions Aij entre
les individus, par
Aij + Aji
JACij = JACji = P P .
k6=j Aik + k6=i Ajk

Cet index sert parfois à construire des graphes valués et non dirigés entre un ensemble
d’entités.

Définition (Chemins, connexité, cycles). Un chemin dans G = (V, E) non orienté entre
i, j ∈ V est une suite d’arêtes e1 , . . . , ek ∈ E telle que
• pour tout 1 ≤ t ≤ k − 1, les arê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 à lui mê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 à vj .
Un graphe G = (V, E) est dit connexe s’il possède une unique composante connexe
(i.e. pour tous i, j ∈ V , il existe un chemin de i à j dans G).
Dans un graphe orienté, on peut définir la notion de chemin orienté entre i et j. Il
se peut alors qu’il existe un chemin orienté de i vers j sans chemin orienté de j vers i. De
même il peut exister un chemin de i vers j sans chemin orient de i vers j.
La connexité d’un graphe dirigé est définie à partir des chemins non dirigés.

4
 Pour des définitions plus détaillées cf. p.23 Kolaczyk and Csárdi (2014).

Proposition 1.1. Tout graphe peut être décomposé en un unique ensemble de composantes
connexes (maximales). Le nombre de composantes connexes d’un graphe est supérieur ou
égal à n − |E|.

Preuve. On vérifie facilement que si |E| = 0 alors il y a n composantes connexes. De

même si |E| = 1 on a exactement n − 1 composantes connexes. Par induction sur le
nombre d’arêtes : supposons que G = (V, E) est un graphe avec c composantes connexes
tel que c ≥ n − |E|. On ajoute une arête à G pour fabriquer G0 = (V, E 0 ) et on note c0
le nombre de composantes connexes de G0 . Alors soit c0 = c (l’arête ajoutée relie deux
nœuds qui sont déjà dans la même composante connexe), soit c0 = c − 1 (l’arête ajoutée
relie deux composantes connexes entre elles pour n’en cré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 vérifiée.

Définition (Voisinage, degrés). Dans un graphe G = (V, E) non orienté les voisins de
i ∈ V sont les nœuds j ∈ V tels que {i, j} ∈ E. On note le voisinage de i par

V(i) = {j ∈ V ; {i, j} ∈ E}.

Le degré 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.
Le degré moyen d’un graphe est défini par
1 X
d¯ = di .
|V |
i∈V

Si G est un graphe dirigé, on peut définir le degré sortant dout

i et le degré entrant
din
i du nœud i ainsi que les degrés moyens sortants par
1 X in 1 X out
d¯in := di = d¯out := di .
|V | |V |
i∈V i∈V

Notons que les degrés moyens sortants et entrants sont nécessairement égaux

d¯in = d¯out .

Preuve par raisonnement par récurrence sur les nombre d’arêtes |E|.
P
Proposition 1.2. Dans un graphe G = (V, E) non orienté on a i∈V di = 2|E|. En
particulier, la somme des degrés d’un graphe non orienté est toujours paire.

Preuve par raisonnement par récurrence sur les nombre d’arêtes |E|.
La suite des degrés (d1 , . . . , dn ) d’un graphe est très contrainte. En fait Erdős and Gallai
(1961) ont montré la propriété suivante (voir aussi Berge, 1976, Chapitre 6, Théorème 4).

5
Quitte à ré-ordonner (d1 , . . . , dn ) de sorte que d1 ≥ d2 ≥ · · · ≥ dn , une condition nécessaire
et suffisante pour que (d1 , . . . , dn ) soit la réalisation de la séquence des degrés d’un graphe
est que pour tout 1 ≤ k ≤ n − 1 on ait

k
X n
X
di ≤ k(k − 1) + min(k, di ).
i=1 i=k+1

1.2 Représentation visuelle

On représente les nœuds et les arêtes sans accorder d’importance à la position d’un
nœud dans l’espace. Les nœuds ont des labels qui peuvent ou non être spécifiés sur la
représentation.
Attention, la représentation visuelle d’un graphe est très trompeuse ! Les exemples de
la Figure 1.1 sont tirés du livre Kolaczyk and Csárdi (2014).
La question de la visualisation et de la représentation d’un graphe est donc très impor-
tante. Il faut garder à l’esprit que pour les grands graphes, la représentation est toujours
biaisée.

Remarque. Un graphe est dit planaire lorsque l’on peut le représenter dans le plan sans
qu’aucune arête n’en croise une autre. Dans ce cours, on ne s’intéresse pas à cette propriété.

1.3 Stockage informatique

1.3.1 Les matrices d’adjacence
Définition. Un graphe G = (V, E) binaire sur un ensemble V = {1, . . . , n} de nœuds
peut-être représenté par sa matrice d’adjacence (binaire) A = (Aij )1≤i,j≤n où
(
1 si {i, j} ∈ E,
Aij =
0 sinon.

Lorsque le graphe est non dirigé, la matrice A est symétrique. Si le graphe est simple on
pose Aii = 0 pour tout i. Si le graphe est valué, on peut considérer une matrice d’adjacence
valuée (
wij si l’arête est présente entre i et j et de poids wij ,
Aij =
0 sinon.

Proposition 1.3. Les degrés s’obtiennent à partir de la matrice d’adjacence via des
sommes en ligne ou en colonne
X X X
di = Aij (cas non dirigé) ; dout
i = Aij ; din
i = Aji .
j;j6=i j;j6=i j;j6=i

6
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=[Link]
of graph drawing de-
aer, is6by>of
notion definition
force forhighly
each uniform
plot(aidsblog, in>inthe
itsgraph
connectivity
vertex4layout=[Link])
title("Blogdepending, at the very least, on
Network")
og network is [Link] vertices Network")
7 >of title("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
[Link]=3,
1 > plot(g.l, [Link]=NA,
layout=[Link])
e=0.5)
2 > title("5x5x5 Lattice")
))
3 > plot(aidsblog, layout=[Link])
=[Link])
4 > title("Blog Network")
tice")
own in Fig. 3.2, we see that substantially more of the structure inherent to each
ayout=[Link])
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 is that of edge-crossings
of energy-placement throum
f the circle. Ordering of of the
vertex vertices
positions, around
ostensibly the circle
is definedis important
using expre w
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 [Link] Common ver
is typica
.2 Layouts using the method of Fruchterman and Reingold
or circularFigure
layouts henceordering
include the assertion by heredegree is thatanda graph
grouping
1.1 – Chaque ligne contient deux représentations différentes d’un même réseau
drawnby accor
co
be visually
ttributes. (tiré de Kolaczyk and Csárdi (2014)). En appealing. 3
haut : Cube {1, . . . , 5} , en bas un réseau de

Often more
lternatively,
blogs.
effective
motivated by the Methods
forfact that it based
creating isuseful ondrawings
possible multidimensional
to associate arethe layoutsscaling (MD
based
collection of
tice is much more with pleasing
anthe to the system
social eye
networkthan that of
literature, areandof this
snalogies
in springbetween
systems the relational
overall structure in graphs
energy, another commonthetype. Theam
forces
approach m
o the lowlayouts
nerating level of is edge-crossings
that One is a popular through
of energy-placement the
variant. center
Using An
methods. thisenergy,
layout,as a function
n physical
vertices
systems.
around 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 associating motivated by those
vertices
layout=[Link].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
7 the total system energy.
that ofsystem
ysical the blog network.
with minimum Common
3 > vertex
energy orderings
is typically
plot(aidsblog,in its most relaxed state, and
layout=[Link]
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 encodé 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 dirigé (matrice
symétrique).

Il peut s’avérer que cette représentation ne soit pas adaptée au stockage informatique
• si trop grand nombre de nœuds (matrice de taille n × n),

• si le graphe est très creux (on peut éventuellement utiliser des outils spécifiques pour

manipuler les matrices creuses). En effet, les grands graphes réels sont généralement
assez creux, car typiquement un individu n’interagit qu’avec une très petite partie
de l’ensemble d’individus dans le graphes.

1.3.2 Les listes d’arêtes

Lorsque la liste des nœuds est déjà connue, on peut se contenter de stocker les arêtes
du graphe. Attention, il est nécessaire d’indiquer le nombre total de nœuds du graphe,
sinon on ne connaı̂t pas les nœuds isolés.
Exemple . Reconstruire le graphe encodé comme indiqué 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 modèle G(n, p) et graphes remarquables

Un modèle de graphes aléatoires est une collection (finie ou dénombrable) G de
graphes et une loi de probabilité P sur cette collection G.
Le modèle de graphe aléatoire le plus simple est le modèle introduit dans les années
1950 par Erdös et Rényi. Il s’agit de la collection G(n, M ) de tous les graphes simples non
dirigés d’ordre n et de taille M , munie de la loi uniforme P sur cette collection. Ainsi, la
N


collection G(n, M ) contient M graphes différents, où N = n(n − 1)/2 et la probabilité
N


de chacun d’eux est 1/ M .
Une variante plus commune consiste à considérer la collection G(n, p) de graphes
simples non dirigés générés selon un modèle à deux paramètres : n le nombre de nœuds du
graphe et p ∈ (0, 1) la probabilité de connection de deux nœuds pris au hasard. C’est un
graphe dont toutes les arêtes Aij , 1 ≤ i < j ≤ n sont des variables i.i.d. de loi de Bernoulli
B(p).
Un réseau observé peut être considéré comme une réalisation de la variable aléatoire
G(n, p) ou de la variable G(n, M ) de loi comme ci-dessus.

8
 Souvent, on considère que p = pn peut varier avec n. (Sinon on a des graphes trop
denses pour modéliser les grands graphes réels). Lorsque M ∼ n2 pn , les deux modèles

sont équivalents pour n grand, car le nombre moyen d’arêtes dans un graphe G(n, p) est
donné par  
 
X X n
EG(n,p) [|E|] = E  Aij =
 E[Aij ] = p.
2
1<i<j<n 1<i<j<n

Le modèle G(n, p) d’Erdös-Rényi est un modèle mathématique très étudié, mais qui
s’ajuste mal aux réseaux observés. En revanche, l’idée de modéliser les arêtes par des va-
riables aléatoires permet de définir facilement d’autres modèles de graphes plus appropriés
pour l’analyse de graphes réels (cf. Chapitre 4). Dans la suite, on décrira les propriétés du
modèle G(n, p) au regard de celles des réseaux réels.

Simulation de graphes G(n, p). En principe, il suffit de générer n2 variables aléatoires

de Bernoulli de paramètre p. Lorsque n est grand et p = pn de l’ordre de 1/n, cette

procédure est très inefficace : l’espérance du degré 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 ).

Définition. Le graphe complet (ou clique) Kn est le graphe (non dirigé) sur n sommets
qui contient toutes les arêtes possibles entre ces sommets.

Ainsi, K2 est une simple arête entre deux nœuds, K3 est un triangle. Les sous-graphes
complets d’un graphe sont plus communément appelés cliques.

Définition. Un graphe dont tous les nœuds ont le même degré d est un graphe régulier
ou encore d–régulier.

Exemple de graphes réguliers. Grille Z2 est 4–régulier, le graphe complet Kn est

(n − 1)–régulier.
Les graphes réels sont rarement réguliers.

9
Bibliographie

Albert, R. and A.-L. Barabási (2002, Jan). Statistical mechanics of complex networks.
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.

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

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

Springer.

Kolaczyk, E. D. and G. Csárdi (2014). Statistical analysis of network data with R. Use
R ! Springer, New York.

Luke, D. A. (2015). A User’s Guide to Network Analysis in R. Springer.

von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing 17 (4),
395–416.

10