Département STIC. Réseau thématique: Mathématique de l'Informatique
Action Spécifique Algorithmique des grands graphes André Raspaud
- LaBRI (Thème: Graphes et Applications).
Peu d'évenements dans l'histoire de l'informatique ont eu une
influence si profonde dans la société que l'avènement et le
développement du "World Wild Web". Pour la première fois des millions
et bientôt des milliards d'individus utilisent, créent, exploitent
des données d'une façon distribuée. D'un point de vue plus général
les grands réseaux modélisés par des grands graphes sont aujourd'hui
l'objet d'études algorithmiques. Les algorithmes classiques doivent
être adaptés étant données la taille des graphes et la
faisabilité. L'objectif de cette action spécifique est de développer
en France ce courant de reherche déja fortement présent a
l'étranger. On peut citer C. Papadimitrou (modèle aléatoire pour
internet), R. Broder, R. Kumar (Graph structure in the web),
A. L. Barabasi (Complex cellular network), son livre: "Linked: The New
Science of Network". Dans ce dernier cas il s'agit des grands réseaux
présents en biologie, science sociale, informatique etc.
Les
principaux points de cette action porteront donc sur la recherche
algorithmique des grands graphes, nous développons maintenant les
idées évoquées ci-dessus:
De nombreux modèles de grands graphes ont été déjà proposés.
Les observations des réseaux existants donnent des contraintes fortes et
les modélisations doivent en tenir compte. Par exemple: graphes
``scale free''
(les degrés doivent suivre une loi de puissance), le voisinage d'un
sommet doit être très interconnecté (``clustering'' voisin de 1),
diamètre faible. Les réseaux à faible diamètre et fort clustring sont les réseaux ``petit monde''.
On s'intéressera en particulier à la construction déterministe et
aléatoire de ces graphes et
à l'adaptation des algorithmes sur les graphes;
les algorithmes de parcours et de recherche par exemple. Notre savoir faire en mathématiques discrètes, théorie des graphes et algorithmique doivent nous permettre
d'innover dans ce domaine et d'apporter notre contribution.
Pour le routage dans les graphes, les algorithmes simples demandent beaucoup d'espace mémoire. Ceci dépend de la taille du graphe. Si le graphe
considéré est ``grand'', il faut trouver des algorithmes et des méthodes plus performants pour réduire la taille de la mémoire nécessaire,
il faut de plus réduire la taille des structures de données (structures de données compactes).
Le routage dans les modèles proposés n'a pas été beaucoup étudié de
même que les problèmes de communications. La propagation d'informations et de défauts sont des points importants. L'étude des capacités structurelles
des graphes proposés
pour la réalisation d'échanges d'informations d'une façon optimale n'a
pas été réellement abordée jusqu'à présent.
Les documents du Web peuvent être vus comme des arbres étiquetés
(XML). Les requêtes sur ces documents demandent des algorithmes rapides et des
étiquetages dont le codage est réduit en place. L'algorithme de la
recherche de l'ancêtre commun est un algorithme utilisé et des travaux récents
sur le sujet montrent l'intérêt de cette problématique. Plus généralement les structures de données compactes permettent de représenter et
dans un second temps d'extraire de l'information issue de données de très grandes tailles. On peut espérer gagner du temps en ajoutant
aux données des attributs compacts.
Les équipes impliquées sont (certaines ont déjà des contributions
dans le domaine):
INRIA Rocquencourt: Projet Hipercom (Laurent Viennot)
LRI/LIX: Algorithmique et complexite (Claire Kenyon), Théorie des
Graphes et Fondement des Communications (Pierre Fraigniaud)