Discussion :

[Cedric Chevalier]

Des chercheurs du MIT créent KLOS, un algorithme puissant de parcours de graphe non orienté
plus performant que les algorithmes de flots maximum connus

Qu’est ce qu’un graphe ? Des points et des lignes. En tout cas, c’est la réponse que donnerait n’importe quel profane s’il était mis en présence de cette structure simple, mais puissante, dont les applications tant en génétique qu’en informatique sont légions.

La méthode de compression des fichiers au format Zip créée par l’américain David Huffman en 1952 est une application de la théorie des graphes. On peut également citer l’algorithme de recherche du plus court chemin proposé par le néerlandais Edgser Dijkstra, algorithme très employé dans le domaine des réseaux informatiques, où son utilité permet aux routeurs de déterminer le plus court chemin que doit emprunter un paquet pour atteindre sa destination.

Les graphes sont omniprésents en informatique. Leur origine est associée aux travaux du mathématicien Leonhard Euler en 1736, mais ils sont cependant très discrets. Combien sont-ils au courant de leur existence, alors qu’ils sont quotidiennement employés ?

Il n’est donc pas surprenant que le tout nouvel algorithme des chercheurs du MIT n’attire lui non plus l’attention, autant que le ferait la sortie d’un tout nouveau smartphone comme l’iPhone 5s par exemple.

Les travaux des chercheurs du MIT ont en effet porté sur la création d’un nouvel algorithme de parcours de graphe, dont l’évolution est quasi linéaire. Ils l’ont sobrement baptisé « KLOS algorithm », en l’honneur des chercheurs qui lui ont donné naissance (Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et Aaron Sidford).

KLOS est présenté comme l’algorithme de parcours de graphe le plus abouti à l’heure actuelle. Il serait plus performant que les algorithmes de flot maximum (max flot) connus. KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.

Existe-t-il déjà des bibliothèques d’implémentation de KLOS ? Aucune à l’heure actuelle. Les développeurs sont appelés à être patients, car ça ne saurait tarder.

Source: Rapport de recherche PDF

Et vous ?

Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?

[hannibal.76]

Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?

Attendre peut etre pas, je vais surtout remonter mes manches et implémenter ceci dans l'API Graphstream

[KsassPeuk]

L'important ici n'est clairement pas le parcours mais le flot maximum, or on a l'impression que c'est le parcours qui nous intéresse ici. Avec une structure de donnée basique, on peut déjà faire du linéaire en (n+m) pour le parcours.

[GLDavid]

Bonjour

Je vois déjà une bonne implémentation de ces différents algorithmes dans mon domaine: la bioinformatique.
Savez-vous ce qu'est l'interactomique ? Il s'agit de la science d'étude des interactions entre les différentes protéines et les métabolites. Cette science utilise donc des graphes pour retranscrire le réseau d'interactions. Ces réseaux sont importants afin d'étudier toute la voie de signalisation d'une cellule, ce qui explique notamment des processus de pathologie comme le cancer. Mais également de mettre en évidence des voies de thérapies sur des cibles clairement identifiées par ce biais.
Ce qui émerge c'est l'inférence de réseaux: si une protéine est normalement produite, quel est l'impact dans la cascade des évènement si je la surexprime ? Ou si je la sous-exprime ?
Evidemment, des initiatives existent déjà pour encoder ces réseaux (XML et HUPO-PSI-MI notamment, plus RDF). Pour le jeu d'algorithmes comme la recherche de voisins ou le plus court chemoin, tout cela est intéressant pour gagner en performances.

A voir donc dans ce domaine.

@++

[Invité]

Peut-être une question stupide mais je me lance

A fortiori, KLOS devrait être applicable à des graphes orientés ?

Steph

[srvremi]

Pour mes cours j'ai hâte de voir si ce sera implémentable par des élèves de niveau bac +3/+4.

@+
Rémi

[if_zen]

Petite question : est-ce que ce genre d'algorithme pourrait simplifier et améliorer les performances et résultats de l'algorithme du "voyageur de commerce" (cf. Wikipedia, ne pas confondre avec Dijkstra) consistant à trouver le plus court chemin sur un ensemble d'étapes pré-établi ?

