Utilisateur:Margaux Tournois/Modélisation des Réseaux (M1 SIREN, 2022)/Activité E

Votre réseau

En incluant mon deuxième prénom, je m'appelle Margaux Anne Tournois.

Parmi les lettres [a, b, c, d, e, f], en prenant la première et la dernière lettre en commun, j'ai donc L1 = a et L2 = e.

J'ai décidé d'enlever le lien de L1 à c

Je rajoute un lien de c à L2

On obtient donc le graphique suivant :

Composantes

I. Identifiez les composantes fortement connexes du graphe.

L'ensemble du réseau, c'est à dire {L1,b,c,L2,d,f} , est une composante fortement connexe.

II. En fonction des ses composantes fortement connexes, que peut-on conclure à propos de la centralité de vecteur propre du graphe ?

Nombre de voisins par composantes fortements connnexes

L1	b	c	L2	d	f
4	3	3	3	3	2

D'après le graph et le tableau, on peut donc en déduire que le nœud le plus central est A car il possède 4 voisins et le moins central est F car il n'a que 2 voisins. De plus, B, C, D et E sont également centraux car ils possèdent 3 voisins et sont connectés à des sommets très connectés.

Vecteur propre et PageRank

I. Construisez la matrice pour le calcul de la centralité de vecteur propre par multiplication matricielle, comme proposé dans les diapos.

On veut construire la matrice A, matrice des nœuds sortants origine-direction. Pour commencer je fais un tableau et je met 1 lorsqu'on a un nœud sortant entre 2 composantes.

	L1	b	c	d	L2	f
L1	0	1	0	1	0	0
b	0	0	1	0	1	0
c	0	0	0	0	1	0
d	0	0	1	0	0	1
L2	1	0	0	0	0	1
f	1	0	0	0	0	0

Ensuite je traduis ce tableau sous forme de matrice : $A={\begin{pmatrix}0&1&0&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}}$

Pour construire ma matrice M je reprends ma matrice A et lorsque j'ai x nœuds sortant je divise 1 par ce nombre. Par exemple sur ma première ligne L1 possède 2 nœuds sortant donc j'obtiens deux fois 1/2 sur la première ligne de la matrice.

$M={\begin{pmatrix}0&1/2&0&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\end{pmatrix}}$

Ensuite je fais la matrice transposée de M. Ceci nous donne donc :

$\mathrm {M} ^{t}={\begin{pmatrix}0&0&0&0&1&1\\1/2&0&0&0&0&0\\0&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\end{pmatrix}}$

II. Calculez une itération de PageRank avec S = 0,9 :

• J'initialise le vecteur de matière pour le calcul de la centralité de vecteur propre en la partageant entre tous les nœuds. J'utilise donc le vecteur V₀ tel que :

$V_{0}={\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}$

J'effectue le calcul d'une itération de la centralité de vecteur propre :

$M^{t}*V_{0}={\begin{pmatrix}0&0&0&0&1&1\\1/2&0&0&0&0&0\\0&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\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\1/2\\1\\1/2\\3/2\\1/2\end{pmatrix}}$

On obtient une matière de 6. On multiplie ensuite le résultat obtenu par 0,9, puis on la partage par 0,1. Ceci nous donne :

$M^{t}V_{0}*0,9+0,1$

Soit :

${\begin{pmatrix}2\\1/2\\1\\1/2\\3/2\\1/2\end{pmatrix}}*0,9+{\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}={\begin{pmatrix}1,8\\0,45\\0,9\\0,45\\1,35\\0,45\end{pmatrix}}+{\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}={\begin{pmatrix}1,9\\0,55\\1\\0,55\\1,45\\0,55\end{pmatrix}}$

On obtient bien une nouvelle fois 6.

Graphe de blocs

Graphique de blocs H1 :

Graphique de blocs H2 :