Modélisation des Réseaux (M1 SIREN, 2020)/Activité D

Bonjour, et bienvenue à l'Activité D 🙃 !

L'objectif, on se trompe pas, est de travailler la compréhension du contenu des dernières séances sur les mesures et centralités.

Instructions[modifier | modifier le wikicode]

Partez de votre Réseau projeté II de l'activité B, et cherchez deux autres Réseau projeté II de vos collègues, d'une telle sorte que l'union des trois résulte un graphe connexe.

C'est-à-dire, ce nouveau graphe est formé d'une seule composante connexe. Autrement dit, il existe un chemin entre n'importe quels pair de nœuds du réseau.

En suite, pour ce nouveau réseau :

1. Faites le tableau et le graphique pour la distribution de degrés.

2. Faites le tableau et le graphique pour la corrélation de voisins entre degré et degré.

3. À partir de ce graphique, peut-on dire que le réseau, concernant le degré des nœuds, est assortatif ou dissortatif ?

4. Calculez le coefficient de clustering pour les nœuds.

5. Faites le tableau et graphique pour la corrélation combiné entre degré et coefficient de clustering.

6. Essayez d'expliquer ce que vous observez dans ces trois tableaux et graphiques.

7. Si possible, choisissez un nœud à coefficient de clustering plus petit que 1. Trouvez le plus petit ensemble de liens que vous pouvez ajouter dans votre réseau pour que ce nœud aie un coefficient de clustering égal à 1.

8. Si possible, choisissez un nœud à coefficient de clustering égal à 1. Trouvez le plus grand ensemble de liens que vous pouvez retirer du réseau sans modifier ni le nombre de voisins ni le coefficient de clustering de ce nœud.

9. Quels nœuds du réseau pensez-vous avoir la plus grande et plus petite proximité ? Et pour l'intermédiarité ? Justifiez.

Notes[modifier | modifier le wikicode]

I. Dans ce réseau vous trouverez potentiellement des liens multiples, c'est à dire plusieurs liens entre les mêmes nœuds (et dans la même direction, si dans un graphe orienté, mais ce n'est pas le cas ici). Rappelons qu'on appelle un graphe où l'on trouve des liens multiples un multigraphe, en opposition à un graphe simple.

La définition du degré doit prendre en compte ces liens. Sinon, on parlerait plutôt du nombre de voisins, ou d'une transformation préalable du réseau pour le rendre un graphe simple avant de calculer les quantités. Alors, dans un multigraphe, on peut toujours utiliser le nombre de voisins $N(v)$ à la place du degré $d(v)$ quand on ne veut pas prendre en compte la multiplicité des liens. En pratique, travailler avec le degré ou le nombre de voisins, voire avec un multigraphe ou un graphe simple, reste toujours un choix à considérer en fonction du sens qu'on veut retrouver dans les mesures.

Par exemple, parfois la multiplicité de liens représente l'intensité du rapport entre deux nœuds, donc la question devienne si on veut prendre en compte l'intensité ou juste l'existence d'un rapport. Dans un réseau d'achat de produits, ce serait la différence entre les questions « qui a déjà testé un produit ? » et « qui a l'habitude de l'acheter ? ».

II. On définit la corrélation de voisins entre degré et degré comme une fonction qu'à chaque degré $D$ correspond une valeur que se calcule comme ça :

pour chaque degré
1. considère tous les nœuds ayant ce degré
2. pour chacun de ces nœuds
  1. calcule la moyenne du degré des voisins de ce nœud
3. calcule la moyenne de ces moyennes pour obtenir la valeur pour le degré

La formule explicite pour un graphe avec nœuds et liens $G=(V,E)$ , et avec la notation $N(i)$ pour l'ensemble des voisins de $i$ :

$Corr_{d}^{d/N}(D)={\frac {\sum _{i\in V,d(i)=D}{\frac {\sum _{j\in N(i)}d(j)}{\left\vert N(i)\right\vert }}}{\left\vert i\in V,d(i)=D\right\vert }}$

III. On définit la corrélation combiné entre deux propriétés des nœuds comme la moyenne de la deuxième propriété pour tous les nœuds ayant la même valeur pour la première propriété. La formula explicite pour deux propriétés $p$ et $q$ est :

$Corr_{p}^{q}(P)={\frac {\sum _{i\in V,p(i)=P}q(i)}{\left\vert i\in V,p(i)=P\right\vert }}$

Bon travail, et n'hésitez pas à poser vos questions dans l'onglet Discussion de cette page.

.~´

Activités[modifier | modifier le wikicode]