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

Travail original

Partie I : Réseau unique

Pour cette partie, commencez par corriger votre activité A suivant la correction modèle pour l'activité A. Vous n'êtes pas obligés à utiliser une liste d'adjacence comme moi, vous pouvez très bien utiliser un dessin ou autre représentation. Et considérez le réseau de vos collègues également selon la correction, c'est-à-dire, construisez leur réseau correctement à partir de leurs récits, au lieu d'utiliser les représentations qu’ils sont proposé.

1. Trouvez deux collègues dont les réseaux de l'activité A ont des nœuds en commun avec le vôtre.

Keyi CHEN:

Keyi CHEN – (aime regarder) -> Friends

Keyi CHEN – (aime jouer) -> badminton

Keyi CHEN – (aime faire) -> natation

Martin LEMOULANT:

Martin LEMOULANT – (a visité) -> New York

2. Construisez un réseau unique à partir des trois réseaux, dans leurs versions sans propriétés.

Yibo MA – (aime écouter) -> Jackson WANG, Jay CHOU

Yibo MA – (a visité) -> Rome, Budapest

Yibo MA, Martin LEMOULANT – (a visité) -> New York

Yibo MA, Keyi CHEN – (aime jouer) -> Badminton

Yibo MA, Keyi CHEN – (aime faire) -> Natation

Yibo MA – (aime regarder) -> Two Broke Girls

Yibo MA, Keyi CHEN – (aime regarder) -> Friends

Jackson WANG – (joue dans le genre) -> rap

Jay CHOU – (joue dans le genre) -> pop

Rap – (est un cas de) -> genre de musique

Pop – (est un cas de) -> genre de musique

New York – (se trouve en) -> les États-Unis

New York – (est un cas de) -> ville

Les États-Unis – (est un cas de) -> pays

Rome – (se trouve en) -> Italie

Rome – (est un cas de) -> ville

Italie – (est un cas de) -> pays

Budapest – (se trouve en) -> Hongrie

Budapest – (est un cas de) -> ville

Hongrie – (est un cas de) -> pays

Badminton – (est un cas de) -> sport

Natation – (est un cas de) -> sport

Two Broke Girls – (est un cas de) -> série télévisé

Friends – (est un cas de) -> série télévisé

Partie II : Réseau projeté I (projection orientée)

1. Construisez un réseau projetant les nœuds les plus granulaires, auxquels les participants du cours sont liés, sur les autres. C'est-à-dire, dans Solstag -> Gloria Groove et Gloria Groove -> hip-hop, remplacez le nœud Gloria Groove par un lien orienté : Solstag -> hip-hop. Optionnellement, vous pouvez garder la raison de chaque lien sous forme d'une propriété : Solstag - (Gloria Groove) -> hip-hop.

Yibo MA – (Jackson WANG) -> rap

Yibo MA – (Jay CHOU) -> pop

Yibo MA – (Rome) -> Italie

Yibo MA – (Budapest) -> Hongrie

Yibo MA, Martin LEMOULANT – (New York) -> Les États-Unis

Yibo MA, Keyi CHEN – (Badminton, Natation) -> sport

Yibo MA – (Two Broke Girls) -> série télévisé

Yibo MA, Keyi CHEN – (Friends) -> série télévisé

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

Définition : les réseaux en graphe biparti quand on retrouve dans le graphe des groupes de nœuds qui ne se lient pas entre eux. On peut partager le graphe en deux et tous les liens du graphe coupent cette partition. Tous les graphes qui représentent des relations d’éléments contenant eux-mêmes d’autres éléments sont en bipartis.

Selon cette définition, on peut observer que c’est un réseau biparti.

Première partition : Yibo MA, Keyi CHEN, Martin LEMOULANT

Deuxième partition : rap, pop, Italie, Hongrie, Les États-Unis, sport, série télévisé

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

Voilà le matrice d'adjacence pour le réseau projeté I:Image 1

Partie III : Réseau projeté II (projection non-orientée)

