Cours sur les graphes
Point sociologique
En sciences humaines et sociales, l’expression "réseau social" désigne un agencement de liens entre des individus ou des organisations, constituant un groupement qui a un sens : la famille, les collègues, un groupe d’ami...
Avant d’être matérialisé de façon numérique, un réseau social représente donc les connexions humaines entre différents individus.
Un anthropologue britannique, Robin Dunbar, a indiqué qu’un être humain ne peut pas entretenir plus de 150 relations humaines stables avec d’autres individus. Au delà de ce nombre, les relations s’en retrouvent affectées.
It's a small world (after all)
Le "Petit Monde" a été une étude sociologique menée par le psychosociologue Milgram en 1967, introduisant le concept de distance "maximale" permettant de relier n’importe quels individus entre eux, par le biais d’une chaîne de relation.
Cette étude vérifie un postulat formulé en 1929, indiquant qu’il existe ce qu’on appelle les 6 degrés de séparation.
Autrement dit, nous sommes à une chaîne maximale de 6 relations de connaître n’importe qui dans le monde entier : "Je connais quelqu’un, qui connait quelqu’un, qui connait quelqu’un, qui connait quelqu’un, qui connait quelqu’un, qui connait un inuit en Arctique."
Avec l’avènement des réseaux sociaux, ce nombre s’est considérablement réduit !
En novembre 2011, Facebook a publié une étude menée sur 721 millions de personnes (nombre d’utilisateurs à l’époque), avec 69 milliards de liens d'amitié. Elle a pu démontrer que ce nombre de relation a pu se réduire à 4,71 relations "d’amitié" de connaître tout le monde sur Facebook.
En février 2016 avec 1.6 milliards d'utilisateurs, une nouvelle étude indique que ce nombre est descendu à 4,57.
En 2010, une étude indiquait que Twitter (X actuellement) avait une distance moyenne de 4,12 relations entre 2 individus.
Depuis une dizaine d’années, les grandes plateformes sociales ont de plus en plus encadré l’accès à leurs données d’amitiés/relations à grande échelle. Ainsi, bien que des études comme celle de Facebook (2016) existent, il est devenu beaucoup plus difficile pour les chercheurs externes d’obtenir des données complètes et à jour pour mesurer des indicateurs comme le “degré de séparation moyen”.
Les graphes
Notions de graphes
Les graphes sont une représentation schématique permettant de déterminer des liens entre différents objets.
On détermine ce que l’on appelle des sommets (les cercles numérotés dans l’exemple) reliés entre eux par des arêtes (les traits).
Ils permettent de schématiser l’ensemble des relations entre des individus.
La plupart des réseaux actuels implémentent un système de follower (individus qui nous suivent) et following (individus suivis).
On peut les modéliser en mettant des flèches sur nos arêtes :
1 suit 3, et 3 suit 2
Définitions sur les graphes
L’avantage des graphes, c’est qu’il est possible de calculer des informations essentielles, notamment sur les réseaux sociaux. Il y a un ensemble de notions à connaître :
- Distance
- Centre
- Excentricité
- Rayon
- Diamètre
Une distance entre 2 sommets correspond au nombre minimal d’arêtes entre ces 2 sommets, en prenant toujours les chemins les plus courts.
Le centre d’un graphe, c’est le sommet possédant la plus petite distance par rapport à tous les autres sommets du graphe.
L’excentricité d’un sommet est la distance maximale existante entre ce sommet et les autres sommets du graphe.
On cherche à savoir la distance entre ce sommet et le ou les sommets les plus éloignés.
Le rayon correspond à l’excentricité du centre du graphe.
À partir du centre du graphe, on essaie de voir par combien de sommets il faut passer pour arriver au(x) sommet(s) le(s) plus loin(s).
Le diamètre correspond à la distance maximale entre 2 sommets dans un graphe.
Tous les sommets sont accessibles entre eux avec au maximum cette distance.
Exemple
- L’excentricité : de Bastien est de 2, car sa distance maximale entre tous les sommets est de 2 ;
- Le centre : est Frank (ou Brice), car ils peuvent aller partout avec la plus petite distance;
- Le rayon : est de 2, car la distance entre Frank (ou Brice) entre tous les autres sommets est au maximum de 2 ;
- Le diamètre : est de 3 car si on calcule l’excentricité de tout le monde, on peut remarquer que l’excentricité de Nathan par exemple est de 3. Tous les sommets peuvent donc voir tous les autres sommets avec une distance maximale de 3.