UNIVERSITE MOHAMED BOUDIAF DE M’SILA

DEPARTEMENT D'INFORMATIQUE

Les Fondements de la théorie

des graphes
Chapitre 1: Concepts de base

Dr. SAID KADRI

Maître de Conférence

Department d'informatique, Faculté des Mathematiques et de l'Informatique, Université

Mohamed Boudiaf de M'sila

E-mail: kadri.said28@[Link]

Website: [Link]

2017 - 2018
 Définition d'un Graphe
▪ Un Graphe est une collection de sommets connectés
par des arêtes ou des arcs.

▪ On appelle un graphe le couple G(X, U) tel que:

▪ X = {x1, x2, ….., xn} est l'ensemble des sommets du
graphe.
▪ U={u1, u2, …., un} est l'ensemble des arcs du graphe
▪ U  XxX
Sommet

Arête

▪ Le terme réseau: est utilisé pour designer des systems reels

(réseau routier, Réseau électrique, réseau informatique, etc).

▪ Le terme Graphe: est utilisé pour designer une représentation

mathématique d'un réseau.
Mais, généralement: “Réseau” ≡ “Graphe”
Propriétés d'un graphe:
• n=|X| est appelé l'ordre du graphe G.
• m=|U| est la taille du graphe ([Link])
• un sommet xi est représenté par un point.
• Un arc U=(xi, xj)XxX est représenté par une flêche ou un
segment de droite (selon le type du graphe orienté/non orienté)

u1
1 2
5
u2 u3 u4
u6
3
u5 4

n=|X|=5 m=|U|=6

• Si xi=xj ==> u=(xi, xj) est représenté par une boucle (c.à.d les
deux sommets sont confondus).
xi
yj

• Le 1/2 degré extérieur du sommet x est le nombre d'arcs dont x

est l'extrémité initiale ou le nombre d'arcs sortants de x.
On note d+(x).
• Le 1/2 degré intèrieur du sommet x est le nombre d'arcs dont x
est l'extrémité terminale ou le nombre d'arcs entrants dans x et
On note d-(x).
• Le degré du sommet x est le nombre d'arcs dont x est l'extrémité
initiale ou terminale et on note d(x) = d+(x) + d-(x).

x x x

d+(x) = 4 d-(x) = 3 d(x) = d+(x) + d-(x) = 7

• Si (x, y)U, alors x est dit prédécesseur de y, y est le successeur

de x.
x y

• +(x): l'ensemble des successeurs de x.