1. À partir du réseau projeté I, construisez une nouvelle projection, cette fois sur les nœuds qui représentent les participants du cours. C'est-à-dire, remplacez les nœuds cibles par des liens non-orientés entre chaque pair de participants du cours ayant des cibles en commun : Solstag -> hip-hop et Marie -> hip-hop donne lieu à Solstag -- Marie.

Yibo MA -(Les États-Unis)- Martin LEMOULANT

Yibo MA -(sport, série télévisé)- Keyi CHEN

Yibo MA – (Jackson WANG) -> rap

Yibo MA – (Jay CHOU) -> pop

Yibo MA – (Rome) -> Italie

Yibo MA – (Budapest) -> Hongrie

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

Voilà le matrice d'adjacence pour le réseau projeté II:Image 2

Partie IV : Mesures locales

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

Réseau unique :

d^-(Yibo MA) = 0 d⁺(Yibo MA) = 9

d^-(Keyi CHEN) = 0 d⁺(Keyi CHEN) = 3

d^-(Martin LEMOULANT) = 0 d⁺(Martin LEMOULANT) = 1

d^-(Jackson WANG) = 1 d⁺(Jackson WANG) = 1

d^-(Jay CHOU) = 1 d⁺(Jay CHOU) = 1

d^-(rap) = 1 d⁺(rap) = 1

d^-(pop) = 1 d⁺(pop) = 1

d^-(genre de musique) = 2 d⁺(genre de musique) = 0

d^-(Rome) = 1 d⁺(Rome) = 2

d^-(Budapest) = 1 d⁺(Budapest) = 2

d^-(New York) = 1 d⁺(New York) = 2

d^-(Les États-Unis) = 1 d⁺(Les États-Unis) = 1

d^-(Hongrie) = 1 d⁺(Hongrie) = 1

d^-(Italie) = 1 d⁺(Italie) = 1

d^-(ville) = 3 d⁺(ville) = 0

d^-(pays) = 3 d⁺(pays) = 0

d^-(Badminton) = 1 d⁺(Badminton) = 1

d^-(Natation) = 1 d⁺(Natation) = 1

d^-(sport) = 2 d⁺(sport) = 0

d^-(Two Broke Girls) = 1 d⁺(Two Broke Girls) = 1

d^-(Friends) = 1 d⁺(Friends) = 1

d^-(série télévisé) = 2 d⁺(série télévisé) = 0

Réseau projeté I :

d^-(Yibo MA) = 0 d⁺(Yibo MA) = 7

d^-(Keyi CHEN) = 0 d⁺(Keyi CHEN) = 2

d^-(Martin LEMOULANT) = 0 d⁺(Martin LEMOULANT) = 1

d^-(rap) = 1 d⁺(rap) = 0

d^-(pop) = 1 d⁺(pop) = 0

d^-(Les États-Unis) = 2 d⁺(Les États-Unis) =0

d^-(Hongrie) = 1 d⁺(Hongrie) = 0

d^-(Italie) = 1 d⁺(Italie) = 0

d^-(sport) = 2 d⁺(sport) = 0

d^-(série télévisé) = 2 d⁺(série télévisé) = 0

Réseau projeté II :

d(Yibo MA) = 6

d(Keyi CHEN) = 1

d(Martin LEMOULANT) = 1

d^-(Hongrie) = 1 d⁺(Hongrie) = 0

d^-(Italie) = 1 d⁺(Italie) = 0

d^-(rap) = 1 d⁺(rap) = 0

d^-(pop) = 1 d⁺(pop) = 0

2. Pour le réseau projeté I, on peut calculer le degré à partir de la somme de lignes ou colonnes matrice d'adjacence. Expliquez.

Oui, on peut calculer le degré à partir de la somme de lignes ou colonnes de matrice d'adjacence.

Explication par le matrice : Image 3

3. Pour le réseau projeté II, on peut calculer les degrés sortant et entrant à partir de la somme de lignes ou colonnes matrice d'adjacence. Expliquez.

