.. _chap-coursFouilleGraphesReseauxSociaux: ################################################# Cours - Fouille de graphes et réseaux sociaux (1) ################################################# .. admonition:: Support complémentaires : Vous pouvez télécharger les `diapositives du cours `_ qui sont projetées durant la séance. .. admonition:: Note aux lecteurs⋅ices : La rédaction de ce cours est récente, vous pouvez me communiquer vos retours pour l'améliorer à `fournier@cnam.fr`. Introduction ============ Un réseau social est un ensemble d'individus qui interagissent. L'étude scientifique de ces groupes a débuté dans les années 50, avec les travaux des anthropologues J.A. Barnes, M. Gluckman suivis par le sociologue M. Granovetter [G73]_. Une des premières expériences est celle de S. Milgram [M67]_, un psychologue américain, appelée « l'expérience des six degrés de séparation » (1967). Elle vise à étudier les degrés qui séparent des individus, donc les interconnexions entre leurs réseaux sociaux. L'objectif de l'expérience : faire transiter une lettre depuis Omaha (Nebraska) jusqu'à Boston (Massachussetts). Plusieurs expériences ont été menées. Dans l'une de celles-ci, 296 lettres partent d'Omaha (remise entre les mains de volontaires), qui doivent les faire parvenir à une personne donnée, résidant à Boston. Chacune des personnes qui reçoit la lettre doit la remettre en mains propres à une personne de son choix, supposée permettre de rapprocher la lettre de l'objectif. .. figure:: figures/USAmod.png :width: 50 % :alt: Carte des USA avec les États de départ et d'arrivée des lettres de Milgram :align: center Carte des USA avec les États de départ et d'arrivée des lettres de Milgram Les résultats furent les suivants : 64 lettres sur 296 arrivèrent, et les chemins eurent en moyenne 5,2 intermédiaires, ce qui amena l'expression « six degrés de séparation ». Plusieurs observations ont été tirées de cette expérience, par Milgram lui-même ou d'autres depuis : - il existe des « chemins courts » entre des personnes lointaines (une lettre ne mis que 4 jours pour arriver). Ce phénomène, déjà postulé par F. Karinthy en 1929, s'appelle aussi « phénomène du petit monde » ; - les membres du réseau parviennent à trouver ces chemins sans connaissance exhaustive de l'organisation du réseau (qui est ici de taille très grande, avec 300 millions d'habitants aux USA) : leur connaissance essentiellement `locale` leur permet de trouver des chemins `globaux` ; - pour les lettres qui ne sont pas arrivées (232, tout de même), l'interruption de la chaîne ne veut pas nécessairement dire qu'il n'existait pas de chemin ; - les lettres arrivées nous permettent de connaître des chemins de longueur x, ce qui ne veut pas dire qu'il n'existait pas de chemin de longueur inférieure (mais seulement que la transmission ne l'a pas empruntée à ce moment-là). .. figure:: figures/sixdegrees.png :width: 50 % :alt: 5 intermédiaires en moyenne, soit 6 degrés de séparation. :align: center .. TODO : Le paradoxe : 10² amis / personne => en 3 sauts, on touche 1 million .. de gens. Oui mais, 99amis se connaissent entre eux => 200 personnes… Depuis 1967, cette expérience a été reproduite plusieurs fois, avec des conditions expérimentales différentes, avec des courriers électroniques notamment, mais aussi en 2011 par les chercheurs de Facebook. Les résultats sont sensiblement les mêmes, bien que la valeur moyenne de la longueur des chemins varie un peu (4,74 dans le cas de Facebook). Une partie importante de ces travaux de recherche a consisté à proposer des `modèles` pour formaliser et reproduire l'expérience de Milgram sur des graphes aléatoires. En particulier, cela a conduit à développer des outils mathématiques dérivant de la théorie des graphes pour pouvoir analyser les phénomènes observés. D. Watts, associé à S. Strogatz, puis J. Kleinberg ont proposé des modélisations, reposant sur l'existence de distances connues localement et d'autres globalement. Le modèle de Kleinberg [K00]_ présente une grille, régulière, supposée connue de tous (connaissance `globale`). Les liens sont orientés, la connaissance des uns et des autres n'est pas forcément mutuelle. On ajoute :math:`q` voisins quelconques à chaque sommet, pointant vers un nœud éloigné du réseau. Ces liens représentent les `connaissances locales` du nœud (il est le seul de son voisinage à connaître ces personnes éloignées). Ces liens sont distribués aléatoirement dans le réseau, en suivant une loi de probabilité proportionnelle à l'inverse de la distance entre les points (élevée à une puissance :math:`s` à paramétrer) : :math:`p_{(u,v)} \propto \frac{1}{d^s}`. On peut voir la grille comme une modélisation du réseau social géographiquement proche, les liens supplémentaires comme des relations éloignées. Un individu connaît quelques personnes loin de lui, et celles-ci ne sont pas connues des gens qui vivent dans la même ville que lui (exemple : sa famille éloignée, des anciens collègues). Les auteurs de l'expérience proposent de faire circuler les messages selon un `algorithme glouton `_, c'est-à-dire ici qu'il choisira toujours le voisin le plus proche de la cible (en fonction d'une distance sur la grille). .. figure:: figures/milgrammod-plot.png :width: 50 % :align: center :name: milgrammod-plot Courbe de l'approximation du (log du) « temps » de routage en fonction de s Le point surprenant de l'étude est l'effet de seuil observé sur la valeur de :math:`s` : avec une valeur de :math:`s=2`, l'acheminement du message requiert en moyenne :math:`log(n)` sauts. C'est la seule valeur pour laquelle cela se produit, avec des valeurs significativement supérieures dans les autres cas (:math:`n^{(2-s)/3}` pour :math:`0 \leq s \lt 2`, :math:`n^{(s-2)/(s-1)}` pour :math:`s>2`). Voir la :ref:`milgrammod-plot`. En fait, quand `s` est trop petit, la probabilité de pointer sur des liens distants est forte : l'algorithme « saute » souvent à longue distance, même quand il est proche de la destination, rallongeant la marche. Avec `s` grand, les liens aléatoires ne permettent pas de faire de « grand saut » vers la destination, le chemin reste long. .. _milgrammod2: .. figure:: figures/milgrammod2.png :width: 50 % :alt: Modèle "en grille" proposé par Kleinberg pour modéliser l'effet petit monde, avec des sauts possibles. :align: center Ce phénomène de « petit monde » a été généralisé ensuite à des réseaux de dimension :math:`d > 2`. Il a été aussi mis en évidence expérimentalement dans des réseaux variés, qu'il s'agisse des neurones de `C. elegans` ou de la distribution d'électricité aux USA. Des exemples de réseaux sociaux et de graphes d'interaction =========================================================== Depuis l'arrivée, au début des années 2000, de technologies ayant permis le Web 2.0 (participatif), les « réseaux sociaux en ligne » se sont multipliés. Il s'agit de l'informatisation de modélisations parfois existantes, qui a rendu visible (et grand public) la notion de « réseau social ». Les membres de ces plateformes peuvent interagir avec leur « réseau » : ajouter des amis (Facebook, LinkedIn), suivre des personnes (Twitter), créer des groupes. Les réseaux sociaux constituent des réseaux d'interaction particuliers, entre individus. Examinons quelques exemples célèbres de tels réseaux. Le nombre d'Erdős ----------------- .. _paulerdos: .. figure:: figures/paulerdos.jpg :width: 10 % :align: center :alt: Paul Erdős Paul Erdős fut un mathématicien hongrois (1913-1996) extrêmement prolifique, qui co-signa des articles avec plus de 500 collaborateurs directs. Pour lui rendre hommage, le graphe des chercheurs en mathématiques a été étudié et chaque membre peut évoquer son « nombre d'Erdős », qui évalue la distance à Erdős dans ce graphe de collaboration. Le nombre d'Erdős est donc défini comme suit : - 0 : Pál Erdős - 1 : ses collaborateurs - 2 : les collaborateurs de ses collaborateurs - etc. Voir l'Erdős Number project sur http://www.oakland.edu/enp/. En pratique : il suffit de récupérer une liste d'articles et de calculer les `plus courts chemins` entre chaque chercheur et Erdős. On pourrait bien sûr calculer en prenant un autre scientifique pour référence. Le Kevin Bacon Game ------------------- .. _kevinbacon: .. figure:: figures/kevinbacon.jpg :width: 10 % :align: center :alt: Kevin Bacon Kevin Bacon (1958--) est acteur américain et le Kevin Bacon Game (ou « Six Degrees of Kevin Bacon ») est une transposition du concept de nombre d'Erdős à l'univers d'Hollywood. En 1994, sur un forum d'Internet, des étudiants se sont demandés (alors que des bases de données n'existaient pas encore) dans combien de films il avait joué et le nombre de personnes avec lesquelles il avait joué. Rapidement, c'est devenu un jeu pour cinéphiles que d'essayer de relier des acteurs au hasard avec Kevin Bacon. Deux acteurs sont reliés s'ils ont joué dans un même film. Il existe maintenant une plateforme en ligne où l'on peut vérifier les résultats : http://oracleofbacon.org/. On peut également y calculer les distances entre acteurs (en dehors de Kevin Bacon) : - Distance entre Tom Cruise et Clint Eastwood ? 2 (un acteur commun entre Space Cowboys et Eyes Wide Shut) - Distance entre Mickey Mouse et Omar Sy ? 4 Il existe quelques acteurs qui ne peuvent pas être reliés à Kevin Bacon. .. _linkedin: Réseaux de connaissances professionnelles ----------------------------------------- .. figure:: figures/linkedin-network-map.jpg :width: 90 % :alt: Réseau social "égo-centré", obtenu avec l'outil InMap de la plateforme LinkedIn (non disponible à ce jour). :align: center Réseau professionnel égocentré Réseaux de communication ------------------------ Les communications entre individus requièrent des `réseaux de communication` (réseau téléphonique, Internet, etc.). On peut collecter et analyser les échanges par le biais de ces réseaux. Internet n'est pas constitué que du Web, d'autres protocoles y existent : mail (SMTP/POP/IMAP), réseaux `peer-to-peer` (BitTorrent, Gnutella, etc.). En 2011, Friggeri et Latapy ont par exemple observé `la diffusion d'un fichier de proche en proche dans un réseau P2P `_. Comme on le verra plus tard, étudier Internet pose un certain nombre de questions (`biais de mesure`), même si cela fournit souvent des données nombreuses et extrêmement riches. Le projet Senseable (http://senseable.mit.edu/realtimerome/) a collecté diverses informations sur le réseau téléphonique et présenté des analyses (type d'appelant, comportement de mobilité), durant la finale de la coupe du monde de football en 2006 : .. _senseable: .. figure:: figures/worldcup-phone.jpg :width: 50 % :alt: Observation de communications téléphoniques autour de la finale de la Coupe du Monde de football 2006 : un graphe dynamique. :align: center Encore d'autres réseaux ----------------------- D'autres réseaux présentent des caractéristiques communes et soulèvent des problématiques d'études similaires : - informatique : pages Web, routeurs, P2P, etc. - biologie : protéines, neurones cérébraux, etc. - sciences sociales : amitiés, collaboration, contacts sexuels, etc. - économie : échanges financiers - histoire : mariages - linguistique : synonymie, co-occurrence - transports : réseau aérien, électrique Éléments de théorie des graphes =============================== En vue de permettre l'étude des graphes et réseaux sociaux, quelques rapides rappels de définitions et terminologies issues de la théorie des graphes. Un graphe est défini par un couple :math:`G = (V,E)` tel que : - :math:`V` (pour l'anglais `vertices`) est un ensemble fini de sommets - :math:`E` (pour l'anglais `edges`) est un ensemble fini de arêtes Un graphe peut être orienté, ou non : - si oui, les couples :math:`(v_i, v_j) \in E` sont ordonnés, :math:`v_i` est le sommet initial, :math:`v_j` est le sommet terminal. on appelle alors le couple :math:`(v_i, v_j)` un `arc`, représenté graphiquement par :math:`v_i \rightarrow v_j`. - si non, les couples ne sont pas orientés et :math:`(v_i, v_j)` est équivalent à :math:`(v_j, v_i)`, et on l'appelle `arête`, représenté par :math:`v_i - v_j` Terminologie : - **l'ordre** d'un graphe, c'est son nombre de sommets (souvent désigné par :math:`n`) - une **boucle** est un arc/une arête reliant un sommet à lui-même - un graphe dépourvu de boucle est dit **élémentaire** - un graphe **simple** ne comporte pas de boucle et au plus une arête entre deux sommets - un graphe **partiel** est le graphe obtenu en supprimant certains arcs ou arêtes - un **sous-graphe** est le graphe obtenu en supprimant certains sommets et tous les arcs/arêtes incidents aux sommets supprimés. - un graphe est dit **complet** s'il comporte une arête :math:`(v_i, v_j)` pour toute paire de sommets :math:`(v_i, v_j) \in E^2`. - un sommet :math:`v_i` est dit **adjacent** à un autre s'il existe une arête entre eux (on parle alors de sommets **voisins**). - le **degré** d'un sommet est le nombre d'arêtes incidentes à ce sommet (il peut y avoir un degré entrant et un degré sortant, pour les graphes orientés) .. figure:: figures/inoutdegree.png :width: 50 % :alt: degré entrant, degré sortant. :align: center Degré entrant, degré sortant. Si les liens de ce graphe n'étaient pas orientés, le degré de i serait de 5. - le **plus court chemin entre deux nœuds** est la valeur qui minimise la somme des valuations des arêtes empruntées pour parcourir le chemin entre ces nœuds. Dans un graphe non valué, il s'agit simplement du plus petit nombre d'arêtes à emprunter pour passer d'un nœud à l'autre. L'algorithme de Djikstra permet de calculer le plus court chemin entre deux nœuds avec une complexité polynomiale (non détaillé ici, voir par exemple `l'article Wikipedia consacré `_). .. figure:: figures/shortestpaths.png :width: 50 % :alt: plus court chemin :align: center Entre les noeuds i et l, il y a **trois** plus courts chemins : i-j-k-l, i-n-m-l et i-n-k-l. Ils ont pour longueur 3. - le **diamètre d'un graphe** (ou excentricité maximale) est la valeur maximale des distances entre les nœuds. Pour l'obtenir, on calcule les plus courts chemins entre chaque paire de nœuds et on garde le maximum. L'excentricité minimale, ou rayon du graphe, est la plus petite distance à laquelle puisse se trouver un sommet de tous les autres. Étudier de tels réseaux ======================= L'objectif est de comprendre le comportement des entités qui interagissent dans le système étudié, les lois qui les gouvernent. On cherche donc : - quelle est la structure des graphes ? - quelle est l'évolution de cette structure ? - quels sont les phénomènes reposant sur l'existence de ce réseau ? Les applications sont multiples. En informatique/télécommunications, comme la conception et la mise en place de réseaux est un enjeu crucial, on étudie les réseaux existants en vue de les améliorer (en amendant les protocoles existants ou en élaborant de nouveaux), que ce soit pour des questions de performances ou de sécurité. En sciences humaines, l'étude de réseaux d'interaction permet de comprendre la diffusion d'innovations (économie), de rumeurs (sociologie). En médecine, les réseaux sont fondamentaux pour comprendre les interactions entre protéines mais aussi la propagation de virus au sein des populations (et les effets des campagnes de vaccinations, par exemple). On propose dans ce cours une méthode d'étude générale, qui est ensuite affinée par les praticiens des différentes disciplines en fonctions de leurs besoins. Les outils sont souvent les mêmes : - Théorie des graphes - Analyse statistique - Modélisation probabiliste On procède parfois à de la simulation sur des données synthétiques que l'on compare à des données réelles. Les problématiques rencontrées dans l'étude des réseaux sociaux peuvent être classées en quatre catégories : Mesure, Modélisation, Analyse et Algorithmique (il faudra souvent faire des allers-retours entre ces domaines, par exemple en améliorant le modèle après des analyses préliminaires peu satisfaisantes, voir refaire une expérience de captation de données). Mesure ====== La mesure, ou métrologie, désigne ici la capture des données. Les réseaux sociaux que l'on cherche à étudier sont généralement issus d'une expérience de mesure d'un système donné, vu comme un graphe. Celle-ci est particulièrement déterminante : une mauvaise capture peut rendre complètement fausses les analyses subséquentes. Il faut donc, dès l'obtention des données, se poser la question des "biais d'observation", en ayant des réponses précises aux questions suivantes : - quelle proportion du système a été mesurée ? - combien de temps la mesure a-t-elle duré ? - quelles étaient les contraintes techniques ? - qui a fait la mesure ? - la mesure peut-elle être reproduite ? Compte tenu de la taille des systèmes concernés (Facebook et Twitter comptent plusieurs centaines de millions d'utilisateurs), de leur caractère dynamique (les réseaux P2P ont des utilisateurs qui ne restent dans le système que quelques heures au maximum), ces problématiques jouent fortement sur la qualité des représentations qui seront obtenues. En effet, un graphe qui ne modéliserait que 1000 utilisateurs de Facebook, par exemple, ne pourrait évidemment prétendre décrire le comportement global des membres de cette plateforme. De même, une mesure d'une heure sur un réseau P2P très populaire ne mènera qu'à des analyses limitées. Enfin, la connaissance du protocole de mesure est importante pour estimer si des informations observables ne l'ont pas été. Par exemple, l'utilisation de l'outil *traceroute*, souvent employé pour établir des « cartes physiques » de l'Internet, présente un certain nombre de caractéristiques qu'il faut maîtriser. Cet outil enregistre les chemins qu'empruntent des paquets de données pour atteindre une adresse IP spécifique, à partir d'une source. Ces deux paramètres, une adresse IP de départ et une d'arrivée, sont des contraintes fortes sur la mesure, et on doit en tenir compte : pour cartographier une zone de l'Internet (par exemple, l'environnement d'une machine donnée), il est donc nécessaire de multiplier les points "source" à partir desquels on tentera d'atteindre cette machine. Il faut noter que certaines zones seront inaccessibles (par exemple des routeurs de degré 1, sauf s'ils sont sources ou destinations), et que la répartition de charge (`load-balancing`) peut amener des routeurs en milieu de chemin à faire passer les paquets par une branche d'une fourche plutôt qu'une autre (cf les figures :ref:`zonedure1` et :ref:`zonedure2`). Ces deux phénomènes conduisent à ne pas observer certains nœuds et certains liens du réseau, ce qui peut changer considérablement les caractéristiques du réseau mesuré par rapport au réseau original (cf la figure :ref:`degreobserve`, où la distribution de degré observée n'est pas la même que celle qu'on attendrait : il y a des contraintes techniques qui ont un impact significatif sur la mesure.). .. figure:: figures/dur1.png :width: 30 % :alt: zone dure à mesurer :name: zonedure1 Nœud accessible par un seul chemin. .. figure:: figures/dur2.png :width: 30 % :alt: zone dure à mesurer :name: zonedure2 Équilibrage de charge sur une fourche. .. figure:: figures/observation1.png :width: 70 % :alt: distdegre :align: center :name: degreobserve Distribution de degré observée et distribution réelle .. eqt-mc:: coursfouillegraphesreseauxsociauxQ1 **Question :** Quels sont les risques associés à la capture des données provenant de réseaux et graphes de grande échelle ? (plusieurs réponses) A) :eqt:`I` dupliquer des données #) :eqt:`C` ne pas collecter des nœuds et liens existants en fait dans le système #) :eqt:`C` fausser les analyses ultérieures #) :eqt:`I` créer des liens inexistants Analyse ======= Une fois que les données sont collectées, il faut procéder à l'analyse de celles-ci. L'objectif est d'obtenir des informations pertinentes sur le système, à l'aide d'une description statistique que l'on interprète ensuite. L'analyse des graphes peut passer d'abord par la détermination des valeurs de certaines propriétés "classiques" (distribution de degrés, longueurs des chemins, etc.), des propriétés spécifiques pertinentes pour le graphe en question (coefficient de *clustering*, existence et taille de communautés, etc.). L'analyse peut aussi requérir une phase préalable de modélisation (cf :ref:`section-modelisation`), permettant de comparer le graphe étudié avec un ou des graphes aléatoires "similaires" (ou supposés tels). Enfin, un aspect important mais sur lequel on s'étend peu dans ce cours, c'est l'évolution dynamique des graphes : quels sont les changements des valeurs des propriétés au cours du temps. Quelques propriétés classiques ------------------------------ Les propriétés classiques que l'on peut observer sur des graphes proviennent de la théorie des graphes. - la "longueur moyenne des (plus courts) chemins" : on la définit comme la moyenne, pour toutes les paires de sommets du graphe, des plus courts chemins. Formellement, pour un graphe :math:`G(V,E)` où :math:`d(v_1,v_2)` désigne le plus court chemin entre :math:`v_1` et :math:`v_2` (:math:`v_1,v_2 \in V`), la longueur moyenne :math:`l_G` vaut : :math:`l_G = \frac{1}{n(n-1)} \sum_{i \neq j} d(v_1,v_2)`. - le coefficient de *clustering*. Il existe une version globale, parfois appelée "transitivité", et une version locale, provenant du travail de Watts et Strogatz [WS98]_. La version globale est définie comme : :math:`C = \frac{3 \times \text{nb triangles}}{\text{nb triplets connectés}}`. Un triplet connecté étant soit un triangle (triplet fermé), soit un triangle privé d'une arête (triplet ouvert). Notons :math:`N(i)` le voisinage du sommet i : :math:`N(i) = \{ v_j : e_{ij} \in E\}` (ensemble des sommets connectés à i par au moins une arête). Cette version locale mesure, pour un sommet donné, à quel point son voisinage se rapproche d'une clique (c'est-à-dire un ensemble de :math:`|N(i)|+1` sommets tous connectés entre eux). On définit le coefficient de *clustering* comme étant le rapport entre le nombre d'arêtes existant dans le voisinage et le nombre de celles qu'il pourrait y avoir s'il s'agissait d'une clique. Pour un sommet avec :math:`k_i` voisins, il pourrait y avoir :math:`\frac{k_i(k_i-1)}{2}` arêtes. Donc, la valeur du coefficient de *clustering* local est : :math:`c(i) = 2 \times \frac{|e_{xy} \in E / x,y \in N(i) |}{k_i(k_i-1)}` - la distribution de degrés :math:`P(k)`. Pour un graphe donné, il s'agit de la fraction de sommets du graphe de degré :math:`k`. S'il y a :math:`n` sommets, et que :math:`n_k` d'entre eux ont pour degré :math:`k`, :math:`P(k) = \frac{n_k}{n}`. Attention, il y a parfois une confusion de faite avec la distribution *cumulative* des degrés, désignant la fraction de sommets qui ont un degré *au moins égal à* :math:`k`. .. figure:: figures/distrib-degres.png :width: 50 % :alt: plus court chemin :align: center Distribution gaussienne (à gauche), en loi de puissance à droite. - les composantes connexes. C'est un ensemble maximal de sommets tel qu'il existe un chemin entre toute paire de sommets dans l'ensemble. Certains graphes sont entièrement connexes. D'autres non, auquel cas il est intéressant de mesurer la taille et le nombre des composantes connexes - les communautés. Ce sont des ensembles de sommets très liés entre eux et peu liés vers le reste du graphe. Nous étudierons en détail dans la seconde partie du cours quelles communautés on peut rechercher dans un graphe et les principales manières de le faire. - la centralité. Pour chaque sommet du graphe, on peut définir plusieurs mesures de centralité, qui estiment à quel point il est "central" dans le graphe : - centralité de degré, égale au degré. - centralité d'intermédiarité (betweenness centrality) : nombre de plus courts chemins passant par un sommet : :math:`C(v) = \sum_{s \neq t \neq v \in V} \frac{s_{st}(v)}{s_{st}}` - centralité de proximité : inverse de la distance à tous les autres sommets :math:`C(x) = \frac{1}{\sum_y d(y,x)}` La centralité la plus utilisée est la centralité d'intermédiarité. Les réseaux réels ont souvent des propriétés assez différentes des graphes aléatoires que l'on peut générer (cf section suivante) : - faible densité - fort *clustering* - faible distance moyenne - distribution de degré très hétérogène - composante connexe géante - présence de communautés .. eqt:: coursfouillegraphesreseauxsociauxQ2 **Question :** La *densité* d'un graphe est définie comme le rapport entre le nombre d'arêtes divisé par le nombre total d'arêtes possibles. On peut donc relier cette propriété : A) :eqt:`I` au diamètre #) :eqt:`I` à la centralité d'intermédiarité #) :eqt:`I` au nombre de composantes connexes #) :eqt:`C` au coefficient de clustering .. _section-modelisation: Modélisation ============ La modélisation, dans notre contexte, consiste à proposer des modèles de graphes afin de les comparer au graphe étudié et d'estimer si les propriétés observées étaient attendues, ou non. On utilisera souvent des graphes "aléatoires", c'est-à-dire générés par tirage aléatoire en respectant éventuellement une loi (contraignant la distribution de degrés, la densité, etc.). On peut, dans un premier temps, utiliser un modèle uniforme, en se donnant :math:`n` sommets et en décidant que chaque arête a une probabilité :math:`0`_, commencé en projet étudiant à l'Université Technologique de Compiègne et open source. Il permet l'analyse de graphes de tailles raisonnables, intègre de nombreux algorithmes et traitements classiques (PageRank, modularité, plus courts chemins, etc.), le tout en permettant un ajustement fin de la visualisation définitive. .. eqt-mc:: coursfouillegraphesreseauxsociauxQ4 **Question :** Quelles sont les difficultés algorithmiques liées aux graphes ? (plusieurs réponses) A) :eqt:`I` on manque de bibliothèques dédiées efficaces #) :eqt:`C` la taille des systèmes analysés pose problème (stockage, traitement) #) :eqt:`C` la complexité des algorithmes est généralement élevée Références ========== Ce cours repose sur les travaux de l'équipe `ComplexNetworks `_ du `LIP6 `_ au sein duquel l'auteur a effectué son travail de doctorat. En particulier, les cours de `Jean-Loup Guillaume `_ ont été une source d'inspiration précieuse, de même que le livre *Mining massive datasets* [MMDS]_ et le matériel associé. .. [AB02] Albert, R. and Barabási, A.-L. *Statistical mechanics of complex networks*. Reviews of Modern Physics. 2002. 74: 47–97. .. [G73] Granovetter, M. S. *The Strength of Weak Ties*. American Journal of Sociology, Volume 78, Issue 6 (May, 1973), 1360–1380. .. [K00] Kleinberg, J. M. *Navigation in a small world*. Nature. 2000 Aug 24;406(6798):845. http://www.nature.com/nature/journal/v406/n6798/full/406845a0.html#B2 .. [M67] Travers, J. and Milgram, S. *An experimental study of the small world problem*. Sociometry, Vol. 32, No. 4. (Dec., 1969), pp. 425-443. http://www.jstor.org/stable/2786545 .. [MABDHLC10] Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. *Pregel: A System for Large-Scale Graph Processing*. SIGMOD 2010. https://kowshik.github.io/JPregel/pregel_paper.pdf .. [MMDS] Leskovec, J., Rajaraman, A. and J. D. Ullman. *Mining of Massive Datasets*. *Cambridge University Press*, New York, NY, USA, 2011. Accessible en version numérique http://www.mmds.org .. [WS98] Watts, D. J. and Strogatz, S. H. *Collective dynamics of 'small-world' networks*. Nature 393, 440-442. http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html .. Routage dans les petits mondes Lebhar/Schabanel 2007