Théorie des graphes — concepts de base
Partie 1 — Prélude théorique à une analyse des réseaux Twitter des candidats à la présidentielle
Dans le cadre de mon mémoire de recherche, je vais bientôt représenter des réseaux de communautés et visualiser des “bulles informationnelles”. Afin de ne pas me noyer dans les noeuds, les liens et les formules mathématiques, je profite du contexte politique pour m’entraîner. Je commence donc avec une explication la plus compréhensible possible des réseaux !
Petite note: je suis débutant :)
(si vous voyez des erreurs ou des obscurités, merci de les reporter dans les commentaires)
Quelques bases, rapidement
Réseau dirigé et non-dirigé
Si je vous dis “réseau”, il y a peu de chances que vous pensiez à autre chose qu’à des entités qui sont connectées d’une certaine manière entre-elles. Il existe une multitude de types de réseaux et à propos de Twitter par exemple, on parle de… “réseau social” car tenez-vous bien, les entités sont des personnes (avec plein d’exceptions, j’en conviens).
Twitter est un réseau dirigé (directed), ce qui veut dire qu’une personne (“nodes” ou “vertex” est le terme scientifique anglais pour désigner l’entité décrite ci-dessus) peut être connectée à une autre (le lien est appelé “edge” ou “arc”) sans que celle-ci soit connectée en retour. Facebook, à l’inverse, est un réseau non-dirigé (undirected) puisque si vous êtes ami.e avec une personne, celle-ci est également amie avec vous.
Avant de continuer, ayez-bien en tête que nous parlons ici de représentation du réel. Les visualisations (comme mes dessins ou celles obtenues avec Gephi) sont donc remplies de biais. Leur validité scientifique est même discutable.
Prenons vos cinq meilleures amies (faisons simple)
Ici, on se place dans un réseau non-dirigé, comme Facebook.
Première question : vos meilleures amies se connaissent-elles toutes ?
Si oui, le réseau est une “clique” (on dit pareil en anglais).
Il y a toutefois une plus grande probabilité que toutes vos meilleures amies ne se connaissent pas toutes entre elles. Imaginons que vous avez deux amies du travail (qui elles, se connaissent), une pote de la Fac et une autre que vous avez rencontrée sur un Forum en ligne.
Trois grands concepts
1. La “force” des relations
En fonction du nombre de fois que vous rencontrez vos amies par mois, on va attribuer une valeur à la “force” (weight) du lien.
On pourrait tout à fait prendre d’autres critères, comme la distance géographique ou encore votre sentiment d’intimité avec ces personnes.
Dans notre exemple, disons que vous avez rencontré vos deux amies du travail 5 fois (toujours en même temps, d’où le lien entre elles sur le schéma), votre pote de la Fac 1 fois et votre amie du Forum 10 fois.
Ici, nous considérons que plus vous voyez une amie, plus vous êtes proche d’elle.
1bis. Gravité
Dans l’exemple précédent, la représentation de la force est linéaire. 10cm = 1 rencontre, 5cm = 5 rencontres, etc.
Des algorithmes de visualisation utilisant ce paramètre de “force” vont raisonner en termes de “gravité”. Dans ce cas précis, ils ne calculeraient pas la représentation de la proximité par une valeur fixe (1, 5, 10) mais par une valeur relative (qui provient d’un calcul prenant en compte toutes les valeurs fixes de tous les liens).
La visualisation est obtenue de la manière suivante : chaque lien entraîne une attraction entre les deux noeuds liés et chaque noeud entraîne une répulsion proportionnelle au nombre de noeuds du réseau.
Petit défi :
Prenez un réseau de trois noeuds, A, B et C. La force du lien entre A et B est égale à 1. Celle entre B et C = 5 et celle entre C et A = 2. Prenez un crayon et un papier et essayer de respecter ces valeurs avec 1 = 1cm. Tendu.
En fait, lorsqu’on lance l’algorithme, il passe en revue les valeurs de tous les noeuds et liens plusieurs fois, itère et adapte sa visualisation, qui se stabilise naturellement (ce type d’algorithme est stochastique et non pas déterministe ; la visualisation finale n’est pas toujours la même car les itérations ne se font pas toujours dans le même ordre).
On a donc une visualisation qui s’est adaptée. Dans notre défi, si on mesure les distances (ça n’a pas de sens) qui relient A à B, B à C et C à A, on trouverait seulement une représentation des ordres de grandeur des forces.
2. Communautés et homophilie
Gardons ce réseau de cinq amies et rappelez-vous que vos deux amies du travail se connaissent mutuellement. On peut ainsi considérer que vous trois formez une communauté.
Admettons que vous trois êtes militantes pour l’égalité des sexes. Il se trouve que le Forum sur lequel vous avez rencontrée votre autre amie est un lieu de débat autour de l’égalité des salaires.
Même si ces trois amies ne se connaissent pas, on peut dire que vous êtes homophile (point définition : ici, “attirance (amicale) pour les personnes similaires à soi-même”. Source) du fait de l’homogénéité de votre réseau de meilleures amies. On parle aussi d’assortativity en anglais.
3. Centralité
Un peu plus dur.
On peut définir et représenter la centralité d’un noeud selon plusieurs critères. Une définition large et simplifiée de la centralité sous forme de question pourrait être : dans le réseau, combien le noeud étudié connecte-t-il d’autres noeuds ?
Nombre d’amies (ou théoriquement : le degré du noeud)
Dans notre exemple, on s’intéresse d’abord au nombre d’amis que vous avez et qu’ont vos amies. Après un petit calcul, voici le résultat : vous avez 4 amies (degré = 4), vos deux amies du travail ont toutes les deux 2 amies et votre amie de la Fac et du Forum ont 1 amie (vous) chacune.
Certes, notre réseau de cinq personnes est un peu trop basique, mais je vais essayer de vous expliquer la notion de centralité intermédiaire (betweenness centrality).
Centralité intermédiaire
Nous observons que chaque personne est directement ou indirectement connectée à quatre autres personnes.
Maintenant (et on arrive au coeur du concept de centralité), imaginez que chacune de vos amies veuille rencontrer respectivement vos autres amies, sans vous. Vos potes du travail se connaissent et ont déjà échangé leur numéro, elles n’ont pas besoin de passer par vous.
Par contre, si elles veulent rencontrer votre amie de la Fac et votre amie du Forum, elles sont obligées de passer par vous.
Aussi, elles veulent être efficaces et vont choisir le “chemin” le plus court. Une de vos amies du travail ne va pas s’amuser à contacter l’autre amie du travail, qui vous contactera, qui vous connectera à votre amie de la Fac.
Avant que toutes vos amies se contactent entre-elles, le réseau ressemble à ceci.
On observe que vous avez une position centrale car vos quatre amies doivent passer par vous si elles veulent contacter vos autres amies (à une exception près). Vous avez un ratio élevé de centralité intermédiaire.
Pour mettre en valeur cette centralité, on peut aussi considérer que toutes les personnes du réseau veulent contacter les autres personnes et qu’à chaque fois qu’une personne contacte ou est contactée (pour avoir un numéro ou pour appeler), on incrémente la valeur de centralité de ces deux personnes (oula, compliqué).
Ratio de centralité
Enfin, considérons que plus le ratio de centralité est élevé, plus la taille du carré est grande.
4. Et après tout ça ?
Désolé de vous l’annoncer, mais vous avez perdu en betweenness centrality (oui, cette phrase sonne mieux en anglais) :/
La communauté (à trois) qui vous (r)assemble avec vos amies du boulot existe toujours, mais est moins évidente.
Un mois plus tard, le réseau a une tout autre tête car vos potes se sont vues (et pas toujours avec vous :p). La clique !
Mais pas d’inquiétudes, vous avez pris votre revanche :)
Fin et suite
Quelques liens
Wikipédia est bon sur le sujet. Je vous conseille d’aller jeter un oeil aux articles suivants :
- La théorie des graphes
- La structure de communautés (en anglais)
- Homophily, ou assortativity (en anglais)
- Centralité
- Centralité intermédiaire (en anglais)
Et aussi :
- Étude du petit monde (le concept des “six degrés de séparation”)
- Analyse des réseaux sociaux
- Tracé de graphes
- Une explication du concept à la source de l’algorithme de Google Search, le PageRank
Suite
J’ai encore quelques données à passer à la moulinette et je vous présente mes graphs créés avec Gephi !
Prochaine étape : l’explication de visualisations de mes réseaux Twitter et Facebook (vous vous en foutez me direz vous, mais je connais tous les noeuds donc l’analyse est plus simple)
Je remercie particulièrement Telmo (mon collègue) pour ses explications et également Luca et Martin Grandjean pour leurs tutoriels.
Si vous avez ❤ cet article, recommandez et partagez-le :) Merci !
