Cours - Graphes et réseaux sociaux : définitions, propriétés, modèles¶
Supports complémentaires :
[Diapositives du cours : 2 par page] [Diapositives du cours : 1 par page]
Motivation : pourquoi étudier les graphes ?¶
De nombreux systèmes réels peuvent être modélisés comme des graphes : réseaux sociaux en ligne (Facebook, LinkedIn, Twitter/X), graphe du Web, réseaux biologiques (gènes, protéines, neurones), réseaux de transport, réseaux électriques, réseaux de co-authorship scientifique. Dans tous ces cas, les entités (personnes, pages, gènes, villes…) sont connectées par des relations, et c’est précisément la structure de ces connexions qui porte l’information utile.
L’étude scientifique des réseaux sociaux remonte aux années 1950, avec les travaux des anthropologues J.A. Barnes et M. Gluckman, puis du sociologue M. Granovetter [G73]. Depuis l’avènement du Web 2.0, la disponibilité de graphes de plusieurs milliards de nœuds a rendu le passage à l’échelle indispensable, ce qui motive l’ensemble de ce chapitre.
Le phénomène du petit monde¶
L’expérience de Milgram [M67] (1967) constitue le point de départ expérimental du domaine. L’objectif était de mesurer la distance sociale entre individus dans un vaste réseau : des lettres devaient transiter d’Omaha (Nebraska) à Boston (Massachusetts) en passant de main en main. Sur 296 lettres envoyées, 64 arrivèrent à destination en empruntant en moyenne 5,2 intermédiaires, donnant naissance à l’expression « six degrés de séparation ».
Fig. 58 Carte des États-Unis avec les états de départ et d’arrivée des lettres de Milgram¶
Cette expérience, reproduite depuis sur courriel et en 2011 sur Facebook (où la distance moyenne est de 4,74), met en évidence deux propriétés fondamentales des réseaux sociaux réels :
des chemins courts globaux malgré la grande taille du réseau (d’où le nom « petit monde » ou small-world) ;
une navigabilité locale : les individus trouvent ces chemins courts sans connaissance globale du réseau, en exploitant uniquement leur réseau de proximité.
Il faut cependant interpréter ces résultats avec précaution : les lettres non arrivées (232 sur 296) ne signifient pas qu’aucun chemin n’existait, et les chemins observés ne sont pas nécessairement les plus courts possibles.
Le modèle de Kleinberg [K00] propose une formalisation de l’expérience de Milgram. La connectivité est modélisée par une grille régulière de taille \(n \times n\) (contacts géographiquement proche) à laquelle on ajoute aléatoirement des liens longue portée connus seulement par les nœuds qu’ils connectent (contacts éloignés). Si \(d\) est la distance entre deux nœuds \(u, v\) sur la grille, la probabilité d’avoir un lien direct entre ces nœuds est proportionnelle à \(\frac{1}{d^r}\), \(r \ge 0\) étant le paramètre de cette loi. Pour acheminer un message d’un nœud source \(s\) vers un nœud cible \(t\) on considère que le dépositaire du message à un moment donné connaît seulement la structure de la grille et la localisation de la cible sur la grille. Il choisit donc de transmettre le message au nœud (auquel il est connecté) qui est le plus proche de la cible en termes de distance \(d\) sur la grille.
Kleinberg [K00] démontre que l’espérance du nombre total de liens traversés a une borne supérieure proportionnelle à \((\log n)^2\) (qui augmente donc avec le carré du logarithme de \(n\)) pour \(r = 2\), ce qui est un minimum sur le domaine de variation de \(r\). Pour \(r = 0\), qui implique une distribution uniforme par rapport à la distance, l’espérance du nombre total de liens traversés a une borne inférieure proportionnelle à \(n^{2/3}\) (qui augmente avec une puissance de \(n\)) ; les liens longue distance sont souvent trop longs et ne peuvent que rarement servir à écourter le chemin. Aussi, pour \(r > 2\) les liens longue distance sont souvent trop courts et ne font pas gagner assez de temps par rapport à un parcours sur la grille.
Ce phénomène de « petit monde » a été aussi mis en évidence expérimentalement dans des réseaux variés, qu’il s’agisse des neurones de Caenorhabditis elegans ou de la distribution d’électricité aux USA.
Éléments de théorie des graphes¶
Définitions fondamentales¶
Un graphe est défini par un couple \(G = (V, E)\) où :
\(V\) (vertices) est un ensemble fini de sommets (ou nœuds), de cardinal \(n = |V|\) ;
\(E\) (edges) est un ensemble fini d”arêtes (ou liens), de cardinal \(m = |E|\).
Un graphe est orienté si les paires \((v_i, v_j) \in E\) sont ordonnées (on parle alors d”arcs, notés \(v_i \rightarrow v_j\)) ; non orienté sinon (arête \(v_i - v_j\) équivalente à \(v_j - v_i\)). Un graphe est valué (ou pondéré) si chaque arête porte un poids numérique (distance, coût, force du lien, etc.).
Terminologie essentielle :
ordre du graphe : son nombre de sommets \(n\) ;
graphe simple : sans boucle (arête reliant un sommet à lui-même) et sans arêtes multiples entre deux mêmes sommets ;
graphe complet : une arête existe pour toute paire de sommets ; \(m = \frac{n(n-1)}{2}\) pour un graphe complet non orienté ;
sous-graphe : obtenu en supprimant certains sommets (et toutes les arêtes incidentes) ; graphe partiel : obtenu en supprimant seulement des arêtes ;
densité : rapport \(\delta = \frac{m}{n(n-1)/2}\) entre le nombre d’arêtes réelles et le nombre maximal possible (pour un graphe non orienté) ; les réseaux réels sont en général très peu denses (\(\delta \ll 1\)).
Degré¶
Le degré d’un sommet \(v\) est le nombre d’arêtes qui lui sont incidentes. Dans un graphe orienté, on distingue le degré entrant \(k^{in}(v)\) (arcs pointant vers \(v\)) et le degré sortant \(k^{out}(v)\) (arcs partant de \(v\)).
Fig. 59 Degré entrant et degré sortant. Si les liens n’étaient pas orientés, le degré de \(i\) serait de 5.¶
Le degré moyen d’un graphe non orienté vaut \(\langle k \rangle = \frac{2m}{n}\). La somme des degrés est toujours paire (lemme des poignées de mains).
Chemins et distances¶
Un chemin est une suite de sommets \(v_1, v_2, \ldots, v_k\) telle qu’il existe une arête entre chaque paire de sommets consécutifs. Sa longueur est le nombre d’arêtes traversées (ou, dans un graphe valué, la somme de leurs poids).
Le plus court chemin (ou géodésique) entre deux sommets \(u\) et \(v\) est le chemin de longueur minimale. La distance \(d(u,v)\) est cette longueur minimale. Dans un graphe non valué, l’algorithme BFS (Breadth-First Search) calcule les distances depuis une source en \(O(n + m)\). Dans un graphe valué à poids positifs, l’algorithme de Dijkstra les calcule en \(O((n + m) \log n)\).
Fig. 60 Entre \(i\) et \(l\) il y a trois plus courts chemins, de longueur 3 : i-j-k-l, i-n-m-l et i-n-k-l.¶
Propriétés dérivées des distances :
excentricité du sommet \(v\) : \(\epsilon(v) = \max_{u \in V} d(v, u)\) ;
diamètre du graphe : \(D = \max_{v} \epsilon(v)\) est la plus grande distance entre deux nœuds quelconques ;
rayon du graphe : \(r = \min_{v} \epsilon(v)\) ;
centre du graphe : ensemble des nœuds d’excentricité minimale (nœuds les « moins éloignés » de tous les autres) ;
longueur moyenne des plus courts chemins : \(\ell = \frac{1}{n(n-1)} \sum_{u \neq v} d(u,v)\).
Le diamètre est coûteux à calculer exactement (\(O(nm)\)) ; des estimations en \(O(m)\) suffisent en pratique.
Connexité¶
Un graphe non orienté est connexe s’il existe un chemin entre toute paire de sommets. Dans un graphe orienté, on distingue la connexité forte (chemin orienté dans les deux sens) et la connexité faible (connexité en ignorant les orientations).
Une composante connexe est un sous-ensemble maximal de sommets connexes entre eux. Les réseaux réels présentent souvent :
une composante connexe géante (CGC) regroupant une fraction macroscopique de tous les nœuds ;
de nombreuses petites composantes isolées.
La taille relative de la CGC est un indicateur de robustesse du réseau.
Représentations informatiques¶
Deux représentations classiques coexistent pour les graphes :
Matrice d’adjacence \(A\) de taille \(n \times n\), avec \(A_{ij} = 1\) s’il existe une arête \((i,j)\), 0 sinon (ou le poids pour un graphe valué). Avantage : tester l’adjacence en \(O(1)\). Inconvénient : espace occupé \(O(n^2)\), prohibitif pour de grands graphes creux, même si des bibliothèques récentes permettent de réduire la place occupée par une matrice creuse.
Listes d’adjacence : pour chaque sommet, la liste de ses voisins. Espace \(O(n + m)\), adapté aux graphes creux. Parcourir tous les voisins d’un nœud est en \(O(k)\) (\(k\) étant le degré du nœud).
Fig. 61 Exemple de graphe¶
Fig. 62 Matrice d’adjacence associée au graphe¶
On définit aussi la matrice des degrés \(D\) (diagonale, \(D_{ii} = k_i\)) et la matrice laplacienne \(L = D - A\), utilisée notamment dans les algorithmes de détection de communautés (voir le cours suivant).
Parcours de graphe : BFS et DFS¶
Fig. 63 Graphe illustrant les deux algorithmes de parcours¶
Parcours en largeur (BFS, ou Breadth-First Search) : à partir d’une source S, on visite d’abord tous les voisins directs, puis leurs voisins, etc. Implémenté avec une file. Sur le graphe ci-dessus avec S = A : ordre de visite A, B, C, E, D, F, G. Usage principal : plus courts chemins (en nombre de sauts), calcul de distances, détection de composantes connexes.
Parcours en profondeur (DFS, ou Depth-First Search) : à partir de S, on explore récursivement chaque voisin jusqu’au bout avant de revenir. Implémenté avec une pile (ou récursion). Sur le graphe ci-dessus avec S = A : ordre de visite A, B, D, F, E, C, G. Usage principal : détection de cycles, tri topologique, calcul de composantes fortement connexes (algorithme de Tarjan).
Propriétés caractéristiques des graphes¶
Distribution de degrés¶
La distribution de degrés \(P(k)\) est la fraction de sommets de degré \(k\). Elle constitue l’une des empreintes les plus discriminantes d’un réseau. Attention, parfois une confusion est faite avec la distribution cumulative des degrés, désignant la fraction de sommets qui ont un degré au moins égal à \(k\).
Fig. 64 Distribution gaussienne (graphe aléatoire, à gauche) vs loi de puissance (réseau réel, à droite)¶
Dans les graphes aléatoires uniformes (modèle de Erdős-Rényi), la distribution des degrés suit une loi binomiale. La plupart des nœuds ont un degré proche de la moyenne.
Dans de nombreux réseaux réels (pages Web, citations scientifiques, réseaux sociaux), la distribution suit une loi de puissance : \(P(k) \propto k^{-\gamma}\), avec \(\gamma\) typiquement entre 2 et 3. Ces réseaux sont dits sans échelle (scale-free) : ils sont dominés par quelques nœuds très connectés appelés hubs, alors que la grande majorité des nœuds ont un faible degré. Cette hétérogénéité a des conséquences directes sur la robustesse (résistance aux pannes aléatoires mais vulnérabilité aux attaques ciblées sur les hubs) et sur la vitesse de diffusion d’information ou de virus.
Coefficient de clustering¶
Le coefficient de clustering mesure dans quelle mesure les voisins d’un nœud sont également connectés entre eux, c’est à dire la propension à former des triangles (« mes amis sont amis entre eux »).
Version locale (Watts-Strogatz [WS98]) pour un sommet \(i\) de degré \(k_i\) :
où \(N(i)\) est l’ensemble des voisins de \(i\). C’est le rapport entre le nombre d’arêtes effectivement présentes dans le voisinage et le nombre maximal possible (si ce voisinage formait une clique).
Version globale (transitivité) :
Un triplet connecté est tout ensemble de trois nœuds dont deux au moins sont reliés ; un triangle est un triplet fermé (les trois paires sont reliées).
Les réseaux réels ont un coefficient de clustering bien supérieur à celui d’un graphe aléatoire uniforme de même taille et densité.
Centralités¶
Les mesures de centralité quantifient l’importance ou l’influence d’un nœud dans le graphe. Plusieurs définitions existent, chacune capturant un aspect différent.
Centralité de degré : simplement le degré \(k(v)\), mesure la connectivité locale. Facile à calculer mais ignore la structure globale.
Centralité d’intermédiarité (betweenness centrality) :
où \(\sigma_{st}\) est le nombre total de plus courts chemins entre \(s\) et \(t\), et \(\sigma_{st}(v)\) le nombre de ces chemins passant par \(v\). Mesure l’influence de \(v\) sur la circulation de l’information dans le réseau. Un nœud de haute intermédiarité est un pont entre communautés ; sa suppression peut fragmenter le réseau. Complexité de calcul : \(O(nm)\) avec l’algorithme de Brandes.
Centralité de proximité (closeness centrality) :
(ou sa version normalisée \(\frac{n-1}{\sum_{u} d(u,v)}\)). Inverse de la somme des distances à tous les autres sommets, mesure à quel point un nœud peut atteindre rapidement tous les autres. Utile pour identifier des nœuds stratégiques dans la diffusion d’information ou les réseaux logistiques.
PageRank : mesure issue de l’algorithme de classement de Google. Un nœud a un PageRank élevé s’il est pointé par de nombreux nœuds ayant eux-mêmes un PageRank élevé. Formellement, en notant \(\mathcal{B}(v)\) les prédécesseurs de \(v\) :
avec \(d \approx 0{,}85\) (probabilité de suivre un lien plutôt que de se « téléporter » aléatoirement). S’applique aux graphes orientés ; contrairement à la centralité de degré entrant, il tient compte de la « qualité » des liens entrants. Utilisé en fouille du Web, recommandation et détection de nœuds influents dans des réseaux sociaux.
En pratique
La centralité d’intermédiarité est la plus riche d’interprétations structurelles (ponts, courtiers d’information). Le PageRank est important dans les graphes orientés où la notion d’autorité ou de prestige est pertinente. La centralité de proximité est utile pour les problèmes de localisation ou de diffusion.
Modèles de génération de graphes¶
Ces modèles servent deux objectifs : comprendre les mécanismes qui engendrent les propriétés observées et générer des graphes de référence pour l’analyse.
Modèle de Gilbert \(G(n,p)\)¶
Appelé parfois aussi Erdős–Rényi (confusion possible avec un autre modèle), c’est un graphe à \(n\) sommets, entre deux sommets l’arête existe avec probabilité \(p\) indépendamment des autres. On observe alors en général une composante connexe géante, un diamètre proche de \(\log(n)\), un clustering faible, une distribution de degrés suivant une loi binomiale, l’absence de structure communautaire. Ce modèle sert surtout de base de comparaison.
Modèle de Watts-Strogatz¶
On part d’un réseau en anneau régulier (chaque nœud est connecté à ses \(k\) voisins les plus proches), puis on « reconnecte » chaque arête avec une probabilité \(p\). Pour \(p\) intermédiaire, le graphe combine fort clustering et faible distance moyenne, étant ainsi un modèle de petit monde.
Modèle de Barabási-Albert (attachement préférentiel)¶
On construit le graphe de façon incrémentale : chaque nouveau nœud se connecte à \(m\) nœuds existants avec une probabilité proportionnelle à leur degré courant \(p_i = \frac{k_i}{\sum_j k_j}\). Cette règle de génération fait que les nœuds qui ont déjà des connexions ont tendance à en recevoir toujours davantage (rich-get-richer), ce qui crée des « hubs » et une distribution de degrés qui est asymptotiquement une loi de puissance \(P(k) \propto k^{-3}\) [AB02]. Ce modèle capture la croissance de nombreux réseaux réels (Web, citations, réseaux de collaborations).
Modèle configurationnel¶
On fixe a priori la séquence de degrés souhaitée, puis on crée les liens aléatoirement en respectant ces degrés. Ce modèle est utile pour isoler l’effet de la distribution de degrés de tout autre biais structurel.
Propriétés typiques des réseaux réels¶
En comparant des réseaux réels à des graphes aléatoires de même taille et densité suivant le modèle \(G(n,p)\) de Gilbert on observe systématiquement :
Propriété |
Graphe aléatoire \(G(n,p)\) |
Réseau réel |
|---|---|---|
Densité |
Contrôlée par \(p\) |
Très faible |
Distribution de degrés |
Loi binomiale |
Loi de puissance |
Coefficient de clustering |
Faible (\(\approx p\)) |
Élevé |
Longueur moyenne des chemins |
\(O(\log n)\) |
\(O(\log n)\) |
Composante connexe géante |
Oui (pour \(p >\) seuil) |
Oui, très grande |
Structure communautaire |
Non |
Oui |
..La combinaison fort clustering et faible distance moyenne correspond au modèle petit monde de Watts-Strogatz [WS98]. La combinaison loi de puissance et petit monde correspond aux réseaux sans échelle de Barabási-Albert [AB02].
Mesure et biais d’observation¶
Avant toute analyse, il faut s’interroger sur la qualité des données collectées. Les graphes étudiés sont souvent le résultat d’une mesure partielle ou biaisée du système réel.
Questions à se poser systématiquement :
Quelle proportion du système a été mesurée ? Sur quelle durée ?
Quelles contraintes techniques ont pesé sur la collecte ?
La mesure peut-elle être reproduite ? Est-elle indépendante de l’observateur ?
Exemple : cartographie d’Internet par traceroute. Cet outil enregistre les
chemins empruntés par des paquets du protocole IP entre une source et une destination.
Il y a deux biais structurels importants : (1) les nœuds de degré 1 ne sont accessibles que
s’ils sont source ou destination ; (2) l’équilibrage de charge peut faire
emprunter des routes différentes à des paquets successifs. Ces effets modifient
la distribution de degrés observée par rapport à la distribution réelle.
Fig. 65 Distribution de degrés observée (biaisée) vs distribution réelle¶
Une mesure biaisée peut conduire à des conclusions erronées sur les propriétés structurelles du réseau. La validité des analyses dépend directement de la qualité de la capture.
Difficultés algorithmiques¶
Les graphes réels sont souvent d’une taille qui rend les calculs exacts impraticables. Quelques ordres de grandeur importants (avec \(n\) sommets, \(m\) arêtes) :
Parcours (BFS/DFS) : \(O(n + m)\), passage à l’échelle raisonnable ;
Plus courts chemins depuis une source (Dijkstra) : \(O((n+m)\log n)\) ;
Plus courts chemins entre toutes les paires de nœuds (Floyd-Warshall) : \(O(n^3)\), impraticable au-delà de quelques milliers de nœuds ;
Diamètre exact : \(O(nm)\), on emploie souvent des estimations en \(O(m)\) ;
Comptage de triangles (naïf) : \(O(n^3)\) ; des algorithmes exploitant la loi de puissance ramènent cela à \(O(m \cdot n^{1/a})\) pour une distribution des degrés \(P(k) \propto k^{-a}\) ;
Centralité d’intermédiarité exacte : \(O(nm)\) (algorithme de Brandes) ;
Détection de communautés : NP-difficile dans sa formulation exacte, traité en pratique par des heuristiques (voir le cours suivant).
Ces contraintes justifient l’utilisation de frameworks de calcul distribué (Spark avec GraphFrames, Pregel, etc.) et d’algorithmes approximatifs.
Outils et frameworks¶
GraphFrames (graphframes.io) est la bibliothèque que nous utilisons en TP. Elle étend Spark avec des algorithmes de graphes parallélisés, en proposant des API Python, Scala et Java. Elle hérite des avantages de Spark (tolérance aux pannes, intégration avec les DataFrames, déploiement sur cluster).
Pregel [MABDHLC10], développé par Google, repose sur un modèle de calcul par passage de messages entre nœuds (approche Bulk Synchronous Parallel, BSP). Plusieurs implémentations open source existent (Giraph, etc.).
NetworkX est une bibliothèque Python pour graphes de taille modérée (tout en mémoire), très utile pour la visualisation et le prototypage.
Neo4j est une base de données orientée graphes, bien adaptée aux requêtes de type « traversée de graphe » et aux applications transactionnelles.
Gephi (gephi.org) est un logiciel de visualisation et d’analyse de graphes (PageRank, modularité, chemins, etc.), employé en TP.
Références¶
Albert, R. and Barabási, A.-L. Statistical mechanics of complex networks. Reviews of Modern Physics. 2002. 74: 47–97.
Granovetter, M. S. The Strength of Weak Ties. American Journal of Sociology, Volume 78, Issue 6 (May, 1973), 1360–1380.
Travers, J. and Milgram, S. An experimental study of the small world problem. Sociometry, Vol. 32, No. 4. (Dec., 1969), pp. 425–443.
Malewicz, G. et al. Pregel: A System for Large-Scale Graph Processing. SIGMOD 2010.
Leskovec, J., Rajaraman, A. and Ullman, J. D. Mining of Massive Datasets. Cambridge University Press, 2011. http://www.mmds.org