Oui, on peut calculer le degré à partir de la somme de lignes ou colonnes de matrice d'adjacence.

Explicationpar le matrice : Image 4

Partie V : Mesures globales

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

Définition : le diamètre, c’est la plus grande distance.

Réseau unique :

Δ{Yibo MA, Jackson WANG, Jay CHOU, rap, pop, genre de musique} = 3

Δ{Yibo MA, baminton, natation, sport} = 2

Δ{Keyi CHEN, baminton, natation, sport} = 2

Δ{Yibo MA, Friends, 2 Broke Girls, série télévisé} = 2

Δ{Yibo MA, Budapest, Rome, New York, Italie, Hongrie, Les États-Unis, pays} = 3

Δ{Yibo MA, Budapest, Rome, New York, ville} = 2

Δ{Martin LEMOULANT, New York, Les États-Unis, pays} = 3

Réseau projeté I :

Δ{Martin LEMOULANT, Les États-Unis} = 1

Δ{Keyi CHEN, sport, série télévisé} = 1

Δ{Yibo MA, rap, pop, série télévisé, sport, Italie, Hongrie, Les États-Unis} = 1

Réseau projeté II :

Il n’y a pas de diamètre pour le réseau projeté II, car il a des projections non-orientées et on ne peut pas trouver un chemin qui représente la plus grande distance.

Correction

Partie I

J'ai trouvé les réseaux de Martin Lemoulant et Keyi Chen qui ont des nœuds en commun avec le mien. Le réseau résultant est :

Participants

Yibo MA -> Jackson WANG, Jay CHOU, New York, Rome, Budapest, Badminton, Natation, Two Broke Girls, Friends

Keyi CHEN -> Lana Del Rey, XXXTentacion, Seoul, Dubrovnik, Barcelona, voyage, natation, badminton, Friends, Game of Throne, Rick&Morty

Martin LEMOULANT -> Gainsbourg, Georges Brassens, Kamaal Williams, Miles Davis, Underground Resistance, Drexciya, Istanbul, New-York, guitare, peinture, The Office

2. Autres nœuds

Jackson WANG -> rap

Jay CHOU -> pop

Rap -> genre de musique

Pop -> genre de musique

New York -> les États-Unis, ville

Les États-Unis -> pays

Rome -> Italie, ville

Italie -> pays

Budapest -> Hongrie, ville

Hongrie -> pays

Badminton -> sport

Natation -> sport

Two Broke Girls -> série télévisé

Friends -> série télévisé

Lana Del Rey -> Dream Pop

XXXTentacion -> Hip-hop

Dream Pop -> genre de musique

Hip-hop -> genre de musique

Seoul -> Corée du sud, ville

Corée du sud -> pays

Dubrovnik -> Croatie, ville

Croatie -> pays

Barcelona -> Espagne, ville

Espagne -> pays

Voyage -> activité

Game of Throne -> série télévisé

Rick&Morty -> série télévisé

Gainsbourg -> Chanson française

Brassens -> Chanson française

Kamaal Williams -> Jazz

Miles Davis -> Jazz

Underground Resistance -> Techno

Drexciya -> Techno

Chanson française -> genre de musique

Jazz -> genre de musique

Techno -> genre de musique

Istanbul -> Turquie, ville

Turquie -> pays

guitare -> instrument de musique

peinture -> activité

The Office -> série télévisé

Partie II

Avant de faire la projection, je note deux conséquences des instructions de l'activité A :

Le nœud "ville" ne porte pas vraiment de sens, car n'importe quel participants serait lié à ce nœud, donc je n'ajoute pas de lien "participant -> ville" lorsque je projette chaque ville (e.g. New York), c'est-à-dire je la projette uniquement vers son pays.

Pareil pour les nœuds "série télévisé" et "activité" (en effet, "instrument de musique" est aussi une activité), mais dans ce cas il ne m'est pas possible de projeter sans que ce soit sur ces nœuds, donc je garde les nœuds granulaires, sans projeter. Le résultat de la projection est :

