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

Mon réseau modifier

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.

Réponse modifier

Mon L1 est le nœud a et mon L2 est le nœud d. J'enlève le lien (a, b) J'ajoute un lien (f, d).

Voici mon graphe :

 
J'enlève un lien sortant de mon nœud L1 - je choisis (a, b) - et j'ajoute un lien vers mon nœud L2 - je choisis (f, d).

Composantes modifier

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 ?

Réponse modifier

I. Les composantes sont : {a, d, f}, {b}, {c}, {e}.

II. On voit que la composante {b} verse sa matière vers {c} et {e} et ne reçoit pas d'autre matière, que la composante {e} ne reçoit que de {b} et qu'elle verse sa matière dans {a, d, f}, et que {a, d, f} à son tour ne reçoit que de {e} et verse as matière vers {c}. On en conclut que la composante {c} va concentrer toute la matière, et donc toute la centralité de vecteur propre du réseau.

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   :

  • 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  .
  • 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  , puis partagez également   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.

Réponse modifier

I. Plaçant les nœuds ordonnées alphabétiquement, on obtient la matrice   :

 ,  ,  

II.

J'initialise mon vecteur de matière distribuant également une matière totale de   :

 

Je procède au calcul d'une itération de la centralité de vecteur propre :

 

Même avant la multiplication par le facteur redistributif s, je note que la matière totale est passée à ...   ?! Ce n'est pas bien.

Ah, je lis la note sur les « nœuds sans issue » et je me rends compte que mon nœud c n'a pas d'issue ! Il faut alors suivre l'instruction et traiter le nœud c comme s'il était connecté à tous les autres nœuds, pour distribuer également sa matière entre eux. Comme ça on obtient une nouvelle matrice   :

 ,  ,  

Et donc le nouveau calcul de l'itération :

 

Pour une matière totale après l'itération de ... 6 ! Elle reste inchangé, comme on voulait.

On peut alors effectuer l'étape de redistribution, pour éviter que le risque que la matière se concentre uniquement dans quelques composantes fortement connexes du graphe vers lesquelles elle rentrerait mais ne sortirait pas.

 

On vérifie que la matière totale est ... 6 ! Super !

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 ?

Réponse modifier

Attribuer à chaque nœud une partie   de la matière de chacun des nœuds, cela correspond à une matrice où tous les éléments sont  , où   est le nombre de nœuds du graphe.

Comme on veut aussi garder une partie   de la matière de chaque nœud dans le nœud lui-même, il faut ajouter ce terme   à la diagonale de la matrice.

Dans notre cas, pour   (et donc  ) on obtient alors la matrice de redistribution :

 

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

Graphe de blocs modifier

  • 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.

Réponse modifier

I.

Je prends la matrice d'adjacence de mon graphe :

 

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=d} et B2 = {c, e, f}

Liens entre les blocs
B1 B2
B1 (a,d), (a,c), (b, c), (b, e), (d,c), (d, f)
B2 (e,a), (f,a), (f,d)

J'obtiens par le nombre de liens la matrice d'adjacence :

Matrice d'adjacence
B1 B2
B1 1 5
B2 3 0

Pour H2: B1 = {L1=a, L2=d, f}, B2 = {b, c, e}

Liens entre les blocs
B1 B2
B1 (a,d), (d, f), (f,a), (f,d) (a,c), (d,c)
B2 (e,a) (b, c), (b, e)

J'obtiens par le nombre de liens la matrice d'adjacence :

Matrice d'adjacence
B1 B2
B1 4 2
B2 1 2

II. De façon un peu naïve, on pourrait dire que : étant donné que les nombres de nœuds dans les blocs des partitions H1 et H2 sont égaux, et que donc on n'a pas à se soucier des effets de nombre, la partition H1 est plus intéressante car elle met en évidence des tendances plus fortes dans le réseau : dans H1, le bloc B2 ne se connecte qu'à B1, et le bloc B1 se connecte de façon cinq fois plus intense à B2 qu'à soi-même. Si on se souvient du concept de bipartition, ça nous montre quasiment une bipartition du réseau. Tandis que, pour la partition H2, les tendances sont moins claires, avec le double de connexions de B1 à B1 que à B2, et de B2 à B2 que à B1. Donc on dirait que la partition H1 capture de façon plus fidèle la structure du réseau.

Une façon plus rigoureuse de voir ce problème est de se poser la question : 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 ? Cette question ce traduit en dans combien de façons différentes je pourrai les redistribuer, la bonne façon étant l'une des possibilités. Le plus de façons de redistribuer, le moins de chance qu'on tombe sur la bonne. Comme les blocs ont tous la même taille 3, les liens possibles entre deux blocs sont 3 * 3 = 9, et donc le nombre de façons de distribuer les liens entre blocs vers les nœuds est le nombre de combinaisons de 9 possibilités N à N, où N est le nombre de liens à apporter, ce qui correspond à la valeur entre les deux blocs dans la matrice d'adjacence. Comme le nombre de combinaisons se réduit quand on est proche des extrêmes*, c'est la partition en blocs H1, avec ça matrice d'adjacence à valeurs plus caractéristiques (1, 5, 3, 0), contre les valeurs plutôt moyens (4, 2, 1, 2) de la partition H2, qui nous permet de reconstruire le graphe original entre nœuds avec une plus grande probabilité.

* Voyez que zéro liens ne se choisissent que d'une seule façon, ainsi que tous les 9 liens ne se choisissent que d'une seule façon; quand 1 lien se choisit de 9 façons, et 8 liens c'est pareil à choisir le seul lien pas choisi; le nombre de possibilités grandit quand on se rapproche d'un distribution égale entre liens choisis et pas choisis, comme le volume d'un carré quand on se rapproche d'une distribution égale de la taille totale de ses arêtes. La formule explicite pour ce qu'on appelle une k-combinaison est   (on l'avait rencontré, avec k=2, lors du calcul de la transitivité).