Thème 05: Les réseaux sociaux⚓︎
1. Graphes et réseaux sociaux⚓︎
Un mini-réseau-social
Essayons de représenter des liens d'«amitié» (ou de connaissance) entre certaines personnes:
- Ahmed: ami avec Béatrice et Emma
- Béatrice: amie avec Ahmed, Camille et Dylan
- Camille: ami.e avec Béatrice et Dylan
- Dylan: ami avec Béatrice, Camille et Emma
- Emma: amie avec Ahmed, Dylan, Fanny et Greg
- Fanny: amie avec Emma et Greg
- Greg: ami avec Emma et Fanny
Graphe: structure d'objets appelés sommets (vertex) et dont certains sont en relation par des arêtes ou arcs (edges).
Histoire des graphes
D'autres types de graphes
Exemple: réseau routier, recherche du plus court chemin (GPS)
Exemple: réseau social asymétrique, problème d'ordonnancement des tâches
Exemple: algorithme PageRank de Google, modèle proie-prédateur
Exemple de problèmes
Un passeur doit faire traverser, d'une rive à l'autre, un loup, une chèvre et un chou. Sa barque ne lui permet que d'emporter un seul des trois objets à la fois et, bien entendu, il ne peut laisser ensemble loup et chèvre ni chèvre et chou.
Les sommets du graphe sont de 2 types :
- ceux qui correspondent à une situation possible sur la rive de départ avec le passeur
- ceux qui correspondent à une situation possible sur la rive de départ sans le passeur
Dans le graphe ci-contre, un état représente ce que le passeur a déjà pu transporter sur l’autre rive (« P » représente le passeur, « L » le loup, « C » la chèvre, et le chou a été noté par « S »):
Un barman aveugle propose un jeu à son client, pour lui offrir la prochaine tournée en cas de victoire.
- Il a devant lui un plateau avec 4 verres;
- à chaque tour, le barman fait retourner au client des verres;
- si tous les verres sont dans le même sens, le barman a gagné.
Bilan
Les graphes sont prépondérants dans:
- les réseaux (routiers, téléphoniques, sociaux, ...)
- les sciences : probabilités, physique, génétique, ...
- l'informatique
Modélisation d'un réseau social par un graphe pour:
- obtenir des indicateurs sur ce réseau
- faire des recommandations
- prévoir ce que feront les personnes
- influencer les comportements
2. Vocabulaire des graphes⚓︎
Lexique
Un chaîne est une suite de sommets adjacents reliés par des arêtes. Un cycle est une chaîne dont les sommets de départ et de fin sont les mêmes. Le nombre d'arêtes de la chaîne est sa longueur.
On parle plutôt de chemin lorsque le graphe est orienté.
Le degré d'un sommet est le nombre d'arêtes du sommet.
La distance entre deux sommets est la plus petite longueur des chaînes qui les relient.
L'excentricité d'un sommet est la distance au sommet le plus éloigné.
Le diamètre d'un graphe est la plus grande excentricité entre ses sommets.
Le centre d'un graphe est le sommet qui possède la plus petite excentricité. Il peut y en avoir plusieurs.
Un graphe est connexe s'il est d'un seul tenant: n'importe quelle paire de sommets peut toujours être reliée par une chaîne.
3. «Petit monde» de Milgram⚓︎