Aller au contenu

Rechercher sur le site

Échap pour fermer · Ctrl K ou ⌘ K pour ouvrir la recherche

ActivitéLes réseaux sociauxÉtape 3 sur 3

Activité — Réseaux sociaux et graphes

Capacités du programme abordées par cette ressource (2)

Ces capacités sont abordées par cette ressource. Cela ne signifie pas qu'elles sont entièrement couvertes : la couverture du programme relève d'une appréciation pédagogique.

  • Capacité 1Rayon, diamètre et centre d'un grapheDéterminer ces caractéristiques sur des graphes simples.
  • Capacité 2Notion de « petit monde ». Expérience de MilgramDécrire comment l'information présentée par les réseaux sociaux est conditionnée par le choix préalable de ses amis.

Objectif

Représenter un réseau social par un graphe, puis déterminer distance, excentricité, centre, rayon et diamètre.

Papier et crayon suffisent. Aucun compte, aucune donnée personnelle, aucun logiciel n’est nécessaire.

Partie A — Du texte au graphe

Un réseau social compte six abonnés : A, B, C, D, E et F.

  • A est ami avec B, C et D
  • B est ami avec A et D
  • C est ami avec A, D et E
  • D est ami avec tous les autres abonnés
  • E est ami avec C, D et F
  • F est ami avec D et E

L’amitié est réciproque : « X est ami avec Y » et « Y est ami avec X » sont la même relation.

  1. Cette description en toutes lettres est déjà pénible à lire pour six personnes. Combien de lignes faudrait-il pour un million d’abonnés ?
  2. Dessinez le graphe correspondant : un cercle par abonné (le sommet), un trait par relation d’amitié (l’arête).
  3. Combien ce graphe compte-t-il d’arêtes ? Vérifiez en les énumérant.
  4. Vérifiez votre dessin : chaque abonné doit avoir exactement le nombre de traits annoncé par la description.

Partie B — Distances

En vous appuyant sur votre graphe de la partie A :

  1. Donnez une chaîne reliant A à E. En existe-t-il plusieurs ?
  2. Quelle est la distance entre A et E ? Rappel : la distance est le nombre minimum d’arêtes. Vérifiez qu’aucune chaîne plus courte n’existe.
  3. A-D-E-F est une chaîne de A à F. Est-ce la distance de A à F ? Justifiez.
  4. Complétez le tableau des distances depuis chaque sommet :
depuis \ vers A B C D E F
A 0
B 0
C 0
D 0
E 0
F 0
  1. Ce tableau doit être symétrique. Pourquoi ? Servez-vous-en pour vérifier votre travail.

Partie C — Excentricité, centre, rayon, diamètre

Utilisez le tableau complété.

  1. L’excentricité d’un sommet est la distance maximale entre ce sommet et tous les autres. Sur votre tableau, c’est le plus grand nombre de sa ligne. Donnez l’excentricité des six sommets.
  2. Le centre est un sommet d’excentricité minimale. Quel est le centre de ce graphe ? Est-il unique ?
  3. Le rayon est l’excentricité d’un centre. Que vaut-il ici ?
  4. Le diamètre est la distance maximale entre deux sommets quelconques, c’est-à-dire le plus grand nombre de tout le tableau. Que vaut-il ?
  5. Rayon et diamètre sont-ils égaux ? Peuvent-ils l’être en général ?

Trois erreurs à éviter, à reformuler avec vos mots :

  • l’excentricité concerne un sommet, le diamètre concerne le graphe ;
  • l’excentricité et le diamètre sont des maximums, pas des moyennes ;
  • le centre n’est pas « le sommet qui a le plus d’amis » : c’est celui dont le plus éloigné des autres est le moins loin possible. Vérifiez sur ce graphe si les deux coïncident, et dites si cela prouve quelque chose en général.

Partie D — Un second graphe

Reprenez tout le travail avec ce réseau :

  • A est ami avec B et E
  • B est ami avec A et C
  • C est ami avec B, D et F
  • D est ami avec C, E et F
  • E est ami avec A, D et F
  • F est ami avec C, D et E
  1. Dessinez le graphe et comptez ses arêtes.
  2. Complétez le tableau des distances.
  3. Déterminez excentricités, centre(s), rayon et diamètre.
  4. Comparez avec le graphe de la partie A : lequel est le plus « resserré » ? Sur quel critère vous appuyez-vous ?

Partie E — Le petit monde

L’expérience de Milgram (1967) demandait à des personnes de faire parvenir une lettre à un inconnu en ne la transmettant qu’à une connaissance directe. Les chaînes qui ont abouti étaient courtes.

  1. Dans vos deux graphes, le diamètre est petit. Est-ce surprenant pour six sommets ? Cela suffit-il à parler de « petit monde » ?
  2. Le « petit monde » concerne les distances typiques dans de très grands réseaux. Pourquoi un graphe de six sommets ne permet-il pas de l’établir ?
  3. Sur un réseau social, votre fil dépend de qui vous suivez. Si vos contacts se ressemblent tous, quelles informations risquez-vous de ne jamais voir ?
  4. Proposez deux manières concrètes d’élargir volontairement ce que l’on voit.

Ce que vous devez rendre

  • Les deux graphes dessinés, avec le décompte des arêtes.
  • Les deux tableaux de distances complets et symétriques.
  • Excentricités, centre(s), rayon et diamètre pour les deux graphes.
  • Vos reformulations des trois erreurs à éviter (partie C).
  • Vos réponses argumentées de la partie E.

À retenir

  • La distance entre deux sommets est le nombre minimum d'arêtes qui les séparent.
  • L'excentricité d'un sommet est sa distance maximale à tous les autres ; le centre est un sommet d'excentricité minimale, et le rayon est l'excentricité d'un centre.
  • Le diamètre est la distance maximale entre deux sommets quelconques.

Ce thème dans la progression

Retour au thème Les réseaux sociaux