Utilisateur:Fanny Sauvee/Modélisation des Réseaux (M1 SIREN, 2021)/Activité B

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


Partie I : Réseau unique[modifier | modifier le wikicode][modifier | modifier le wikicode]

  1. Trouvez deux collègues dont les réseaux de l'activité A ont des nœuds en commun avec le votre.
  2. Construisez un réseau unique à partir des trois réseaux, dans leurs versions sans propriétés.

J'ai choisi de construire un réseau unique à partir du réseau de Yibo MA, et Lisa NGO avec qui j'ai certains noeuds en commun : la série Prison Break avec Lisa, et la ville Rome avec Yibo ainsi que les genres de musique pop et rap.

J'obtiens :

Fanny, Yibo, Lisa -> Russ, Parcels, Oscar Anton, Seoul, Rome, cuisine, crossfit, Prison Break, Itaewon Class, Johnny Hallyday, Palerme, Madrid, Barcelone, Olbia, Le Serpent, Yoga, Peinture, Jackson WANG, Jay CHOU, New York, Budapest, Badminton, Natation, Two Broke Girls, Friends

Partie II : Réseau projeté I (projection orienté)[modifier | modifier le wikicode][modifier | modifier le wikicode]

  1. Construction d'un réseau projetant les nœuds les plus granulaires, auxquels les participants du cours sont liées, sur les autres.

Je garde la raison de chaque lien sous forme d'une propriété. Etant liés sur les genres Pop et Rap, la ville Rome et la série Prison Break, cela me donne :

Fanny -(Oscar Anton)-> Pop Yibo - (Jay CHOU) -> Pop Fanny -(Russ)-> Rap Yibo -(Jackson WANG)-> Rap Fanny -(Rome) -> Pays Yibo -(Rome) -> Pays Fanny -(Prison Break)-> Série Lisa -(Prison Break)-> Série .


  1. Est-ce un réseau biparti ? Si oui, que représentent les deux partitions ?

Un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints X et Y tels que chaque arête ait une extrémité dans X et l'autre dans Y. Un graphe biparti permet notamment de représenter une relation binaire. Ici, je n'ai pas de réseau biparti car chaque sommet va soit vers Yibo, soit vers Fanny, soit vers Lisa, on a donc 3 ensembles et non deux.

  1. Représentez ce réseau sous forme d'une matrice d'adjacence.

Partie III : Réseau projeté II (projection non-orienté)[modifier | modifier le wikicode][modifier | modifier le wikicode]

  1. A partir du réseau projeté I, construisez une nouvelle projection, cette fois sur les nœuds qui représentent les participants du cours.

Fanny -> pop et Yibo -> pop donne lieu à Yibo -- Fanny . Fanny -> rap et Yibo -> rap donne lieu aussi à Yibo -- Fanny . Fanny -> Prison break et Lisa -> Prison Break donne lieu à Lisa -- Fanny Fanny -> Italie et Yibo -> Italie donne lieu à Yibo -- Fanny .

  1. Représentez ce réseau sous forme d'une matrice d'adjacence.

Partie III : Mesures locales[modifier | modifier le wikicode][modifier | modifier le wikicode]

  1. Pour chacun des réseaux : réseau unique, réseau projeté I, réseau projeté II.
    1. Calculez le degré des nœuds. Le cas échéant, leurs degrés sortant et entrant.

Réseau unique : pas de degrés entrants/sortants.

Réseau projeté I :[modifier | modifier le wikicode]

d(Yibo) = 3 (sortants)

d(Fanny)= 4 (sortants)

d(Lisa) = 1 (sortant)

d(Pop) = 2 (entrants)

d(Rap) = 2 (entrants)

d(Prison Break) = 2 (entrants)

d(Pays) = 2 (entrants)

Réseau projeté II :[modifier | modifier le wikicode]

d(Yibo) = 4 et 3 orientés (sortants)

d(Fanny)= 6, et 4 orientés (sortants)

d(Lisa) = 2, et 1 orienté (sortant)

