Modélisation des Réseaux (M1 SIREN, 2021)/Activité E

Bonjour ! Bienvenue à l'activité E.

Votre réseau modifier

Considérez le graphe du diapo 25 de l'ensemble 3 :

Enlevez les nœuds "g" et "h".
Parmi les lettres [a, b, c, d, e, f], prenez la première et la dernière qu'apparaissent dans votre nom complet. On va las appeler L1 et L2.
- Par exemple, dans mon nom je trouve "a" (dans Alexandre) pour L1 et "d" (dans Abdo) pour L2.
Enlevez l'un des liens sortants du nœud L1.
Rajoutez un lien depuis un nœud autre que L1 vers le nœud L2.

Composantes modifier

I. Identifiez les composantes fortement connexes du graphe.

Proximité et intermédiairité modifier

I. Calculez la proximité de L1 et L2.

II. Calculez l'intermédiarité de L1 et L2.

Vecteur propre et PageRank modifier

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

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

Initialisez le vecteur de matière pour le calcul de la centralité de vecteur propre en la partageant également entre tous les nœuds.
- Pour simplifier le calcul vous pouvez choisir une quantité totale égal au nombre de nœuds, d'une telle sorte que chaque nœud est initialisé avec $1$ .
Pour une fois :
- Faites une itération pour tous les nœuds de l'algorithme pour e calcul de la centralité de vecteur propre (de façon matricielle ou manuelle).
- Multipliez 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.
Vérifiez que la matière totale n'a pas changé au bout des comptes.

Note 1 : Nœuds sans issue modifier

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 !

Note 2 : Question pour les curieux modifier

Il est aussi possible de représenter l'étape redistributive ("revenu universel") sous la forme d'une matrice qui multiplie le vecteur de matière. Quelle serait cette matrice ?

Bon travail !