• -(x): l'ensemble des prédécesseurs de x.
• Un sommet source s est un sommet qui ne possède aucun
prédécesseur (-(s)= / il y a seulement des arcs sortants).
• Un sommet puits p est un sommet qui ne possède aucun
successeur (+(x) = ) / il y a seulement des arcs entrants).
• Un sommet isolé x est un sommet qui ne possède aucun voisin
(ni prédécesseur ni successeur) ((+(x)= (-(x) = ). Alors il
s'agit ici d'un sommet source et puits en même temps, il est aussi
appelé un sommet inaccessible.

s p
 Exemple: b
h
a
e
X={a, b, c, d, e, f, g, h, I, j, k, l}
i
c d
U={(a, b), (a, i), (b, f), (f, d), (d, f), f
(e, a), (e, h), (k, l), (e, c), (c, k), (b, b), g
k
(g, j), (l, j)} j l

+(f) = {d}, +(d) = {f}, +(b) = {f, b},

+(j) = , +(e) = {a, h, c}, -(f) = {b, d},
-(e) = , -(a) = {i, e}

Exemples de graphes:
▪ Graphe représentant un réseau routier, ou les sommets représentent
les intersections et les arcs représentent les routes.
▪ Réseau de distribution de l'eau potable AEP dans une ville.
▪ Réseau informatique au niveau d'une entreprise.
▪ Le réseau international d'information Internet.

Graphe orienté et graphe non orienté

Graphe non orienté Graphe orienté
Lignes: non orientées (symétriques) Lignes: orientées
➔ arètes ➔ arcs
Graphe non orienté Di-graphe = graphe orienté

Définition d'un graphe valué

Un graphe valué est un graphe G(X, U, C) tel qu'on associe au

graphe G(X, U) une function F définie comme suit:

F: U R

F(u) = c est appelé le poids de l'arc u, et on note c(x, y) ou c(u)

Avec:

▪ c(x, y): longueur du tronçon de route (x, y).

▪ Capacité du tronçon de route (x, y).
▪ Debit d'une conduite d'eau potable.
▪ Prix de déplacement entre les villes x, y.
Types de graphes

1. Graphe symétrique
Un graphe G(X, U) est dit symétrique si x, yX, si (x, y)U
===> (y, x) U

1 2 1
2

3 3
4
4

Un graphe symétrique est représenté généralement sans

orientation des arcs. On parle des arêtes au lieu des arcs

2. Graphe complet
Un graphe G(X, U) est dit complet si seulement si:

x, yX, (x, y) U et (y, x) U

2 2

1 3 1 3

4 4
Graphe complet Graphe non complet
3. Graphe simple
Un graphe G(X, U) est dit simple si seulement si:

- Ne contient aucune boucle.

-  x, yX,  au plus u=(x, y)U

4. Graphe vide
Un graphe G(X, U) est dit vide s'il n y a aucun sommet ni arc
ou arête. (X= , U = ).

5. Graphe trivial
Un graphe G(X, U) est dit trivial s'il y a des sommets, mais il
n y a aucun arc ou arete. (U = ).
1 2

3 4

6. Graphe réflexif
Un graphe G(X, U) est dit réflexif, s'il existe une boucle en
chaque sommet x de G.

-  xX ===> (x, x)U

7. Graphe anti-symétrique
Un graphe G(X, U) est dit anti-symétrique si:

-  x, yX, si (x, y)U ===> (y, x)U

8. Graphe transitif
Un graphe G(X, U) est dit transitif si:

-  x, y, zX, si (x, y)U et (y, z)U ===> (x, z)U

9. Inverse d'un graphe

L'inverse d'un graphe G(X, U) est le graphe G'(X, U') déduit
de G en inversant le sens de ses arcs.

OBS: l'inverse de G' est G lui même.

10. Graphe complémentaire

Le graphe complémentaire du graphe G(X, U) est le graphe
G*(X, U*) tel que:

(x, y)U ===> (x, y) U*

11. Multigraphe
si G est un graphe orienté, x et y deux sommets de ce
graphe, si x et y sont liés par deux arcs u1, u2 de même sens,
G est dit multigraphe et l'arc (x, y) est dit un arc multiple.

3 4 3 4

1 1

2 5 2 5

un graphe multiple orienté un graphe multiple non orienté

• (3, 4) un arc multiple

• (2, 5) un arc symétrique

12. Le graphe biparti (bipartite graph)

Un graphe biparti (ou un bi-graphe) est un graphe dont
l'ensemble des ses sommets peuvent être divisé en
deux sous-ensembles disjoints de sommets X1 et X2
tels que deux sommets du même sous-ensemble ne
soient pas adjacents (c.à.d tout arc de G a une
extrémité dans X1 et l'autre dans X2).

Et on note:
G(X, U) avec: X = X1X2 et X1X2=
Et si u=(x1, x2) et x1X1 ===> x2X2
x1X2 ===> x2X1
 X1 X2

13. Graphe planaire

Un graphe G est dit planaire s'il est possible de le

tracer dans le plan de façon que deux arcs
quelconques ne se croisent pas sauf en leurs
extrémités.

On appellee representation planaire ce trace dans le

plan.

Exemple:

G1, G2: deux graphes non planaires G3 un graphe planaire

14. Graphes isomorphes

Deux graphes G(X, U), G'(X', U') sont dits isomorphes

s'il existe une bijection f:

f: X X'

Telle que: (x, y)U  (f(x), f(y)) U'

c.à.d si les deux sommets x, y sont liés par un arc

dans G ===> l'image de x et l'image de y par f sont
aussi liées par un arc dans G'.

Exemple 1:
Soient les deux graphes G, H définis comme suit:

1 5 7 3 f g c

b e

d a
4 2 6

(G) (G')

Et soit une bijection f définie comme suit:

f: {1, 2, …, 7} {a, b, …, g}

Avec: f(1)=a, f(2)=b, …, f(7)=g

G et G' sont isomorphes.

Exemple 2:
Soient les deux graphes G, H définis comme suit:

3 2 1 d c b a

6 g

5 e f
4 7

(G) (H)

(G), (H) deux graphes non orientés et non isomorphes.

Car (3, 5)U ===> (f(3), f(5))=(c, e)U'

Degré d'un sommet

Graphe non orienté Graphe orienté
Degré: le nombre des arêtes dans un graphe orienté, on définit
qui relient les sommets. des degrés intérieurs des degrés
extérieurs.
Le degré total d'un sommet est la
somme du degré intérieur et le degré
extérieur.
Distribution de degrés
Résume les degrés de tous les sommets du graphe.
Deux méthodes de distribution sont proposées:

1. Compter les fréquences des sommets associés à

chaque degré.
2. Calculer la probabilité P(k): qu'un sommet choisi
arbitrairement possède le degré k.
Degré moyen

Graphe non orienté Graphe orienté

N: le nombre de sommets dans le graphe.

L: le nombre d'(arcs/arêtes) dans le graphe
Densité d'un graphe
Nb. de connexions qui peuvent exister entre sommets:

Graphe orienté

Lmax = N*(N-1)

Puisque chaqu'un des N

sommets peut se connecter
avec (N-1) autres sommets

Graphe non orienté

Lmax = N*(N-1)/2

Puisque les arêtes ne sont pas orientées, alors compter

chaque arête uniquement une seule fois.




Valeur de la densité?

Density = L/ Lmax
 Par exemple:
Dans ce graphe, on a:

N=4; L = [Link] = 6
➔ Lmax = 4*(4-1)=12

parmi les 12 connexions possibles

Lmax , ce graphe a 6, donnant une
densité de: 6/12 = 0.50

Definition d'un chemin

On appelle un chemin de G(X, U) la suite de sommets
a1, a2, …, ap (sans coupure) tel que:
▪ (ai, ai+1)U avec i=1, 2, …, p-1.
▪ ai est l'extrémité initiale du chemin
▪ ap est l'extrémité terminale du chemin.

Definition d'un chemin simple

a1, a2, …, ap est un chemin simple tel que:

 i≠j, (ai, ai+1)≠(aj, aj+1) (c.à.d un arc est pris une seule fois).

Definition d'un chemin élémentaire

est un chemin qui ne prend les sommets qu'une seule fois.
Exemples:
x1
x2x1x5x3x1x5x5x3x6 chemin qui n'est pas x2 x5

simple, ni élémentaire. x4 x3

x2x1x5x3x1x2x4 chemin simple

x6 x7
non élémentaire

x1x2x4x3x6 chemin élémentaire

Remarque
Si a1a2a3 ….ap est un chemin
▪ a1 est un ascendant de ap
▪ ap est un descendant de a1

Definition d'un circuit

Un circuit est un chemin a1a2a3 ….ap tel que: a1=ap
c.à.d les deux extrémités initiale et terminale sont
confondues (un chemin fermé).

Observations
▪ De la même façon on peut définir un circuit simple, un
circuit élémentaire.
▪ La notion du chemin circuit met en considération le
sens des arcs du graphe.
▪ Un circuit simple est un chemin fermé qui ne prend les
arcs qu'une seule fois.
▪ Un circuit élémentaire est un chemin fermé qui ne prend
les sommets qu'une seule fois.
Chemins et circuits particuliers
1. Un chemin hamiltonien : est un chemin élémentaire qui
passe par tous les sommets du graphe.
2. Un chemin eulerien : est un chemin simple qui passe
par tous les arcs du graphe une et une seule fois.
3. Un circuit hamiltonien : est un circuit élémentaire qui
passe par tous les sommets du graphe.
4. Un circuit eulerien : est un chemin simple et fermé qui
passe par tous les arcs du graphe une et une seule fois.

t4
Exemples: t2 t5

t1t2t3t4t5t6t7 est un chemin hamiltonien t1

t6

t3
t7

z1z4z5z4z3z3z9z8z2z9z6z7z6z1 est un circuit eulerien

z5

z3
z9 z2
z4
z6
z1 z8
z7
Définition d'une chaîne
Une chaîne d'un graphe non orienté (ou orienté mais
l'orientation n'est pas prise en considération) G(X, U) est
une suite de sommets a1, a2, …, ap (sans coupure) tel que:
(ai, ai+1)U ou (ai+1, ai)U avec i=1, 2, …, p-1.

x2
Exemple:
x1 x4
x1x2x4x3x6x5x3x2 est une chaîne x3
x1x2x5 n'est pas une chaîne
x5
x6
Définition d'une chaîne simple
C'est une chaîne ou les (arcs/arêtes) sont pris(es) une seule
fois.
Exemple:
x1x2x3x2x4x3x5x6x3 est une chaîne simple.

Définition d'une chaîne élémentaire

C'est une chaîne dont tous les sommets du graphe sont pris
une seule fois.

Exemple:
x1x2x4x3x6 est une chaîne élémentaire.
Définition d'un cycle
Un cycle est une chaîne a1a2a3 ….ap, tel que: a1=ap
c.à.d l'extrémité initiale et l'extrémité terminale sont
confondues

Exemple:
x2x4x3x6x5x3x2 est un cycle.

Observations
▪ De la même façon on peut définir un cycle simple, un
cycle élémentaire.
▪ Dans la définition d'une chaîne ou d'un cycle
l'orientation du graphe n'est pas importante.

Chaînes et cycles particuliers

1. Une chaîne hamiltonienne : est une chaîne élémentaire
qui passe par tous les sommets du graphe.
2. Une chaîne eulerienne : est un chaîne qui passe par tous
les arcs du graphe une et une seule fois.
3. Un cycle hamiltonien : est un cycle élémentaire qui
passe par tous les sommets du graphe.
4. Un cycle eulerien : est une chaîne simple et fermée qui
passe par tous les arcs du graphe une et une seule fois.
Exercices:
Exercice 1
Soit le graphe G(X, U) suivant:
▪ bacbd: chemin simple c

▪ eacbd: chaîne élémentaire b

a
▪ acbacbd: chemin non simple
▪ aebdebac: chaîne non simple. d

▪ adbc: ni chemin, ni chaîne

e

Exercice 2
▪ acbacba: circuit non simple.
▪ abdebae: cycle non simple.
▪ acba: circuit élémentaire (même sens).
▪ acbea: cycle élémentaire.
Définition d'un sous graphe
Soit G(X, U) un graphe
G'(X', U') est un sous graphe de G si X'X

U'={uU/ les deux extrémités de u appartiennent à X'}

(c.à.d, on supprime des sommets et des arcs)

Définition d'un graphe partiel

Soit G(X, U) un graphe, on appelle graphe partiel de G, le
graphe G'(X', U') tel que: X'=X, U'U
(c'est un graphe ayant le même ensemble X de sommets,
mais un ensemble different des arcs U'U).

Définition d'un sous graphe partiel

Soit G(X, U) un graphe, on appelle sous graphe partiel de G,
un graphe partiel d'un sous graphe de G.
(c.à.d on supprime des sommets et des arcs)

Exemple:
Soit le graphe G(X, U) avec:
X={a, b, c, d, e, f, g} ; U={(a, b), (a, c), (c, d), (b, f), (f, g),
(e, a), (e, f), (e, d), (f, d)}
1. G'(X', U') est un sous graphe (Fig 1)
X'={a, e, f, d} ; U'={(e, a), (e, f), (d, e), (f, d)}

b
g

a
e
f
X'
c
d G'

Fig 1

2. G"(X, U") est un graphe partiel (Fig 2)

U"={(a, b), (a, c), (c, d), (d, e), (e, f), (f, d)}

b
g

a
e
f

c
d
Fig 2

3. G"'(X', U"') est un sous graphe partiel (Fig 3)

X'={a, e, f, d} ; U"'={(a, e), (e, f), (f, d)}

a
e
f

d
Fig 3
Exemple pratique:
Pour un réseau routier d'un pays

1. L'ensemble des routes d'une wilaya est un sous graphe

du réseau routier.
2. L'ensemble des routes nationales est un graphe partiel
du réseau routier.
3. L'ensemble des routes nationales d'une wilaya est un
sous graphe partiel du réseau routier.

Définition d'un graphe connexe

Un graphe G(X, U) est dit connexe si:
-  x, yX, il existe une chaîne entre x et y (le sens des
arcs n'est pas important)
a
d

b
e
c
Un graphe connexe; mais n'est pas

fortement connexe
Définition d'une composante connexe
Est un sous graphe connexe et maximal pour cette
propriété. C.à.d, si on ajoute un sommet à cette composante
on détruit la connexité.
OBS: si G est un graphe connexe, il constitue lui même la
seule composante connexe.

Définition d'un graphe fortement connexe

Un graphe G(X, U) est dit fortement connexe si:
 x, yX, il existe un chemin de x vers y et un autre de y vers x

Exemple:
(1, 2)  un chemin (1, 2)
(2, 1)  un chemin (2, 3), (3, 1)
(2, 3)  un chemin (2, 3) 2
(3, 2)  un chemin (3, 1), (1, 2)
(3, 1)  un chemin (3, 1) 3
(1, 3)  un chemin (1, 2), (2, 3)
(1, 4), (4, 5), (5, 3) 1
(3, 4)  un chemin (3, 1), (1, 4)
(4, 3)  un chemin (4, 5), (5, 3)
5
(4, 5)  un chemin (4, 5) 4
(5, 4)  un chemin (5, 3), (3, 1), (1, 4) G est fortement connexe
(5, 3)  un chemin (5, 3)
(3, 5)  un chemin (3, 1), (1, 4), (4, 5)
(1, 4)  un chemin (1, 4)
(4, 1)  un chemin (4, 5), (5, 3), (3, 1)
(1, 5)  un chemin (1, 4), (4, 5)
(5, 1)  un chemin (5, 3), (3, 1)
(2, 4)  un chemin (2, 3), (3, 1), (1, 4)
(4, 2)  un chemin (4, 5), (5, 3), (3, 1), (1, 2)
(2, 5)  un chemin (2, 3), (3, 1), (1, 4), (4, 5)
(5, 2)  un chemin (5, 3), (3, 1), (1, 2)
On constate que x, yX On peut trouver un chemin de x vers y et
un autre de y vers x ===> le graphe G(X, U) est un graphe fortement
connexe.

Définition d'une composante fortement connexe

On appelle une composante fortement connexe d'un graphe
G(X, U) un sous graphe G'(X', U') fortement connexe.

Exemple:
Soit le graphe G(X, U) suivant tel que:
X={a, b, c, d, e, f, g, h, I, j}
U={(a, c), (c, d), (d, e), (e, f), (d, j), (b, g), (g, h), (h, f), (f, i),
(I, j), (j, g)}

b
G' g
h
e
f
a
i

d
c

G1 G2

G(X, U) n'est pas fortement connexe.

G'(X', U') est un sous graphe de G.
X'={a, b, e} ; U' = {(a, b), (b, e), (e, a)}
G' représente une composante fortement connexe (non
maximale)
G1(X1, U1), G2(X2, U2) sont deux composantes fortement
connexes maximales.

Observations:
G(X, U) un graphe, si x, yX, il existe une chaîne entre x et y
on dit que G(X, U) est simplement connexe.
G(X, U) un graphe connexe, si après l'élimination de plus de
k arêtes, G devient non connexe on dit que G est k-arêtes
connexe.

Définition d'un point d'articulation:

Un point d'articulation d'un graphe G est un sommet dont la
suppression augmente le nombre de composantes
connexes.

Définition d'un isthme :

Est un arc dont la suppression augmente le nombre de CC.
Algorithme de recherche d'une composante simplement
connexe CSC d'un sommet S

Soit G(X, U) un graphe

(1) Marquer le sommet S (par *)
(2) Marquer tout sommet adjacent (suivant/précedent) à
un sommet déjà marqué
(3) Repéter (2) jusqu'à ce que l'on ne puisse plus marquer
aucun sommet.
(4) Les sommets marqués par (*) forment la composante
simplement connexe de S

b*

Exemple: e*

Soit G(X, U) un graphe avec: a*

X={a, b, c, d, e}
*
d*
c

U = {(a, b), (a, c), (b, e), (c, d), (d, e), (e, a)}

Construisons la CSC de b
(1) Marquer b (b*)
(2) Marquer les sommets adjacents de b (les suivants et
les précédents de b)
(3) Aucun sommet n'est resté sans marquage.
{a, b, c, d, e} constitue une composante simplement
connexe, c.à.d G forme une CSC
Algorithme de recherche d'une composante fortement
connexe CFC d'un sommet S

Soit G(X, U) un graphe

(1) Marquer le sommet S avec (+ et -)
(2) (a) Marquer par (+) tout suivant (non encore marqué +)
d'un sommet déjà marqué (+)

(b) Marquer par (-) tout précédent (non encore marqué -)

d'un sommet déjà marqué (-)

(3) Les sommets marqués à la fois par + et – forment une

CFC contenant S.

Exemple:
dans le graphe ci-contre b+/-
CFC(b)={b, a, e}
e+/-

A+/-

+
d+
c
Le plus court chemin / La distance
▪ La distance (le plus court chemin)
entre deux sommets est définie
par le nombre des arêtes au long
de plus court chemin qui connecte
ces deux sommets. Si les deux
sommets sont disconnectés, la
distance est infinie. S’ils sont
confondus la distance est nulle.

▪ Dans un graphe orienté chaque

chemin doit suivre la direction des
arcs. Donc, la distance du sommet
A au sommet B (sur le chemin AB)
est généralement différente de la
distance du sommet B au sommet
A (sur le chemin BCA).

Diamètre d'un réseau et distance moyenne

Diamètre dmax
Le diamètre dmax est la distance maximale entre n'importe
quelle pair de sommets dans le graphe.

Distance Moyenne
<d> pour un graphe connexe est donnée par:
Avec:

▪ dij est la distance du sommet i au sommet j

▪ N est le nombre des sommets du graphe.

2. Détection d'une Communauté

Une communauté est un ensemble de sommets entre

lesquels les interactions sont (relativement) fréquentes.

 Les communautés sont aussi appelées des groupes, des

segments, ou des modules.

 Trouver une communauté dans un graphe consiste à

identifier un ensemble de sommets ayant des interactions
entre eux plus qu'avec d'autres sommets qui
n'appartiennent pas au même groupe.

Exemples de Communautés
Composantes Géantes et composantes isolées
 Si la plus large
composante dans un graphe
occupe une partie
significative de celui-ci, elle
est donc appelée une
composante géante.
 Les autres petites
composantes du même
graphe sont appelées
composantes isolées.

Exercice: Composantes connexes dans un graphe

 Combien de composantes fortement connexe dans le
graphe suivant?

K-Cores
Un K-Cores est un sous graphe maximal dans lequel chaque
sommet possède au moins un degré k dans le graphe.
 Un K-Cores n'est pas nécessairement un graphe connexe. Par
exemple l'un des 3-cores ci-dessus est constitué de deux parties
(deux composantes).

Exercice: K-Cores

Compter le nombre de 3-cores dans le graph (les couleurs des sommets

indiquent le niveau de k):
Blanc : k=1 (1-core); Gris clair: k=2 (2-cores); gris foncé: k=3 (3-cores)
; noir: k=4 (4-cores)
Cliques et sous graphes complets

Une clique est un sous graphe complet maximal contenant au

moins trois (03) sommets.

Les sommets 5, 6, 7 et 8
forment une clique

Equivalence Structurelle entre sommets

Deux sommets sont structurellement équivalents s'ils sont
connectés aux mêmes ensembles de sommets.

Exemple: les deux sommets 5 et 6

Similarité entre sommets
Similarité de Jaccard

Similarité Cosine

Exemple
Centralité (sommet central)

Centralité
Quels sommets sont plus centraux?
Calculés pour des graphes non orientés

Un sommet central (acteur central) est un sommet

impliqué dans plusieurs arêtes.
La direction des arcs n'est pas considérée.

Concept de centralité

Prestige (sommet prestigieux)

Un sommet prestigieux (acteur prestigieux) est un
sommet qui représente la destination de plusieurs arcs
(reçoit des arcs).
La direction des arcs est considérée dans ce cas.
 Concept de prestige

Degré de centralité
Idée : Mesure la centralité comme le nombre d'arêtes vers
d'autres sommets dans le graphe.

Exemple: combien de personnes

peuvent être influencées
directement par une personne?

Degré de centralité

CD(ni) = d(ni)
Degré normalisé de centralité

C’D(ni) = d(ni) / N-1

 Le degré divisé par le degré maximal possible, c.à.d, le

nombre de sommets – 1
 Proportion de tous les sommets qui sont adjacents à ni

Example: Degré Normalizé de Centralité C’D

Centralisation
Combien de variations existe-il dans le score de centralité
parmi les sommets ?

Formule Générale de Freeman pour la Centralisation:

Valeur maximale de centralité dans le graphe

Mmaximum théorique du graphe

1. Calculer la somme des différences de centralité entre les

sommets les plus centraux du graphe et tous les autres
sommets.
2. Diviser la valeur résultante en (1) par la somme théorique
maximale du graphe.

N.B: Valeur de centralisation[0,1]

Example: Degré de centralisation CD

high

CD = [(5-1)+(5-1)+(5-1)+(5-1)+(5-1)] CD = [(3-2)+(3-2)+(3-2)+(3-3)+(3-2)+(3-2)]
/(6-1)(6-2) = 20/20 = 1.0 /(7-1)(7-2) = 5/30 = 1/6 ≈ 0.167

CD =[(2-1)+ (2-2)+ (2-2)+ (2-2)+ (2-1)]/(5-1)*(5-2)

= 2/12 = 1/6 ≈ 0.167
Centralité entre deux sommets/Binaire
(Betweenness Centrality)

Définition

Les interactions entre deux sommets non-adjacents X et

Y peuvent dépendre d'autres sommets du graphe,
surtout ceux qui appartiennent aux chemins reliant les
deux sommets X et Y.

 lesquels des deux sommets X ou Y a une valeur élevée

de centralité binaire?

Example 1:

Dans fig 1: X a une valeur élevée de centralité binaire

(4) contre Y(3)

Dans fig 2: X a une valeur élevée de centralité binaire

(5) contre Y(1)
Example 2:

A est un sommet qui ne relie entre aucuns autres deux

sommets dans le graphe.
B relie entre A et 3 autres sommets: C, D, et E
C relie entre 4 pairs de sommets (A, D),(A, E),(B, D),
(B, E).

On note ici qu'il n'existe aucun autre chemin alternatif

reliant ces pairs de sommets sauf ceux qui passent par le
sommet C.

Example 3:
(Degré de centralité/centralité binaire) sur le réseau
Facebook
Les sommets sont dimensionnés par degré de
centralité et colorés par centralité binaire
Centralité de proximité

Cette mesure focalise sur la façon qu'un sommet est

proche des autres sommets dans le graphe.

Centralité de proximité est basée sur la longueur

moyenne du plus court chemin entre un sommet et tous
les autre sommets du graphe.

Centralité de proximité :

Centralité de proximité normalisée :

Exemple : Centralité de proximité

Plus d'exemples:

Prestige
Le prestige est une métrique de centralité qui prend en
considération la direction des arcs.

Degré de prestige/Popularité
 le prestige d'un sommet est calculé en fonction du
demi-degré intérieur du sommet (in-degree)

Degré de prestige/Popularité

PD(ni) = din(ni)

Degré de prestige normalisé

P’D(ni) = din(ni)/(N-1)
Domaine d'entrée (d'influence)

 Le degré de prestige
calcule uniquement les
acteurs qui sont adjacents
ou liés directement à
l'acteur ni, mais on peut
aussi prendre en
considération des
sommets qui sont liés indirectement à ni.

 Le domaine d'entrée d'un sommet dans un graphe

orienté est le nombre ou le pourcentage de tous les
autres sommets qui sont liés par des Chemins à ce
sommet. Il est aussi appelé domaine d'influence.

Rang du Prestige

Une nouvelle métrique qui prend en considération les

prestiges des acteurs (sommets) appartennant au même
domaine d'influence.

Un sommet sera plus prestigieux s'il a beaucoups

d'autres sommets prestigieux appartenant au même
domaine d'influence.
j: un sommet dans le domaine d'entrée de i
PR(i): Rang du prestige du sommet i
PR(j): prestige du sommet j