d(Pop) = 2 (entrants)

d(Rap) = 2 (entrants)

d(Prison Break) = 2 (entrants)

d(Pays) = 2 (entrants)

Partie IV : Mesures globales[modifier | modifier le wikicode][modifier | modifier le wikicode]

  1. Pour chacun des réseaux : réseau unique, réseau projeté I, réseau projeté II.
    1. Si possible, calculez le diamètre du réseau. Si non, justifiez pourquoi il n'y a pas de diamètre.

Réseau unique : diamètre = 2

Réseau projeté I : diamètre = 1

Réseau projeté II : diamètre = 1


=== CORRECTION === Je n'avais pas bien compris les consignes, je corrige donc la totalité :

PARTIE I[modifier | modifier le wikicode]

Les réseaux ayant le plus de noeuds en commun avec le mien sont ceux de Lisa NGO et Yibo MA :

  1. Participants

Fanny -> Russ, Parcels, Oscar Anton, Seoul, Rome, cuisine, crossfit, Prison Break, Itaewon Class Lisa -> Johnny Hallyday, Palerme, Madrid, Barcelone, Olbia, Prison Break, Le Serpent, Yoga, Peinture Yibo MA -> Jackson WANG, Jay CHOU, New York, Rome, Budapest, Badminton, Natation, Friends, Two Broke Girls

  1. Autres nœuds

Russ -> Rap Parcels -> Alternative Oscar Anton -> Pop Rap -> genre de musique Pop -> genre de musique Corée du Sud -> Pays Italie -> Pays Seoul -> Corée du Sud, ville Rome -> Italie, ville Cuisine -> Activité manuelle Crossfit -> Sport Prison Break -> série télévisée Itaewon Class -> série télévisée Johnny Hallyday -> Variété française Variété française -> genre de musique Palerme -> Italie, ville Oblia -> Italie, ville Madrid -> Espagne, ville Barcelone -> Espagne, ville Espagne -> Pays Le Serpent -> série télévisé Yoga -> sport Peinture -> activité manuelle Jackson WANG -> rap Jay CHOU -> pop New York -> États-Unis, ville États-Unis -> pays Budapest -> Hongrie, ville Hongrie -> pays Badminton -> sport Natation -> sport Two Broke Girls -> série télévisé Friends -> série télévisé

PARTIE II[modifier | modifier le wikicode]

Projection :

# Participants
Fanny -> rap, pop, alternative, Corée du Sud, Italie,  sport, cuisine, Prison Break, Itaewon Class
YiboMA -> rap, pop, Italie, États-Unis, Hongrie, sport, Two Broke Girls, Friends.
LisaNGO -> variété française, Italie, Espagne, sport, peinture, Prison Break, Le Serpent

# Autres nœuds
Italie -> pays
Hongrie -> pays 
États-Unis -> pays 
Corée du Sud -> pays 
Espagne -> pays
rap -> genre de musique
pop -> genre de musique
alternative -> genre de musique 
variété française -> genre de musique
cuisine -> activité 
peinture -> activité
Two Broke Girls -> série télévisé
Itaewon Class -> série télévisé
Prison Break -> série télévisé 
Le Serpent -> série télévisé
Friends -> série télévisé


Ici, ce réseau est biparti, mais ce n'est pas très évident. Considérons les trois groupes de nœuds : (1) les participants, (2) les nœuds vers lesquels les participants se connectent, et (3) les nœuds vers lesquels ces derniers ce connectent. En effet, pour chaque groupe, il n'y pas de lien entre les membres du groupe. Et comme il n'y a pas de lien entre les membres de (1) et (3) non plus, on peut les unir pour obtenir alors la bipartition : (1+3) et (2).

Le réseau étant biparti, on peut écrire la matrice d'adjacence en deux parties : liens de (1+3) vers (2), et liens de (2) vers (1+3).

