Utilisateur:EmiliaSIREN/Modélisation des Réseaux (M1 SIREN, 2020)/Activité E

ACTIVITE E

Mon prénom et nom sont : Emilia Swieciochowska : ainsi le noeud L1 est pour moi le noeud a et le noeud L2 est le noeud h.

(J'avais écrite cette activité avant que l'énoncé ne soit corrigé, je n'ai donc pas pris en compte la lettre "e" dans mon raisonnement)

Le lien sortant du noeud L1 (noeud a) que j'ai enlevé est le lien vers le noeud c.

J'ai rajouté un lien depuis le noeud e vers le noeud L2 (noeud h).

Voici la représentation du graphe.

I. Les composantes fortement connexes.

En théorie des graphe, un graphe ou une composante d'un graphe orienté est dit fortement connexe s'il/elle est d'un seul tenant.

Les composantes fortement connexes, c'est-à-dire, les groupes des nœuds où il y a un chemin entre tous les pairs, sont donc dans ce cas :

- [g,h] est une composante fortement connexe, il est impossible d'aller vers [a,b,c,d,e,f]

- [a,b,d,e,f] est une composante fortement connexe

- [c] : impossible de revenir depuis [g,h] ou d'aller vers [a,b,d,e,f]

II. La matrice pour le calcul de la centralité de vecteur propre par multiplication matricielle.

Matrice A du graphe

	[a]	[b]	[c]	[d]	[e]	[f]	[g]	[h]
[a]	0	1	0	1	0	0	0	0
[b]	0	0	1	0	1	0	0	0
[c]	0	0	0	0	0	0	1	1
[d]	0	0	1	0	0	1	0	0
[e]	1	0	0	0	0	0	0	1
[f]	1	0	0	0	0	0	0	0
[g]	0	0	0	0	0	0	0	1
[h]	0	0	0	0	0	0	1	0

Ensuite, on divise la valeur de chaque noeud par son degré de sortie.Or les degrés des noeuds sont les suivants (on le trouve en sommant la ligne de chaque noeud):

a = 2

b = 2

c = 2

d = 2

e = 2

f = 1

g = 1

h = 1

//

On a alors la matrice suivante:

Matrice M

	[a]	[b]	[c]	[d]	[e]	[f]	[g]	[h]
[a]	0	1/2	0	1/2	0	0	0	0
[b]	0	0	1/2	0	1/2	0	0	0
[c]	0	0	0	0	0	0	1/2	1/2
[d]	0	0	1/2	0	0	1/2	0	0
[e]	1/2	0	0	0	0	0	0	1/2
[f]	1	0	0	0	0	0	0	0
[g]	0	0	0	0	0	0	0	1
[h]	0	0	0	0	0	0	1	0

Ensuite, on fait la matrice transposée: on échange les lignes et les colonnes, on échange les valeurs de part et d'autre de la diagonale :

Matrice transposée

	[a]	[b]	[c]	[d]	[e]	[f]	[g]	[h]
[a]	0	0	0	0	1/2	1	0	0
[b]	1/2	0	0	0	0	0	0	0
[c]	0	1/2	0	1/2	0	0	0	0
[d]	1/2	0	0	0	0	0	0	0
[e]	0	1/2	0	0	0	0	0	0
[f]	0	0	0	1/2	0	0	0	0
[g]	0	0	1/2	0	0	0	0	1
[h]	0	0	1/2	0	1/2	0	1	0

Ensuite, il faudra multiplier cette matrice transposée Mt par une matrice colonne pi qui contient la densité de matière de chaque noeud. Cette multiplication nous donnera alors la centralité du vecteur propre.

/

/

III. Calcule de deux itérations Page Rank

a) Initialisation de la matière : je choisis une matière de 1 que je partage également entre les 8 noeuds du graphe, ainsi chaque noeud commence avec une densité de 1/8.

On a la matrice suivante:

b) Je fais la première itération par calcul matriciel, on a :

c) Je multiplie la matière dans chaque noeud par s = 0,9 - on a la matrice suivante :

$\left({\begin{array}{c}3/16\\1/16\\1/8\\1/16\\1/16\\1/16\\3/16\\1/4\end{array}}\right)\times 0.9=\left({\begin{array}{c}27/160\\9/160\\9/80\\9/160\\9/160\\9/160\\27/160\\9/40\end{array}}\right)$

d) Ensuite, je partage s-1= 0,1 de la matière totale entre tous les noeuds.

Or la matière totale de base = 1 on ajoute donc 1/80 à chaque noeud; on a la matrice P1 suivante:

e) Je vérifie que la matière totale reste constante: je somme les éléments de la dernière matrice (petit d), que je nomme P1 pour la deuxième itération.

29/160 + 11/160 + 1/8 + 11/160 + 11/160 + 11/160 + 29/160 + 19/80 = 1

Donc la matière totale reste constante.

/

/

f) Je fais la seconde itération:

Et on vérifie :

337/3200 + 301/3200 + 119/1600 + 301/3200 + 139/3200 + 139/3200 + 113/400 + 841/3200 = 1

C'est donc bon, la matière reste constante ! :)