[razlock]

@if_zen je me posais la même question. De très bon algorithmes pour résoudre ce problème se basent sur les algos de flots, donc j'aurais tendance à dire qu'il y aura des répercussions sur pas mal de problèmes de ce genre ...

wait & see

[Patriarch24]

J'ai jeté un œil au papier, mais malheureusement mes compétences en mathématiques sont loin derrière moi et cela m'empêche de comprendre le tout (si tant est que mes compétences passées fussent suffisantes). Il faut être au point en algèbre...

[azias]

Petite précision sur le nom "KLOS": ce ne sont pas les auteurs qui ont nommés cet algorithme KLOS, ils ne lui ont pas donné de nom (y aurait-il une raison de le faire d'ailleurs?). Alors c'est tout simplement nous tous qui utilisons KLOS par simplicité.

J'ai vaguement parcouru l’article ce week-end, j'ai été assez vite dépassé, je pense qu'il faut déjà connaître un peu les travaux antérieurs, en tout cas le vocabulaire, pour suivre.

Ils expliquent dans l’introduction qu'il s'agit d'une amélioration des algorithmes existant, leur permettant d'atteindre pour la première fois une complexité "quasi-linéaire" pour une résolution approchée du problème.

Le problème en question est un problème d'optimisation, celui du flot maximum: dans le graphe il y a une source et un puits et il s'agit de trouver comment répartir l'utilisation des arrêtes (chacune ayant sa limite de capacité) pour obtenir un flot maximum qui part de la source pour tomber dans le puits.

[Teto45]

... Les développeurs sont appelés à être patients, car ça ne saurait tarder.

Heu... cette phrase a comme un problème... Pourquoi être patient si l'implémentation ne saurait tarder ?

[MABROUKI]

bonjour

KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.

Pourquoi presentent -t-ils seulement l'application du Laplacien d'un graphe (matrice associe à un graphe voir wiki fr) au probleme de Flot Max ramene à un probleme Kirchoff(loix des noeuds et des mailles) + contraintes sur les capacites des arcs
Le theoreme de Kirchoff calcule l'ecoulement max des flots "naturels" de fluides ou de courants electriques dans les reseaux.(sans contraintes sur capacites)...Les contraintes sur capacites compliquent serieusement le probleme de Kirchoff dans les modeles pratiques

Le comportement physique naturel des reseaux est tel que l'equiblibre s'etablit au max de flot transmissible....

L'amelioration attendu de cet algo KLOS dans le cas du MaxFlot ,est que le MaxFlot existant calcule un chemin augmentant à la fois ,l'un apres l'autre,ce qui prend trop de temps pour un reseau ou il peut y avoir des millions de noeuds à traiter ...
Le nouvel algo utilise le Laplacien du graphe pour resoudre un probleme de Kirchoff ...
Comme un probleme de Kirchoff est un systeme d'equations lineaires ,la methode iterative du gradient conjuque est utilise avec calcul simultane sur tous les chemins augmentants possibles ....Hic:une methode iterative est approximante....d'ou le titre

Voir ce lien de (Algorithmic Primitives for Network Analysis:
Through the Lens of the Laplacian Paradigm):
http://www.google.fr/url?q=http://ww...RJpEfjdq727wew

Ensuite ce lien plus instructif sur le home page de l'un des auteurs de "KLOSS" Aleksander Madry ou il livre une serie de pdf sur ses recherches :max flow,voyageur du commerce et spanning traites par des methodes algebriques...http://www.google.fr/url?q=http://th...HcrAq5kW8DRcFg

Ce qui intrigue : l'utilisation de cette methode algebrique est limite au flot max à la presentation de portland...

Vpici un papier de 2 gourous de Microsoft Research Center bien detaille sur ce lien pour ceux desireux de s'informer :
http://www.google.fr/url?q=http://research.microsoft.com/en-us/um/people/nvishno/site/Lxb-Web.pdf&sa=U&ei=jefeUt2UBvT3ygOorYD4DA&ved=0CCMQFjAA&usg=AFQjCNFRbmJD6qjyGoVBn498UUJcrr4w



bonne lecture........