SNT Graphes

Identification

Infoforall

3 - Graphes et liaisons sociales


Les réseaux sociaux stockent des informations sur vous et vos gouts, c'est un fait.

Mais comment parvienent-ils à savoir qui connait qui ?

Encoder un texte, ok : un octet représente un caractère. 65 pour A, 66 pour B...

Encoder une image, ok. C'est plus compliqué mais nous avons vu que si on sait comment la suite d'octets a été créée, on peut retrouver l'image qu'ils encodent. C'est la partie photographie.

Mais ... des relations sociales... Ca s'encode comment cette histoire ?

Documents de cours : open document ou pdf

Evaluation ✎ : questions 09-10-11-12

1 - Graphes

Il existe un objet mathématique bien pratique permettant de faire cela : le graphe.

Imaginons qu'on veuille représenter une communauté de 7 personnes identifiées par une lettre : A, B, C, D, E, F et G.

L'une des façons les plus intuitives de représenter leurs relations est la suivante :

graphe représentant les relations

01° Sur ce graphe : Quels sont les gens qui connaissent A ? Quels sont les gens que connait A ?

...CORRECTION...

On voit qu'il y a un "lien" entre A et B, A et C et A et D.

On peut donc dire que A est connu de B, C et D.

On peut donc dire que A connait B, C et D.

graphe représentant les relations

02° Sur ce graphe : Quels sont les gens qui connaissent G ? Quels sont les gens que connait G ?

...CORRECTION...

On voit qu'il y a un "lien" entre G et F et G et E.

On peut donc dire que G est connu de E et F.

On peut donc dire que G connait E et F.

graphe représentant les relations

03° D'un point de vue purement comptable, A est-il plus populaire ou moins populaire que G 

...CORRECTION...

A possède 3 relations.

G possède 2 relations.

A est donc plus populaire que G.

graphe représentant les relations

04° A combien de poignées de mains A et G se situent-ils ?

...CORRECTION...

A connait D. D connait E. E connait G.

Nous avons donc trois poignées de main.

graphe représentant les relations
Graphes

Un graphe est un modèle abstrait constitué par :

  • des sommets (aussi appelés nœuds ou points)
    • Dans notre exemple : les personnes inscrites sur le réseau social
  • des arêtes (ou liens) reliant ces sommets
    • Dans notre exemple : les liens entre les personnes du réseau.

Que peut-on trouver comment informations sur graphe ?

  • Deux sommets reliés par une arête sont dits adjacents : les personnes se connaissent.
  • La longueur d'un chemin est le nombre d'arêtes successives à parcourir sur un chemin.
  • La distance ente deux utilisateurs : la plus petite longueur entre deux utilisateurs. Attention, il peut y avoir plusieurs chemins mais on prend le plus court chemin.
graphe représentant les relations

05° Trouver la distance entre l'utilisateur A et les autes : A-B, A-C...

...CORRECTION...

A - B vaut 1 : une seule arête.

A - C vaut 1 : une seule arête.

A - D vaut 1 : une seule arête.

A - E vaut 2 en passant par D.

A - F vaut 2 en passant par D ou B.

A - G vaut 3.

Graphes : caractérisation des sommets

Le degré d'un sommet est le nombre d'arêtes qui partent de ce sommet (ses liens).

L'excentricité d'un sommet est la distance la plus grande qu'on peut trouver à partir de ce sommet.

graphe représentant les relations

06° Trouver le degré et l'excentricité (la distance max entre ce sommet et le sommet le plus 'lointain') des différents sommets.

...CORRECTION...

