Illustration de quelques possibilités du langage Wolfram pour analyser des graphes.
Avec le développement de l’informatique, la théorie des graphes a été implantée dans des algorithmes permettant de modéliser la propagation des informations sur les réseaux sociaux. La réussite de la diffusion d’une information dépend du nombre de personnes mises au courant mais aussi de la rapidité de la propagation. La modélisation de la propagation des informations a battu en brèche une idée tenace : avoir de nombreux amis sur Facebook ne fait pas de vous un personnage influent.
La Recherche n°498, avril 2015, p. 40 et 42.
Un réseau social peut être représenté par un graphe. Chaque point du graphe correspond à un contact et les liens entre les points font apparaître les relations qu’ils entretiennent.
- Centre d’un graphe
Le centre d’un graphe donne l’ensemble des sommets d’excentricité minimale. Dans un réseau social, ce sont des personnes étroitement liées entre elles.
- Clique d’un graphe
La clique d’un graphe est l’ensemble maximal de sommets formant un sous-graphe complet, c’est-à-dire un sous-graphe dont les sommets sont tous reliés deux à deux par une arête. Une clique permet d’identifier les groupes ou les communautés soudés au sein d’un réseau social.
- Couverture d’un graphe par les liens
La couverture d’un graphe par liens donne l’ensemble minimal de liens touchant tous les sommets. La rupture de ces liens met en péril le réseau.
- Couverture d’un graphe par les sommets
La couverture d’un graphe par sommets donne l’ensemble minimal de sommets touchant tous les liens. Ces sommets sont les « connecteurs » des réseaux sociaux.
- Composant cœur K
Un composant cœur K est un sous-graphe minimalement connecté dans lequel tous les sommets ont au moins un degré K. Ces composants correspondent à des groupes d’acteurs dans les réseaux sociaux.
- Excentricité d’un sommet
L’excentricité d’un sommet donne le plus long des plus courts chemins qui vont de ce sommet à tous les autres sommets du graphe.
Le langage Mathematica dispose de nombreuses commandes permettant d’analyser un graphe. Accédez à quelques explications et interprétations en cliquant sur l’image ci-dessus !