2014-05-24 Graphs and Map / Reduce
Implementing graph algorithm on map/reduce is still a challenge. But maybe because it is a challenge, people keep thinking about it. It is the purpose of GraphX which reduces the processing time for the Page Rank algorithm on a Spark environment. It is not as fast as PowerGraph which is not based on Map/Reduce but it is must faster than Mahout (see paper GraphX: A Resilient Distributed Graph System on Spark). One fact, the language Scala appears more and more. A sign: Mahout recently took the decision to stop implementing machine learning algorithm against Map/Reduce to switch to Spark.
2014-04-20 Les algorithmes sur les graphes ne sont pas aussi simples en Map/Reduce
Je ne suis plus d'où cette histoire est partie ni si elle est vraie mais on dit souvent que si on relie deux personnes quelconques dans le monde par une chaîne d'amis, cette chaîne ne sera pas plus longue que 7. Sans doute Facebook pourrait y trouver à redire. Ce qui m'intéresse ce soir est de savoir la longueur de la chaîne qui me relie au Président de la République.
Je serais bien incapable de vous donner la réponse mais je pourrais vous dire comment la trouver. Si un de vos amis connaît la réponse à cette question, si cette réponse est l, alors dans votre cas, la réponse sera l+1 et vos amis pourront dire que la réponse dans leur cas est l+2. Pour que toute personne dans Paris ait la réponse à cette question, il suffit qu'une vague parte du président et se propage à chacun d'entre nous.
L'algorithme est en lui-même assez simple à implémenter à condition que le graphe soit petit. Lorsqu'il est grand (plusieurs dizaines de millions de noeuds), cela prend du temps, beaucoup de temps même si cela ne peut plus se faire sur le même ordinateur. On pense alors au concept Map/Reduce qui permet d'effectuer des calculs distribués sur plusieurs machines. Mais dans ce cas-ci, ce n'est pas si évident. Et pour comprendre pourquoi, la lecture continue ici : Graphe et Map Reduce.
J'ajoute ici quelques commentaires qui me sont parvenus cette semaine.
Le nombre de connexions qui relient deux individus est un vieux problème : Small-world experiment, Le nombre d'Erdős. Les algorithmes sur des grands graphes ne sont jamais évidents, ne serait-ce que pour calculer (en un temps raisonnable) le plus court chemin entre deux pages Wikipedia comme sur Wikidistrict, décrite ici Wikidistrict, une exploration ludique de Wikipédia. Le premier réflexe lorsqu'on traite un grand nombre de données est de réduire la taille du problème ou de regardeer sur des examples. Cependant, s'il est facile de concevoir ce qu'est un échantillon au sein d'une population, qu'est-ce qu'un échantillon au sein d'un graphe, un échantillon qui respecte les propriétés du graphe. Vous trouverez quelques réponses ici : Statistical Analysis of Network Data (Eric D. Kolaczyk).
|
Xavier Dupré
|
