Graphes géants creux : comment définir le centre du Web

Magazine
Marque
MISC
HS n°
Numéro
18
Mois de parution
novembre 2018
Domaines


Résumé

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...

Cet article est réservé aux abonnés. Il vous reste 96% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite
Références

[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/

[3T. Cormen, C. Leiserson et R. Rivest, Algorithmique - 3ème édition, 2010, Dunod.

[4V. 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

[6] https://www.newcastle.edu.au/__data/assets/pdf_file/0014/22460/06_Automatic-element-reordering-for-finite-element-analysis-with-frontal-solution-schemes.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.

[16] https://neo4j.com/blog/analyzing-panama-papers-neo4j/



Articles qui pourraient vous intéresser...

Et si on déchiffrait la machine Enigma...

Magazine
Marque
GNU/Linux Magazine
Numéro
235
Mois de parution
mars 2020
Domaines
Résumé

La machine Enigma fut utilisée par les Allemands, pendant la Seconde Guerre mondiale, pour chiffrer des messages secrets. Alan Turing est connu pour avoir fortement contribué à la compréhension du fonctionnement du chiffrement de cette machine. Dans cet article, je vais présenter le modèle M3 de la machine Enigma et proposer une simulation de cette machine utilisant le langage Python.

Informatique quantique : l’empire des chats morts-vivants

Magazine
Marque
GNU/Linux Magazine
Numéro
233
Mois de parution
janvier 2020
Domaines
Résumé

Le célèbre paradoxe du chat, à la fois vivant et mort, expérience de pensée due à Erwin Schrödinger en 1935 [1], est très certainement la « bizarrerie » la plus connue, mais aussi la plus perturbante de la mécanique quantique. Elle avait pour but d’illustrer simplement les paradoxes de la mécanique quantique, à une époque où elle n’était pas encore acceptée par les scientifiques. Pour comprendre le passage du monde quantique (la boîte n’est pas ouverte et contient un chat mort-vivant) au monde classique (la boîte est ouverte et le chat est soit mort soit vivant), nous allons présenter les problèmes de cohérence et de mesure. Partons donc à la chasse aux chats morts-vivants.

Les filtres de Bloom : un peu de bruit pour beaucoup [1] !

Magazine
Marque
GNU/Linux Magazine
Numéro
231
Mois de parution
novembre 2019
Domaines
Résumé

Avec l’explosion des données (un fichier de logs, par exemple), chercher une information particulière déjà connue devient une tâche complexe. Or depuis 1970, il existe une technique particulièrement puissante qui permet de résoudre très efficacement ce problème : les filtres de Bloom. Cet article propose de les explorer et de montrer comment les implémenter.

Quelques applications des Arbres Binaires à Commande Équilibrée

Magazine
Marque
GNU/Linux Magazine
Numéro
218
Mois de parution
septembre 2018
Domaines
Résumé

Les Arbres Binaires à Commande Équilibrée, ou ABCE, ont été présentés dans GLMF n°215 [1] au moyen d'une métaphore ferroviaire. Cependant, ils sont surtout utiles dans certains circuits numériques, dont ils améliorent la vitesse et la consommation, pour la plupart des technologies. Par rapport à un arbre binaire classique, le gain de performance augmente avec la taille, ce qui est un atout précieux pour concevoir des circuits intégrés par exemple.

À la découverte des Arbres Binaires à Commande Équilibrée

Magazine
Marque
GNU/Linux Magazine
Numéro
215
Mois de parution
mai 2018
Domaines
Résumé

Dans cet article un peu théorique, nous allons jouer avec la métaphore des aiguillages. Vous pensiez peut-être que concevoir une gare de triage est un jeu d'enfant, mais quand des contraintes (fictives ? réelles ?) s'en mêlent, il faut se gratter un peu la tête et faire appel à des permutations astucieuses... C'est ainsi qu'apparaissent les ABCE, ou Arbres Binaires à Commande Équilibrée, une technique inhabituelle qui trouve sa place, entre autres, dans des circuits électroniques numériques.