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). 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.
Les graphes
Notions
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).
Cela peut donc nous permettre 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 va pouvoir modéliser cela en mettant des flèches sur nos arêtes :
1 suit 3, et 3 suit 2
Rayon, diamètre et centre
L’avantage des graphes, c’est qu’on peut calculer des informations essentielles, notamment sur les réseaux sociaux. On peut calculer ce que l’on appelle un rayon, un diamètre et un centre.
Chacun va avoir sa propre utilité pour des calculs spécifiques.
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. Concrètement, 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. Concrètement, à 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. Cela signifie que 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.