TP 2 Réseaux sociaux et Fakes News.

I/ Les graphes.

1/ Comment représenter, par ce que l'on appelle un graphe, les liens entre abonnés d'un réseau social?

Imaginons un réseau social ne possédant que 7 abonnés:

L est ami avec M,N,O et P M est ami avec L et P N est ami avec L, O et Q
O est ami avec L,N,P,Q et R P est ami avec O, L et M Q est ami avec O et N
R est ami avec O

On remarque, rapidement, que la descripion, ci-dessus, est peu explicite surtout pour 7 abonnés.

Imaginer pour un réseau comme Twitter avec ses 300 millions d'utilisateurs en mai 2018.

Ci-dessous : Une représentation plus visuelle pour nos 7 abonnés.

Graphe 1

2/ A vous.

Construisez un graphe à partir des informations ci-dessous:

A est ami avec B et E  B est ami avec A et C C est ami avec B, F et D
D est ami avec C, F et E E est ami avec A, D et F F est ami avec C,D et E


3/ Les propriétés d'un graphe.

graphe 2
  • La distance entre deux sommets d'un graphe est le nombre minimum d'arêtes pour aller de l'un à l'autre. La distance entre a et f est 2.
  • L'écartement (ou excentricité) d'un sommet est la distance maximale existante entre ce sommet et les autres sommets du graphe. Pour le sommet a, la plus grande distance avec un autre sommet est 2. L'écartement est donc de 2.
  • Le centre d'un graphe est le sommet d'écartement minimal (le centre n'est pas nécessairement unique). Ci-contre, tous les sommets ont un écartement de 2, sauf d qui a un écartement de 1. Le centre est donc d.
  • Le rayon d'un graphe est l'écartement d'un centre du graphe. Ici d est le centre et d a un écartement de 1. Donc le rayon est de 1.
  • Le diamètre d'un graphe est la distance maximale entre deux sommets du graphe. Ici le diamètre est de 2.

4/ A vous.

graphe 3 Déterminez sur le graphe suivant:
  • Le (ou les) centre(s)
  • Le rayon
  • Le diamètre


II/ Expérience du petit monde de Milgram.

Visionner la vidéo suivante:

milgram

Selon l'expérience de Milgram, nous sommes connectés aux autres avec combien d'intermédiaires en moyenne?

Si on considère le monde comme un graphe où chaque personne est un sommet du graphe et chaque relation (A "connait" B) est une arête du graphe, quel est l'écartement (ou excxentricité) moyen d'un sommet quelconque par rapport à un autre d'après la théorie de Milgram?

Depuis l'apparition des réseaux sociaux, à combien d'intermédiares en moyenne nous trouvons-nous les uns des autres?