Les réseaux sociaux en graphes

• Comprendre la notion de graphe et ses composants (sommets, arêtes).
• Modéliser un réseau social simple sous forme de graphe.
• Identifier des propriétés de base d'un graphe (degré, chemin, composante connexe) et les interpréter dans le contexte d'un réseau social.

Qu'est-ce qu'un graphe ? Du jeu aux réseaux

En mathématiques et en informatique, un graphe est un modèle abstrait utilisé pour représenter des relations entre des objets. Il est composé de deux éléments principaux : les sommets (ou nœuds) et les arêtes. Les sommets représentent les objets (par exemple, des personnes, des villes, des pages web). Les arêtes représentent les liens ou relations entre ces objets (par exemple, une amitié, une route, un lien hypertexte). Un graphe peut être représenté visuellement par des points (les sommets) reliés par des traits (les arêtes). Cette notion n'est pas nouvelle : le célèbre problème des sept ponts de Königsberg, étudié par Euler au 18ème siècle, est un des premiers problèmes de théorie des graphes. Dans notre vie numérique, lorsque tu crées un compte sur un réseau social, tu deviens un sommet. Chaque fois que tu deviens 'ami' avec quelqu'un sur Facebook, que tu suis une personne sur Instagram ou que tu te connectes à un collègue sur LinkedIn, tu crées une arête entre ton sommet et le sien. Ainsi, le réseau social tout entier n'est qu'un immense graphe, parfois composé de milliards de sommets et de dizaines de milliards d'arêtes.

Vocabulaire et propriétés d'un graphe de réseau social

Pour analyser un réseau social modélisé en graphe, il faut maîtriser un vocabulaire spécifique. Le degré d'un sommet correspond au nombre d'arêtes qui y sont attachées. Dans un réseau social, c'est le nombre d'amis ou de followers d'une personne. Un individu avec un degré très élevé est un 'influenceur' ou un 'hub'. Un chemin est une suite d'arêtes permettant de relier deux sommets. La longueur d'un chemin est le nombre d'arêtes empruntées. Sur Facebook, la distance entre deux personnes (le nombre minimum d'étapes d'amitié pour les relier) est la longueur du plus court chemin. C'est le fameux 'six degrés de séparation'. Une composante connexe est un ensemble de sommets tous reliés entre eux par au moins un chemin. Dans un réseau social privé comme celui d'une classe, il n'y a souvent qu'une seule grande composante connexe (tout le monde est relié, directement ou indirectement). Sur un réseau public comme Twitter, il peut y avoir plusieurs composantes si des groupes d'utilisateurs ne suivent personne en dehors de leur groupe. Enfin, on distingue les graphes orientés des graphes non orientés. Sur Facebook, l'amitié est mutuelle (non orientée) : si A est ami avec B, alors B est ami avec A. Sur Instagram ou Twitter, le 'suivi' est orienté : A peut suivre B sans que B ne suive A en retour. Cette orientation change radicalement l'analyse du réseau.

Applications pratiques : modélisation et analyse

Prenons un exemple concret avec un mini-réseau social de classe. Imaginons 5 élèves : Léa, Sam, Inès, Tom, Lou. Léa est amie avec Sam et Inès. Sam est ami avec Léa et Tom. Inès est amie avec Léa. Tom est ami avec Sam. Lou n'est ami avec personne pour l'instant. Nous pouvons modéliser cela par un graphe non orienté à 5 sommets. Le degré de Léa est 2 (elle a 2 amis), celui de Sam est 2, celui d'Inès est 1, celui de Tom est 1 et celui de Lou est 0. Le plus court chemin entre Inès et Tom est : Inès -> Léa -> Sam -> Tom (longueur 3). La composante connexe principale contient Léa, Sam, Inès et Tom. Lou forme une composante connexe à part, réduite à un seul sommet. Maintenant, appliquons cela à un algorithme réel : la suggestion d'amis. Comment Facebook propose-t-il 'Les personnes que vous pouvez connaître' ? L'algorithme analyse le graphe. Une méthode simple est de proposer les 'amis de mes amis' qui ne sont pas encore mes amis. Dans notre exemple, Facebook pourrait suggérer Tom à Inès (car Tom est l'ami de Sam, qui est l'ami d'Inès). Cette analyse des graphes est aussi cruciale pour détecter des communautés (groupes d'utilisateurs très connectés entre eux), pour étudier la propagation des informations (ou des rumeurs) et pour optimiser le ciblage publicitaire.