Rayon, diamètre, centre et petit monde
Tu as des amis, qui ont eux-mêmes des amis. Combien de « poignées de main » faut-il pour relier deux élèves de France qui ne se connaissent pas ? Pour répondre, on dessine le réseau : des points et des traits. C'est un graphe.
Un réseau social est un graphe
Pour étudier un réseau social, on simplifie : chaque personne devient un point, chaque relation d'amitié devient un trait.
Une chaîne est une suite d'arêtes qui se suivent. Sa longueur est le nombre d'arêtes. La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie. Un graphe est connexe si l'on peut aller de n'importe quel sommet à n'importe quel autre.
Ici, la distance entre Alice et Chloé est 2 (Alice–Bruno, puis Bruno–Chloé). La distance entre Alice et Emma est 4.
Un réseau social de cinq amis est modélisé par un graphe. Les arêtes (relations d'amitié) sont : Alice–Bruno, Bruno–Chloé, Chloé–David, David–Emma. a) Dessiner…
Un réseau social de cinq amis est modélisé par un graphe. Les arêtes (relations d'amitié) sont : Alice–Bruno, Bruno–Chloé, Chloé–David, David–Emma.
- a) Dessiner mentalement ou sur papier ce graphe et donner la distance entre Alice et Emma.
- b) Donner la distance entre Alice et Chloé.
Excentricité, rayon, diamètre, centre
Pour décrire la « taille » d'un réseau, on utilise quatre notions.
Un sommet central est « bien placé » : de lui, tout le réseau est proche. Le diamètre, lui, dit à quel point le réseau est étendu.
Dans un graphe, l'excentricité d'un sommet est la plus grande distance qui le sépare des autres sommets. Les arêtes du graphe sont : A–B, A–C, A–D. a) Calculer…
Dans un graphe, l'excentricité d'un sommet est la plus grande distance qui le sépare des autres sommets. Les arêtes du graphe sont : A–B, A–C, A–D.
- a) Calculer l'excentricité de chacun des sommets A, B, C et D.
- b) En déduire le rayon et le diamètre du graphe.
Rappeler la définition du diamètre d'un graphe et celle du centre d'un graphe. Les appliquer au graphe en chaîne P–Q–R (arêtes P–Q et Q–R).
Rappeler la définition du diamètre d'un graphe et celle du centre d'un graphe. Les appliquer au graphe en chaîne P–Q–R (arêtes P–Q et Q–R).
Un groupe de six élèves d'un lycée de Lyon est modélisé par le graphe dont les arêtes sont : 1–2, 2–3, 3–4, 4–5, 5–6, 2–5. a) Calculer l'excentricité de chaque sommet.…
Un groupe de six élèves d'un lycée de Lyon est modélisé par le graphe dont les arêtes sont : 1–2, 2–3, 3–4, 4–5, 5–6, 2–5.
- a) Calculer l'excentricité de chaque sommet.
- b) Donner le rayon, le diamètre et le ou les centres du graphe.
Quand on ajoute une arête, ou des sommets
Ajouter une arête peut créer un raccourci : des distances diminuent, jamais elles n'augmentent. Le diamètre et le rayon peuvent donc baisser.
Deux bornes utiles pour un graphe connexe de $n$ sommets : le diamètre est au plus $n-1$ (cas de la chaîne, où l'on passe par tous les sommets) et au moins 1 dès qu'il y a au moins deux sommets. Un graphe où tout le monde est relié à tout le monde a pour diamètre 1 ; une « étoile » (un sommet relié à tous les autres) a pour diamètre 2.
Un graphe a pour sommets A, B, C, D, E, F, G et pour arêtes : A–B, B–C, C–D, D–E, E–F, F–G, C–F. a) Calculer l'excentricité de chaque sommet. b) Déterminer le rayon, le…
Un graphe a pour sommets A, B, C, D, E, F, G et pour arêtes : A–B, B–C, C–D, D–E, E–F, F–G, C–F.
- a) Calculer l'excentricité de chaque sommet.
- b) Déterminer le rayon, le diamètre et le centre.
- c) On ajoute l'arête A–G. Que deviennent le diamètre et le rayon ? Justifier.
On considère un graphe connexe de $n$ sommets. a) Montrer que son diamètre est au plus $n-1$. b) Donner un graphe à 6 sommets dont le diamètre vaut 5, puis un graphe à 6…
On considère un graphe connexe de $n$ sommets.
- a) Montrer que son diamètre est au plus $n-1$.
- b) Donner un graphe à 6 sommets dont le diamètre vaut 5, puis un graphe à 6 sommets dont le diamètre vaut 2. Justifier.
- c) Vérifier par le calcul que, pour le graphe en chaîne à 5 sommets, le diamètre est inférieur ou égal à deux fois le rayon.
Le petit monde
En 1967, le psychosociologue Stanley Milgram demande à des personnes de faire parvenir une lettre à un inconnu, en la transmettant seulement à une connaissance personnelle. Les chaînes qui arrivent comptent en moyenne environ 6 intermédiaires (soit environ 6 étapes) : c'est l'origine de l'expression « six degrés de séparation ».
On parle de petit monde quand un réseau très grand a un diamètre (ou une distance moyenne) très petit. Les réseaux sociaux en sont l'exemple : quelques « sauts » suffisent pour relier deux inconnus, même quand le réseau compte des milliards d'abonnés (de l'ordre de 2,9 milliards pour un grand réseau généraliste, 0,9 milliard pour un réseau professionnel, 0,45 milliard pour un réseau de messages courts).
Attention : ce que tu vois sur un réseau social dépend des amis et des abonnements que tu as choisis au départ. Tu vois surtout des contenus proches de ceux de ton entourage : c'est une bulle informationnelle.
Pourquoi un tel effet ? Le nombre de personnes atteintes croît très vite. Si chacun a 150 relations, on atteint environ 150 personnes en 1 étape, $150^2 = 22\,500$ en 2 étapes, $150^3 = 3\,375\,000$ en 3 étapes. Cette estimation est idéale : elle suppose que les amis de tes amis ne sont pas déjà les tiens, ce qui est faux en pratique.
En 1967, Stanley Milgram a demandé à des personnes de faire parvenir une lettre à un inconnu en la transmettant uniquement à une connaissance personnelle. Les chaînes…
En 1967, Stanley Milgram a demandé à des personnes de faire parvenir une lettre à un inconnu en la transmettant uniquement à une connaissance personnelle. Les chaînes abouties comptaient en moyenne environ 6 transmissions (soit environ 5 intermédiaires).
- a) Expliquer ce que cette expérience cherchait à montrer.
- b) Expliquer ce qu'on appelle un « petit monde » et pourquoi cette expérience n'en est pas une preuve absolue (citer une limite).
Un réseau social A compte 2,9 milliards d'abonnés, un réseau de messages courts B en compte 0,45 milliard et un réseau professionnel C en compte 0,9 milliard. On suppose…
Un réseau social A compte 2,9 milliards d'abonnés, un réseau de messages courts B en compte 0,45 milliard et un réseau professionnel C en compte 0,9 milliard. On suppose que dans chaque réseau le nombre moyen de relations par abonné est de 150 pour A, 200 pour B et 100 pour C.
- a) Calculer le nombre total approximatif de relations (arêtes) de chaque réseau, sachant que chaque relation est comptée une fois pour deux abonnés.
- b) Dans un réseau où chaque abonné a en moyenne 150 relations et où les relations sont « aléatoires », estimer le nombre de personnes atteintes en 2 étapes, puis en 3 étapes (ordre de grandeur $150^k$). Expliquer en quoi cela rend plausible le phénomène de petit monde.
- c) Expliquer pourquoi cette estimation surévalue la réalité dans un groupe d'amis très soudé (bonding).
Liens de cohésion et liens de pont
Tous les liens ne jouent pas le même rôle.
-
Le bonding (capital social de cohésion) : liens forts dans un groupe soudé (famille, club, classe) où tout le monde se connaît. Il apporte soutien et confiance.
-
Le bridging (capital social de pont) : liens vers un autre groupe. Il apporte des informations nouvelles, car ce contact connaît d'autres personnes que ton groupe.
Dans un graphe, un lien de pont est une arête qui relie deux groupes très denses : elle crée un raccourci et réduit les distances. C'est elle qui fait le « petit monde ».
Dans un lycée de Nantes, Léa a des liens très proches avec les 8 membres de son club de handball (qui se connaissent tous entre eux). Elle est aussi en contact avec…
Dans un lycée de Nantes, Léa a des liens très proches avec les 8 membres de son club de handball (qui se connaissent tous entre eux). Elle est aussi en contact avec Hugo, un cousin qui vit à Marseille et travaille dans un autre milieu.
- a) Dire quelle relation relève du « bonding » (capital social de cohésion) et laquelle du « bridging » (capital social de pont).
- b) Expliquer pourquoi le lien avec Hugo peut être plus utile pour trouver un stage dans un domaine inconnu du club.
Retour au début : deux inconnus sont en général reliés par quelques intermédiaires seulement, grâce aux liens de pont qui rendent le diamètre du réseau très petit.
L'essentiel
-
Un réseau social se modélise par un graphe : sommets = personnes, arêtes = relations.
-
La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie.
-
L'excentricité d'un sommet est sa plus grande distance aux autres ; le rayon est la plus petite excentricité, le diamètre la plus grande ; le centre regroupe les sommets d'excentricité égale au rayon.
-
Ajouter une arête ne peut que diminuer les distances.
-
Un petit monde est un grand réseau de petit diamètre (expérience de Milgram, 1967, environ 6 intermédiaires), avec des limites.
-
Les liens de bonding soudent un groupe ; les liens de bridging relient des groupes et raccourcissent les distances.