Rechercher des cliques

Sous-graphes complets et couverture par sommets


Les réseaux sociaux représentent des relations comme les contacts ou l’amitié entre individus, les communications dans un groupe, les transactions entre compagnies. Trouver les acteurs importants, découvrir les groupes ou les communautés soudés, identifier les similitudes sont autant d’exemples d’analyses qui peuvent être menées sur les réseaux sociaux.



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. La clique d’un graphe est l’ensemble maximal de sommets formant un sous-graphe complet (i. e. dont les sommets sont tous reliés deux à deux par une arête). La couverture minimale par sommets donne l’ensemble minimum de sommets couvrant toutes les arêtes de la clique. Cet ensemble correspond très probablement, dans le cas d’un réseau social, aux pontes du réseau. Le langage Mathematica dispose de nombreuses commandes permettant d’analyser un graphe. Accédez à quelques explications et interprétations en cliquant sur les images !


Albums les plus récents