A : degré 3 - excentricité 3 (c'est la distance AG).

B : degré 3 - excentricité 2.

C : degré 2 - excentricité 3.

D : degré 3 - excentricité 2.

E : degré 3 - excentricité 3.

F : degré 4 - excentricité 2.

G : degré 2 - excentricité 3.

07° Vous désirez toucher un maximum de personnes sur le réseau social précédent. Par quel utilisateur passer ? (on parlera d'influenceur)

...CORRECTION...

F est le meilleur choix : meilleur degré et meilleur excentricité. Au moins, c'est simple.

Graphes : caractérisation des graphes

On peut caractériser un graphe par son nombre de sommets : plus ils sont nombreux, plus le parcourir devient complexe.

On nomme ordre d'un graphe son nombre de sommets.

On nomme diamètre D d'un graphe l'excentricité maximale trouvée parmi les sommets.

On nomme rayon R d'un graphe l'excentricité minimale trouvée parmi les sommets.

On nomme centre d'un graphe un sommet dont l'excentricité correspond au rayon.

graphe représentant les relations

08° Trouver l'ordre, le diamètre et le rayon de ce graphe. Quels sont les sommets qu'on peut qualifier de centre ?

A : degré 3 - excentricité 3 (c'est la distance AG).

B : degré 3 - excentricité 2.

C : degré 2 - excentricité 3.

D : degré 3 - excentricité 2.

E : degré 3 - excentricité 3.

F : degré 4 - excentricité 2.

G : degré 2 - excentricité 3.

...CORRECTION...

On a 7 sommets. On dit donc que c'est un graphe d'ordre 7.

L'excentricité maximale est de 3 : on peut écrire que le diamètre est D = 3

L'excentricité minimale est de 4 : on peut écrire que le rayon est R = 2

On peut donc dire que les sommets B, D et F sont des sommets de ce graphe.

Attention, contrairement au cercle, on ne peut pas dire que D = 2 R !

Derrière tout ceci se cache une théorie informatique et mathématique permettant de faire beaucoup de choses. Nous allons la retrouver avec Internet, avec le choix de trajets sur une carte... Beaucoup de problèmes à priori non traitable par les mathématiques deviennent d'une grande simplicité lorsqu'on utilise l'outil adapté : le graphe !

L’experience de Milgram (1967) a consisté à contacter des inconnus pour leur demander celle des courriers qui doivent parvenir à un courtier par des échanges directs de la main à la main. Le courrier arrivera en quatre jours mais seulement 64 chaînes ne se sont pas rompues et en moyenne, il y avait 5,2 intermédiaires. De cette experience, il tire la théorie des Six degrés de séparation : tous les individus de la planète sont les sommets d’un graphe dont le diamètre est de longueur 6. Les réseaux sociaux permettent de réduire cette chaine à moins de 5 (Twitter : 4,67 ; Facebook 4,7) Si l’on vit dans le même pays, la France par exemple, cette chaine tombe à 3. Cette notion a fait l’objet d’un film Six degré de séparation par Fred Schepisi

2 - phénomène du petit monde

En 1929, le Hongrois Frigyes Karinthy évoque la possibilité suivante : nous sommes reliés à toute autre personne sur Terre par six poignées de main au maximum.

Vue d'artiste des 6 degrés
Vue d'artiste des 6 degrés de séparation Laurens van Lieshout / Public domain

Cela peut effectivement aller très vite : vous connaissez quelqu'un qui connait quelqu'un qui connait un homme politique ou d'affaires de premier rang. Celui-ci connait donc d'autres hommes de ce même milieu et on repart dans l'autre sens.

L’expérience de Milgram ou expérience du petit monde est une expérience réalisée entre 1960 et 1963 par le psychologue américain Stanley Milgram. On la nomme aussi l'expérience du petit monde.

Stanley Milgram
Stanley Milgram

Il a demandé à 60 personnes de joindre un destinataire bien précis. La méthode ?

Il devait écrire un courrier indiquant qui ils étaient (et éventuellement la liste des gens qui leur avait donné le courrier). Ce courrier devait ensuite être transmis à la main à son destinataire. On pouvait ainsi garantir le fait que les gens se connaissaient et garder la trace des communications.

Milgram publiera les résultats en déclarant qu'une lettre est parvenue au destinataire en quatre jours seulement. Néanmoins seul 5% des lettres parvinrent à destination au final. L'expérience n'en devint pas moins célèbre.

Avec les moyens modernes de communication, on peut beaucoup plus facilement faire des calculs sur les liaisons entre individus. Du moins, entre individus ayant accès à Internet !

Plusieurs études réalisées par Facebook ou Google montre qu'on s'approche maintenant plus de 4 degrés de séparation.

Attention, Milgram a également réalisé une expérience (portant le même nom du coup) liée au degré d'obéissance des individus.

3 - Exercices

Exercices Exercices

09° Trouver l'ordre, le diamètre D et le rayon R de ce graphe. Trouver le ou les centres. Pour cela, il faudra chercher l'excentricité minimale et maximale.

graphe de l'exercice

10° On parle parfois de ponts comme des connexions qui, si elles sont brisées, coupent les communications entre deux sous-graphes (on pourrait dire ici des communautés). Voyez-vous des ponts sur ces graphes ?

graphe de l'exercice

11° Tous les graphes que nous avons vu sont des graphes non orientés. Sont-ils capables de représenter les réseaux sur lesquels on peut suivre les publications de quelqu'un sans pour autant que cette personne ne vous suive ?

12° Quel sens pourriez-vous donner à ce graphe ?

graphe de l'exercice

Lorsqu'on parvient à créer des programmes sachant gérer et lire de tels graphes, on obtient un outil d'analyse de très grande puissance.

Activité publiée le 11 03 2020
Dernière modification : 11 03 2020
Auteur : ows. h.