Les graphes, composés de sommets et d’arêtes sont des objets communs en mathématiques (et indispensables) en informatique. Lorsqu’on veut manipuler des graphes de plusieurs centaines de millions de sommets, voire de plusieurs milliards de sommets, comme le graphe du web (ou un sous-ensemble) ou le graphe de certains réseaux sociaux, les choses se compliquent singulièrement : la plupart des algorithmes « académiques » se heurtent au « mur » de la complexité en temps (voire en espace), que nous appellerons le mur du « Big Data ». Tout algorithme dont la complexité est de l’ordre de O(n³) ou même de l’ordre de O(n²) est en fait inutilisable en pratique (ou très coûteux) dès lors que n, le nombre de sommets, dépasse (disons) le milliard. Il faut alors suivre d’autres stratégies. Il faut par exemple accepter de ne pouvoir calculer qu’une approximation même si dans certains cas, cette approximation peut en fait être la valeur exacte.
Cet article se propose de présenter la stratégie dite des « sauts multiples » (multiple sweep) et certaines tactiques développées ces dernières années pour résoudre unproblème classique sur les graphes géants : le calcul du diamètre, du rayon et du centre d’un graphe non orienté. Nous finirons par discuter de la faisabilitéde résoudre le problème du calcul du diamètre, du rayon et du centre d’un célèbre graphe non orienté : le « graphe du web ».
1. Graphes
1.1 Dessine-moi un graphe
Un graphe, au sens mathématique, est une structure composée d'objets (les sommets ou les nœuds) dans laquelle certaines paires d'objets sont « liées » par des arcs (on dit arête dans le cas où ce lien est orienté). Ainsi, lorsque vous regardez un plan de métro, que ce soit à Londres ou à Paris, en fait vous regardez un graphe dont les sommets représentent les stations et les arcs représentent les trajets entre les sommets. Les graphes sont très présents...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première
[1] C. Magnien, M. Latapy et M. Habib, Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs, ACM Journal of Experimental Algorithmics (JEA), 13, 2008. Disponible à https://www-complexnetworks.lip6.fr/~magnien/Publis/17diam/article.pdf
[2] C. Magnien,le code (en C) et des graphes géants : https://www-complexnetworks.lip6.fr/~magnien/Diameter/
[3] T. Cormen, C. Leiserson et R. Rivest, Algorithmique - 3ème édition, 2010, Dunod.
[4] V. D Blondel, J.-L . Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment (10), P10008, 2008.
[5] M. Lesk, Diamètre de graphes et qualité de service d’un réseau de données, Revue française d’automatique, d’informatique et de recherche opérationnelle. Recherche opérationnelle, tome 18, n°3 (1984), p. 247-261. Disponible : https://www.rairoro.org/articles/ro/pdf/1984/03/ro1984180302471.pdf
[7] L. Auroux, M. Burelle et R. Erra, Reordering Graphs For Fun & Profit, ISWAG 2015. Disponible : https://hal.archives-ouvertes.fr/hal-01171295/document
[8] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph structure in the web, éditeur, 2003. Disponible à : https://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/broder.pdf
[9] R. Albert, H. Jeong, et A.-L. Barabasi,Diameter of the World Wide Web, Nature 401: 130-131, Sept. 1999.
[10] L. Backstrom, P. Boldi, M. Rosa, J. Ugander et S. Vigna, Four Degrees of Separation, 2012. Disponible à : https://arxiv.org/pdf/1111.4570.pdf
[11] P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi, A. Marino, Finding the diameter in real-world graphs: experimentally turning a lower bound into an upper bound, Proc. ESA, LNCS, vol. 6346, 2010, p. 302–313.
[12] P. Crescenzi, R. Grossi, L. Lanzi, A. Marino, On Computing the Diameter of Real-World Directed (Weighted) Graphs, SEA : Experimental Algorithms, p. 99-110, Springer, 2012.
[13] P. Crescenzi, R. Grossi, M. Habib, L. Lanzi, A. Marino, On computing the diameter of real-world undirected graphs, Theoretical Computer Science, 514 pp 84–95, 2013.
[14] T. AkibaYoichi et I. Kawata, An Exact Algorithm for Diameters of Large Real Directed Graphs, SEA : Experimental Algorithms, p. 56-67, Springer, 2015.
[15] F. W. Takes et W. A. Kosters, Computing the Eccentricity Distribution of Large Graphs, Algorithms, 2013, 6, 100-118.
