Utilisateur:Alice Joie Dauphine/Modélisation des Réseaux (M1 SIREN, 2022)/Activité E

Mon réseau

Graphe - Activité E

Je m'appelle Alice Joie.

En prenant la première et la dernière lettre en commun dans le graphe, 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

Voici le résultat :

Composantes

I. L'ensemble du réseau est une composante fortement connexe soit :

• {L1,b,c,L2,d,f}

II. Tous les noeuds ont minimum deux voisins. Le noeud le plus central est a car il possède 4 voisins. b, c, d et e sont également centraux avec 3 voisins et étant connectés à des sommets très connectés. f est le moins central, ne possédant que deux voisins.

Vecteur propre et PageRank

I. Matrice pour le calcul de la centralité de vecteur propre par multiplication matricielle

Ordre dans la matrice : L1, b, c, d, L2, f

$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}}$

$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}}$

$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. J'initialise mon vecteur de matière distribuant également une matière totale de  :

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

Je procède au 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 a bien une matière totale de 6.

Il faut ensuite multiplier la matière dans chaque nœud par 0,9 , puis partagez également 0,1 de la matière totale entre tous les nœuds.

Donc on doit avoir $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}}$

Encore une fois, on a bien une matière totale de 6.

Graphe de blocs

I. Je reprends la matrice adjacente de mon graphe :

$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 chaque partition en blocs H1 ou H2, je somme les valeurs qui correspondent aux liens d'un bloc à l'autre.

Pour H1 :

B1 = {L1=a, b, L2=e}

B2 = {c, d, f}

Liens entre les blocs

	B1	B2
B1	(L1,b), (b, L2), (L2,L1)	(L1,d), (b,c)
B2	(c, L2), (f, L1)	(d,c), (d,f)

J'obtiens la matrice adjacente : $H1={\begin{pmatrix}3&2\\2&2\end{pmatrix}}$

Pour H2 : B1 = {L1=a, L2=e, f}

B2 = {b, c, d}

Liens entre les blocs

	B1	B2
B1	(L2, L1), (f, L1)	(L1,b), (L1,d)
B2	(b, L2), (c, L2), (d,f)	(b,c), (d,c)

J'obtiens la matrice adjacente :

$H2={\begin{pmatrix}2&2\\3&2\end{pmatrix}}$

II. Aucune des deux matrices adjacentes ne se dégage vraiment. En effet, nous ne pouvons pas observer de tendances de bipartition du réseau. Les deux matrices sont assez semblables, avec des valeurs moyennes de 2 ou 3, et aucune valeur caractéristique ne se dégage.

Si je devrais redistribuer les liens entre blocs vers des liens entre nœuds, quelle est la probabilité que j'obtienne les mêmes liens entre nœuds du graphe original ? Aucun graphe ne se dégage vraiment, car les probabilités sont les mêmes car chaque bloc est composé de 3 noeuds.