Je prends les lettres a et e de A drian PlanE lls .
On supprime le lien entre A et B et on ajoute un lien entre C et E.
I. Identifiez les composantes fortement connexes du graphe :
Il existe 2 composantes fortement connexes (groupes avec des liens entre toutes les paires) :
[A, C, D, E, F] : tous ces nœuds peuvent être reliés entre eux.
[B] isolé car aucun lien ne mène vers B.
Proximité et intermédiairité
modifier
II. Calculez la proximité de L1 (A) et L2 (E).
Rappel : la proximité = l’inverse de la somme des distances au sein des groupes de composantes fortement connexes.
Pour le nœud A, on prend le groupe [A, C, D, E, F]. Distance entre les nœuds : A>C:1, A>D:1, A>E:2, A>F:2.
Cp (A)
=
1
6
{\displaystyle ={\frac {1}{6}}}
Pour le nœud E, on prend aussi le groupe [A, C, D, E, F]. Distance entre les nœuds : E>1: E>C:2, E>D:2, E>F:3.
Cp (E)
=
1
8
{\displaystyle ={\frac {1}{8}}}
III. Calculez l'intermediarité de L1 (A) et L2 (E).
Rappel : l'intermédiarité est la somme, pour chaque paire des autres nœuds, de la fraction des chemins les plus courts entre ces nœuds qui passent par le premier.
Intermédiarité de A
Paire de nœuds
Nombre de chemins les plus courts
Nombre de chemins les plus courts passant par A
C
h
e
m
i
n
s
l
e
s
p
l
u
s
c
o
u
r
t
s
p
a
s
s
a
n
t
p
a
r
A
N
o
m
b
r
e
d
e
c
h
e
m
i
n
s
l
e
s
p
l
u
s
c
o
u
r
t
s
{\displaystyle {\tfrac {CheminslespluscourtspassantparA}{Nombredecheminslespluscourts}}}
C,D
1
1
1
C,E
1
0
0
C,F
1
1
1
D,C
1
0
0
D,E
1
0
0
D,F
1
0
0
E,C
1
1
1
E,D
1
1
1
E,F
1
1
1
F,C
1
1
1
F,D
1
1
1
F,E
1
1
1
Total
8
G(A) = 8
Intermédiarité de E
Paire de nœuds
Nombre de chemins les plus courts
Nombre de chemins les plus courts passant par E
C
h
e
m
i
n
s
l
e
s
p
l
u
s
c
o
u
r
t
s
p
a
s
s
a
n
t
p
a
r
E
N
o
m
b
r
e
d
e
c
h
e
m
i
n
s
l
e
s
p
l
u
s
c
o
u
r
t
s
{\displaystyle {\tfrac {CheminslespluscourtspassantparE}{Nombredecheminslespluscourts}}}
A,C
1
0
0
A,D
1
0
0
A,F
1
0
0
C,A
1
1
1
C,D
1
1
1
C,F
1
1
1
D,A
1
0
0
D,C
1
0
0
D,F
1
0
0
F,A
1
0
0
F,C
1
0
0
F,D
1
0
0
Total
3
G(E) = 3
IV. Construisez la matrice pour le calcul de la centralité de vecteur propre par multiplication matricielle, comme proposé dans les diapos.
On construit la matrice d'adjacence en rangeant les nœuds par ordre alphabétique (A (L1), B, C, D, E (L2), F).
A =
(
0
0
1
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
)
{\displaystyle {\begin{pmatrix}0&0&1&1&0&0\\0&0&1&0&1&0\\0&0&0&0&1&0\\0&0&1&0&0&1\\1&0&0&0&0&0\\1&0&0&0&0&0\end{pmatrix}}}
(
0
0
1
2
1
2
0
0
0
0
1
2
0
1
2
0
0
0
0
0
1
0
0
0
1
2
0
0
1
2
1
0
0
0
0
0
1
0
0
0
0
0
)
{\displaystyle {\begin{pmatrix}0&0&{\frac {1}{2}}&{\frac {1}{2}}&0&0\\0&0&{\frac {1}{2}}&0&{\frac {1}{2}}&0\\0&0&0&0&1&0\\0&0&{\frac {1}{2}}&0&0&{\frac {1}{2}}\\1&0&0&0&0&0\\1&0&0&0&0&0\end{pmatrix}}}
T
M
{\displaystyle ^{T}M}
(
0
0
0
0
1
1
0
0
0
0
0
0
1
2
1
2
0
1
2
0
0
1
2
0
0
0
0
0
0
1
2
1
0
0
0
0
0
0
1
2
0
0
)
{\displaystyle {\begin{pmatrix}0&0&0&0&1&1\\0&0&0&0&0&0\\{\frac {1}{2}}&{\frac {1}{2}}&0&{\frac {1}{2}}&0&0\\{\frac {1}{2}}&0&0&0&0&0\\0&{\frac {1}{2}}&1&0&0&0\\0&0&0&{\frac {1}{2}}&0&0\end{pmatrix}}}
V. Calculez une itération de PageRank avec s = 0,9 :
Le vecteur de matière initial est :
V
0
=
(
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
)
{\displaystyle V_{0}={\begin{pmatrix}1/6\\1/6\\1/6\\1/6\\1/6\\1/6\end{pmatrix}}}
On le multiplie par
T
M
{\displaystyle ^{T}M}
T
M
{\displaystyle ^{T}M}
V
0
{\displaystyle V_{0}}
(
0
0
0
0
1
1
0
0
0
0
0
0
1
2
1
2
0
1
2
0
0
1
2
0
0
0
0
0
0
1
2
1
0
0
0
0
0
0
1
2
0
0
)
{\displaystyle {\begin{pmatrix}0&0&0&0&1&1\\0&0&0&0&0&0\\{\frac {1}{2}}&{\frac {1}{2}}&0&{\frac {1}{2}}&0&0\\{\frac {1}{2}}&0&0&0&0&0\\0&{\frac {1}{2}}&1&0&0&0\\0&0&0&{\frac {1}{2}}&0&0\end{pmatrix}}}
(
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
)
{\displaystyle {\begin{pmatrix}1/6\\1/6\\1/6\\1/6\\1/6\\1/6\end{pmatrix}}}
(
1
/
3
0
1
/
4
1
/
12
1
/
4
1
/
12
)
{\displaystyle {\begin{pmatrix}1/3\\0\\1/4\\1/12\\1/4\\1/12\end{pmatrix}}}
On multiplie ce nouveau vecteur par s = 0,9 ce qui donne
(
3
/
10
0
9
/
40
3
/
40
9
/
40
3
/
40
)
{\displaystyle {\begin{pmatrix}3/10\\0\\9/40\\3/40\\9/40\\3/40\end{pmatrix}}}
−
{\displaystyle -}
On obtient :
V
1
{\displaystyle V_{1}}
(
3
/
10
0
9
/
40
3
/
40
9
/
40
3
/
40
)
{\displaystyle {\begin{pmatrix}3/10\\0\\9/40\\3/40\\9/40\\3/40\end{pmatrix}}}
(
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
1
/
6
)
{\displaystyle {\begin{pmatrix}1/6\\1/6\\1/6\\1/6\\1/6\\1/6\end{pmatrix}}}
(
19
/
60
1
/
60
29
/
120
11
/
120
29
/
120
11
/
120
)
{\displaystyle {\begin{pmatrix}19/60\\1/60\\29/120\\11/120\\29/120\\11/120\end{pmatrix}}}
En additionnant les sommes de matières dans ce vecteur, on obtient bien 1.
On passe à la seconde itération :
T
M
{\displaystyle ^{T}M}
V
1
{\displaystyle V_{1}}
(
0
0
0
0
1
1
0
0
0
0
0
0
1
2
1
2
0
1
2
0
0
1
2
0
0
0
0
0
0
1
2
1
0
0
0
0
0
0
1
2
0
0
)
{\displaystyle {\begin{pmatrix}0&0&0&0&1&1\\0&0&0&0&0&0\\{\frac {1}{2}}&{\frac {1}{2}}&0&{\frac {1}{2}}&0&0\\{\frac {1}{2}}&0&0&0&0&0\\0&{\frac {1}{2}}&1&0&0&0\\0&0&0&{\frac {1}{2}}&0&0\end{pmatrix}}}
(
19
/
60
1
/
60
29
/
120
11
/
120
29
/
120
11
/
120
)
{\displaystyle {\begin{pmatrix}19/60\\1/60\\29/120\\11/120\\29/120\\11/120\end{pmatrix}}}
(
1
/
3
0
17
/
80
19
/
120
1
/
4
11
/
240
)
{\displaystyle {\begin{pmatrix}1/3\\0\\17/80\\19/120\\1/4\\11/240\end{pmatrix}}}
En additionnant les sommes de matières dans ce vecteur, on obtient bien 1.
