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

Votre réseau

Je m'appelle Léa Fournier.

La première lettre qui apparait est la lettre "e".

La dernière lettre qui apparait, en excluant le "e", est la lettre "f".

J'enlève le lien sortant du noeud L1 vers "a".

Je rajoute un lien sortant du noeud c vers le noeud L2.

Voici le résultat. (cf. image) (modifier la flèche de L2 à c en c vers L2)

Composantes

L'ensemble du réseau est fortement connexe à l'exception du noeud L1.

Les noeud "a" et "c" possèdent 4 voisins, c'est les plus centraux. Ensuite, les noeud b, d et L2 possède 3 voisins. Le noeud L1 est le moins central avec 1 unique voisin.

Vecteur propre et PageRank

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

A=${\begin{pmatrix}0&1&1&1&0&0\\0&0&1&0&1&0\\0&0&0&0&0&1\\0&0&1&0&0&1\\0&0&0&0&0&0\\1&0&0&0&0&0\end{pmatrix}}$

M=${\begin{pmatrix}0&1/3&1/3&1/3&0&0\\0&0&1/2&0&1/2&0\\0&0&0&0&0&1\\0&0&1/2&0&0&1/2\\0&0&0&0&0&0\\1&0&0&0&0&0\end{pmatrix}}$

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

Je multiplie la matière dans chaque nœud par $s\ (=0,9)$, puis partagez également $1-s\ (=0,1)$ de la matière totale entre tous les nœuds.

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

Soit :

${\begin{pmatrix}1\\1/3\\4/3\\1/3\\1/2\\1\end{pmatrix}}*0,9+{\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}={\begin{pmatrix}9/10\\3/10\\6/5\\3/10\\9/20\\9/10\end{pmatrix}}+{\begin{pmatrix}1/10\\1/10\\1/10\\1/10\\1/10\\1/10\end{pmatrix}}={\begin{pmatrix}1\\2/5\\13/10\\2/5\\11/20\\1\end{pmatrix}}$

Vérifions que la matière totale n'a pas changé au bout des comptes. Les deux résultats donnent sensiblement la même chose, soit 9/2.

À partir de cette étape

Note 1 : Nœuds sans issue

Si en enlevant le lien sortant du nœud L1 vous vous retrouvez avec un nœud sans lien sortant, la matière dans ce nœud n'aura pas de destination et par conséquence la matière totale ne sera pas constante et aura tendance à s'anéantir. Garder la matière dans le nœud ne résout pas le problème, car on perd la correspondance entre importance du nœud et circulation de matière. C'est alors un peu le même problème des graphes non fortement connexes, et la bonne solution n'est pas si différente : si un nœud n'a pas de lien sortant, on va simplement imaginer qu'il n'a pas de préférence pour verser sa matière et donc on va la repartir également entre les autres nœuds. C'est à dire, un nœud sans lien sortant doit être traité comme un nœud avec des liens sortants vers tous les autres nœuds !

Graphe de blocs

• Pour construire un graphe de blocs, on partage les nœuds du graphe original en groupes qu'on appelle blocs. Chaque bloc représente alors un nœud dans le graphe de blocs, et chaque lien du graphe original devient un lien entre les blocs contenant les nœuds du graphe original participant au lien.

I. Pour votre réseau G, construisez en écrivant la matrice d'adjacence :

• Le graphe de blocs H1, ayant comme blocs B1 = {L1, plus L2, plus le premier des nœuds qui n'est pas L1 ou L2} et B2 = {les autres nœuds}.
• Le graphe de blocs H2, ayant comme blocs B1 = {L1, plus L2, plus le dernier des nœuds qui n'est pas L1 ou L2} et B2 = {les autres nœuds}.

II. Comparez les graphes de blocs H1 et H2 au graphe original G pour choisir celui d'entre eux qui simplifie G de façon la plus fidèle. Argumentez votre choix : il suffit d'expliquer votre raisonnement, il n'y a pas de « bonne réponse » et aucun calcul particulier n'est requis.

Bon travail !