Modélisation d’un réseau social

Cette activité s’inscrit dans la thématique Les Réseaux Sociaux du programme de SNT. Elle est proposée par Claire Savinas, actuellement professeure de mathématiques et d’ICN au lycée Jean Vilar à Villeneuve-lès-Avignon. Claire Savinas assure également les formations académiques de SNT.

  • Contenu : Rayon, diamètre et centre d’un graphe.
  • Capacités attendues : Déterminer ces caractéristiques sur des graphes simples.

Découverte du problème à résoudre

Fanny utilise avec ses amis un réseau social. Elle a fait la liste des liens d’amitiés dans le tableau suivant. Une croix dans le tableau signifie que les deux personnes concernées partagent un lien d’amitié. L’objectif de cette activité est de modéliser ces liens d’amitié pour pouvoir ensuite les étudier.

  Fanny Chloé Robin Maéva Angie Matéi Julia
Fanny   X X       X
Chloé X   X X X X X
Robin X X       X  
Maéva   X     X   X
Angie   X   X     X
Matéi   X X        
Julia X X   X X    

Découverte de la notion de graphe

Pour étudier les liens d’amitié, on va utiliser une représentation sous forme de graphe.

Représentation sous forme de graphe

Question 1

Compléter le graphe ci-dessus où chaque arête signifie “… et …. sont amis”.
Chaque personne est représentée par un sommet et chaque lien d’amitié est représenté par une arête.

Voici le graphe complété
Graph complété

Découverte de l’écartement d’un sommet d’un graphe

On considère que seulement deux personnes amies peuvent communiquer entre elles. Fanny peut parler avec ses amis qui sont Chloé, Robin et Julia. Pour communiquer avec Maéva, elle doit passer par exemple par Chloé, ce qui fait une distance de 2. Pour parler à Angie, elle peut également passer par Chloé, ce qui fait également une distance de 2. Pour parler à Matéi, elle peut passer par Robin, ce qui fait également une distance de 2. La distance maximale entre Fanny et les autres personnes du graphe est de 2.

Question 2

Compléter le tableau ci-dessous avec la distance maximale, c’est-à-dire le nombre de liens d’amitié entre un sommet avec les autres sommets du graphe.

Fanny Chloé Robin Maéva Angie Matéi Julia
2            

Voici le tableau rempli.

Fanny Chloé Robin Maéva Angie Matéi Julia
2 1 2 2 2 2 2

Déterminer le ou les centres d’un graphe

Dans un graphe donné, le centre est le sommet dont l’écartement est minimal. Un graphe peut avoir plusieurs centres. Les centres d’un graphe sont alors les éléments à partir desquels l’information se diffuse le plus vite dans un réseau.

Question 3

Déterminer le centre de ce graphe.

D’après le tableau précédent, la distance minimale est détenue par Chloé qui est donc le centre du graphe.

Question 4

Interpréter la réponse précédente dans le contexte de l’activité.

Chloé est la personne qui devra passer par le moins d’intermédiaires pour joindre tout le groupe. Ici, elle est la seule qui puisse communiquer avec toutes les autres personnes directement.

Déterminer le rayon d’un graphe

Le rayon d’un graphe est l’écartement d’un centre du graphe.

Question 5

Déterminer le rayon de ce graphe.

Chloé est le centre du graphe. Son écartement est de 1. Le rayon du graphe est donc 1.

Question 6

Interpréter la réponse précédente dans le contexte de l’activité.

Le rayon est le nombre d’intermédiaires moins un pour joindre tout le groupe en partant du ou des centres du graphe.

Déterminer le diamètre d’un graphe

Dans un graphe donné, le diamètre est la plus longue distance entre deux sommets.

Question 7

Déterminer le diamètre de ce graphe.

D’après le tableau des distances établi en début d’activité, la distance maximale entre deux sommets est de 2. Le diamètre de ce graphe est donc 2.

Question 8

Interpréter la réponse précédente dans le contexte de l’activité.

Le diamètre du graphe est le nombre maximum d’intermédiaires moins un pour que deux personnes communiquent entre elles.

Déterminer le nombre de liens d’amitiés à utiliser pour contacter une personne.

Une chaîne d’un graphe est une liste ordonnée de sommets du graphe telle que chaque sommet de la liste soit adjacent au suivant. La longueur d’une chaîne est le nombre d’arêtes qui la composent. La distance entre deux sommets d’un graphe est la plus petite des longueurs des chaînes qui la relient.

La matrice d’adjacence associée à un graphe non orienté d’ordre $n$ dont les sommets sont numérotés de $1$ à $n$ est la
matrice carrée d’ordre $n$, où le terme figurant en ligne $i$ et colonne $j$ est égal au nombre d’arêtes reliant $i$ et $j$.

Question 9

Déterminer la matrice d’adjacence de ce graphe.

En conservant le même ordre de prénoms que dans le tableau, la matrice d’adjacence est la suivante :
$\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix}$
Sur la calculatrice :
Matrice sur la calculatrice

Soit M la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés. p désigne un nombre entier naturel. $\text{M}^p$ donne le nombre de chaı̂nes de longueur $p$ reliant $i$ et $j$.

Question 10

Saisir la matrice d’adjacence de ce graphe dans la calculatrice et calculer le carré de cette matrice.

Appuyez sur la touche shift puis sur la touche exp de la calculatrice pour créer une matrice. La remplir ensuite avec les coefficients et appuyer sur la touche square pour calculer le carré.
Carré d'une matrice

Question 11

Interpréter le coefficient $a_{1,2}$ du carré de la matrice d’adjacence.

$a_{1,2}=2$ donc il y a deux chaînes de longueur 2 qui relient Fanny et Chloé. Il s’agit de Fanny-Robin-Chloé et Fanny-Julia-Chloé.

Question 12

Interpréter le coefficient $a_{3,4}$ du carré de la matrice d’adjacence.

$a_{3,4}=1$ donc il n’y a qu’une seule chaîne de longueur 2 qui relie Robin et Maéva. Il s’agit de Robin-Chloé-Maéva.

Différence de fonctionnement entre Facebook et Twitter

Sur le réseau Facebook, pour être en relation, deux personnes inscrites doivent en effet s’accepter mutuellement comme “amis”, alors qu’il est possible sur Twitter, de suivre une personne inscrite sans que cela ne soit réciproque.
On peut représenter ces relations unilatérales par des graphes et modéliser le sens de la relation par une orientation de l’arête.