Aller au contenu

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

Une page de Wikiversité, la communauté pédagogique libre.


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

  • Parmi les lettres [a, b, c, d, e, f, g, h], prenez la première et la dernière qu'apparaissent dans votre nom complet. On va las appeler L1 et 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.

Dans mon nom je trouve "a" (dans Alexandre) pour L1 et "d" (dans Abdo) pour L2. Voici le réseau résultant :

J'ai choisi d'enlever le lien (a, b) et ajouter le lien (f, d).


I. Identifiez les composantes fortement connexes.

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

  • {a, d, f} : avant l'enlèvement du lien (a, b) on y trouvait aussi les nœuds [b] et [e].
  • {b} : isolé de {a, d, f} et de {e} grâce à l'enlèvement du lien (a, b).
  • {c} : inchangé par les modifications; toujours pas possible de revenir depuis {g, h} ou d'aller vers {a, b, d, e, f}.
  • {e} : isolé de {a, d, f} et de {c} grâce à l'enlèvement du lien (a, b).
  • {g, h} : inchangé par les modifications; toujours pas possible d'aller vers {a, b, c, d, e, f}.


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

En ordonnant les nœuds par l'ordre alphabétique, Je construis la matrice d'adjacence, je normalise les lignes (je divise les sorties de chaque nœud par leur somme), et en suite je la transpose :

NOTE: il y a un petit erreur dans les matrices et calculs qui suivent - la ligne du nœud b dans la matrice contient un lien de b à d à la place du lien de b à e dans la figure.

, ,


II. Calculez deux itérations de PageRank avec s=0.9 :

  • Initialisez la matière pour le calcul de la centralité de vecteur propre, en la partageant également entre tous les nœuds.
  • Pour deux 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 manuelle ou matricielle).
    • 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 reste constante.

Le vecteur de matière initial sera :

Je le multiplie par :

Je multiplie la matière de chaque nœud par , puis j'y ajoute le partage égal entre les nœuds de de la matière :

Je vérifie la somme des matières dans le vecteur résultant :

Et tout va bien.

Je passe à le seconde itération :

Je vérifie la somme des matières dans le vecteur résultant :

Et c'est bon !


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 ?

Normalement on ne peut pas représenter une somme avec une multiplication, mais dans notre cas la somme est en réalité aussi une proportion des valeurs du vecteur. La matrice suivante équivaut à la procédure de redistribution :

Sur la diagonale, la partie reprend la fraction de la valeur d'un nœud pour lui-même. Puis, on prend pour chaque nœud la somme de de la valeur pour tous les nœuds y compris lui-même, ce qui équivaut pour un nombre de nœuds à prendre la N-ième partie (partage égal) de la fraction de la valeur totale : .

Plus généralement, pour un réseau à nœuds et avec on peut définir cette matrice comme .