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

Amélioration de l’infrastructure

Magazine
Marque
Linux Pratique
HS n°
Numéro
48
Mois de parution
septembre 2020
Domaines
Résumé

Notre serveur est en place et notre intranet est entièrement fonctionnel ! Il est temps, maintenant, d’aller plus loin et de s’assurer qu’il fonctionne aussi efficacement que possible et de se faciliter, autant que possible aussi, sa maintenance. Dans la même idée, nous allons aussi en profiter pour mettre en place des sauvegardes afin de nous prémunir d’une éventuelle perte des données du wiki.

Détection d'anomalies par ACP

Magazine
Marque
MISC
Numéro
111
Mois de parution
septembre 2020
Domaines
Résumé

Retour de vacances. L’analyse du SIEM après un mois d’absence montre que dix incidents ont été déclenchés sur la base des alertes automatiques et ont pu être gérés convenablement par la chaîne de traitement d’incidents. Tout est-il sous contrôle ? Un analyste aimerait rapidement s’en assurer en complétant cette supervision par sa propre analyse du mois écoulé. Mais par où commencer ? Il est inenvisageable de regarder un mois de logs « rapidement » et d’autant plus quand on ne sait pas précisément ce que l’on cherche… Une solution possible est de recourir à des outils statistiques qui permettent d’identifier des périodes d’activité atypiques sur lesquelles concentrer son analyse. L’analyse en composantes principales (ACP ou PCA en anglais) est une méthode statistique qui peut répondre relativement efficacement à cette problématique. L’article présente cette méthode et son apport dans la détection d’anomalies, en prenant comme exemple l’analyse de flux réseaux.

Installation du serveur à l’aide d’Ansible

Magazine
Marque
Linux Pratique
HS n°
Numéro
48
Mois de parution
septembre 2020
Domaines
Résumé

Comme annoncé dans l’introduction de ce dossier, nous allons documenter l’installation et la configuration de notre serveur RHEL à l’aide du fichier de configuration Ansible (que l’on nomme « playbook »). Afin de nous assurer que le lecteur dispose de tous les éléments nécessaires à la bonne compréhension du contenu de ce numéro spécial, nous allons donc commencer par un rapide tour d’horizon de cet outil.

Avec Asterisk, déployez votre serveur vocal interactif

Magazine
Marque
Linux Pratique
Numéro
121
Mois de parution
septembre 2020
Domaines
Résumé

Un serveur vocal interactif permet de fournir des fonctionnalités permettant de guider un appelant ou de libérer des employés de tâches fastidieuses et répétitives. Il est ainsi possible d’orienter un appelant vers le bon service, enregistrer les coordonnées de carte bancaire ou proposer un rendez-vous.

Introduction au dossier : Déployez un intranet Linux dans votre PME avec Ansible & Red Hat Enterprise Linux

Magazine
Marque
Linux Pratique
HS n°
Numéro
48
Mois de parution
septembre 2020
Domaines
Résumé

Bienvenue dans ce numéro spécial dédié à la mise en place d’un intranet à l’aide de Red Hat Enterprise Linux (RHEL) ! Comme vous allez vite le voir, l’utilisation de la distribution au chapeau rouge ne change que peu de choses et tout ce que nous allons aborder dans ce dossier (ou presque) pourra être utilisé ou reproduit sur des distributions similaires, telles que CentOS ou encore simplement Fedora.