Participants

Yibo Ma -> rap, pop, les États-Unis, Italie, Hongrie, natation, badminton, Friends, Two Broke Girls

Keyi CHEN -> Hip-hop, Dream Pop, Corée du sud, Croatie, Espagne, voyage, natation, badminton, Friends, Game of Throne, Rick&Morty

Martin LEMOULANT -> Chanson française, jazz, Techno, Turquie, États-Unis, guitare, peinture, The Office

2. Autres nœuds

Rap -> genre de musique

Pop -> genre de musique

Les États-Unis -> pays

Italie -> pays

Hongrie -> pays

Badminton -> sport

Natation -> sport

Two Broke Girls -> série télévisé

Friends -> série télévisé

Dream Pop -> genre de musique

Hip-hop -> genre de musique

Corée du sud -> pays

Croatie -> pays

Espagne -> pays

Voyage -> activité

Game of Throne -> série télévisé

Rick&Morty -> série télévisé

Chanson française -> genre de musique

Jazz -> genre de musique

Techno -> genre de musique

Turquie -> pays

guitare -> instrument de musique

peinture -> activité

The Office -> série télévisé

Construit de cette façon, 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 se connectent. En effet, pour chaque groupe, il n'y a 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).

Cependant, dans ce contexte on pourrait facilement enfreindre cette bipartition : il suffirait, par exemple, d'ajouter un lien entre "Dream Pop" et "Pop", ou "Game of Throne" et "Croatie", ou entre "Friends" et "Les États-Unis".

Le fait que le réseau soit biparti nous permet de considérer que les liens entre les deux partitions, alors on peut écrire la matrice d'adjacence en deux parties : liens de (1+3) vers (2), et liens de (2) vers (1+3).

Lien de (1+3) vers 2 : Image 1

Lien de 2 vers (1+3) : Image 2

Partie III

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 :

Yibo MA – (New York) – Martin LEMOULANT

Yibo MA – (natation) – Keyi CHEN

Yibo MA – (badminton) – Keyi CHEN

Yibo MA – (Friends) – Keyi CHEN

La matrice d’adjacence : Image 3

Partie IV

De la matrice d’adjacence

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

1. Les degrés pour le réseau unique

a. Degré sortant :

Participants :

11 : Martin LEMOULANT

11 : Keyi CHEN

9 : Yibo MA

Voisins des participants :

2 : (les villes)

1 : (autres)

Non-voisins des participants :

1 : (les pays), (les genres de musique)

0 : (autres)

b. Degré entrant :

Participants :

0 : (tous)

Voisins des participants :

2 : New York, natation, badminton, Friends

1 : (autres)

Non-voisins des participants :

7 : genre de musique

7 : villes

7 : pays

5 : série télévisé

2 : activité, sport, Jazz, chanson française, Techno

1 : (autres)

2. Les degrés pour le réseau projeté I

a. Degré sortant :

11 : Keyi CHEN

9 : Yibo MA

8 : Martin LEMOULANT

1 : (tous les nœuds de la partition (2))

0 : (tous les nœuds du groupe (3))

b. Degré entrant :

7 : genre de musique

7 : pays

5 : série télévisé

2 : sport, activité, natation, badminton, Friends, Les États-Unis

1 : instrument de musique, (les autres nœuds du groupe (2))

0 : (tous les nœuds du groupe (1))

3. Les degrés pour le réseau projeté II

a. Degré (non-orienté) :

4 : Yibo MA

3 : Keyi CHEN

1 : Martin LEMOULANT

Partie V

Le réseau unique et le réseau projeté I ne sont pas connexes. C'est-à-dire, ils ont plusieurs composantes fortement connexes. Donc le diamètre n'est pas défini pour ces réseaux.

Le réseau projeté II est un graphe complet, on peut calculer le diamètre qui est le plus grande distance.

Δ{Yibo MA, Keyi CHEN, Martin LEMOULANT } = 2

Voir Image 4 :