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

Bonjour ! Bienvenue à l'activité E.

Votre réseau

Considérez le graphe du diapo 24 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

I. Identifiez les composantes fortement connexes du graphe.

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

Vecteur propre et PageRank

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 égale 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

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

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 ?

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. Exemple: un graphe orienté ayant nœuds A, B et C et liens (A, B), (B, C), (C, B), si partitionné entre les blocs B1={A, B} et B2={C}, donne lieu au graphe de blocs avec nœuds B1 et B2 et liens (B1, B1), (B1, B2), (B2, B1).

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 !

Activités