Liens de (1+3) vers (2)
variété française Corée du Sud États-Unis Espagne Friends Itaewon Class rap pop alternative Two Broke Girls Prison Break sport Italie Le Serpent Hongrie peinture cuisine
Fanny 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 1
LisaNGO 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0
YiboMA 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0
(nœuds de (3)) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Liens de (2) vers (1+3)
(nœuds de (1)) pays genre de musique série télévisé activité
Italie 0 1 0 0 0
chanson française 0 0 1 0 0
Corée du Sud 0 1 0 0 0
États-Unis 0 1 0 0 0
Friends 0 0 0 1 0
funk brésilien 0 0 1 0 0
rap 0 0 1 0 0
Itaewon Class 0 0 0 1 0
pop 0 0 1 0 0
alternative 0 0 1 0 0
cuisine 0 0 0 0 1
variété française 0 0 1 0 0
Prison Break 0 0 0 1 0
peinture 0 0 0 0 1
Hongrie 0 1 0 0 0
Two Broke Girls 0 0 0 1 0
Le Serpent 0 0 0 1 0

Partie III[modifier | modifier le wikicode]

Le réseau non-orienté résultant, pour lequel je choisis de garder la raison des liens comme propriétés et de représenter différentes raisons par des liens multiples :

Fanny -(pop)- YiboMA
Fanny (rap)- YiboMA
Fanny- (Prison Break)- LisaNGO
Fanny -(Italie)- YiboMA
Fanny -(Italie)- LisaNGO
LisaNGO -(Italie)- YiboMA
Fanny -(sport)- YiboMA
Fanny -(sport)- LisaNGO
LisaNGO -(sport)- YiboMA


La matrice d'adjacence :

Fanny LisaNGO YiboMA
Fanny 0 3 4
LisaNGO 3 0 2
YiboMA 4 2 0


Partie IV[modifier | modifier le wikicode]

De la matrice d'adjacence[modifier | modifier le wikicode]

  • Si le graphe est orienté :
    • Le degré sortant d'un nœud est la somme de la ligne qui lui correspond.
    • Le degré entrant est la somme de la colonne correspondante.
  • Si le graphe est non-orienté :
    • La matrice est symétrique et on peut sommer soit la ligne, soit la colonne, puisque ces valeurs seront toujours égales.

Degrés[modifier | modifier le wikicode]

Les degrés pour le réseau unique[modifier | modifier le wikicode]

  • Degré sortant :
    • Participants :
      • 9 : Fanny
      • 9 : YiboMA
      • 9 : LisaNGO
    • Voisins des participants :
      • 4 : (les villes)
      • 1 : (autres)
    • Non-voisins des participants :
      • 1 : (pays), (genres de musique)
      • 0 : (autres)
  • Degré entrant :
    • Participants :
      • 0 : (tous)
    • Voisins des participants :
      • 3 : cuisine, peinture, Two Broke Girls
      • 1 : (autres)
    • Non-voisins des participants :
      • 6 : villes
      • 5 : série télévisé
      • 4 : pays, genre de musique
      • 3 : alternative
      • 1 : (autres)

Les degrés pour le réseau projeté I[modifier | modifier le wikicode]

  • Degré sortant :
    • 9 : Fanny
    • 7 : Yibo MA
    • 7 : Lisa NGO
    • 1 : (tous les nœuds de la partition (2))
    • 0 : (tous les nœuds du groupe (3))
  • Degré entrant :
    • 5 : pays, série télévisé
    • 4 : genre de musique
    • 3 : Italie
    • 2 : pop, rap, Prison Break,
    • 1 : activité, (les autres nœuds du groupe (2))
    • 0 : (tous les nœuds du groupe (1))

Les degrés pour le réseau projeté II[modifier | modifier le wikicode]

  • Degré (non-orienté) :
    • 4 : (tous les nœuds)

Partie V[modifier | modifier le wikicode]

Diamètre non défini car le réseau unique et le réseau projeté I ne sont pas connexes. (ils ont plusieurs composantes fortement connexes). Le réseau projeté II est un graphe complet, tous les nœuds se lient entre eux, et donc le diamètre est 1.