Acknowledgments

As I prepare to upload this thesis to the University of Montpellier II server, thereby setting it in stone for all eternity, I cannot help but acknowledge that it would not have been possible without the contributions of many people, to whom I wish to pay a well-deserved tribute.

First of all, even if it is hardly conventional, thank you to the one without whom Fabien Mathieu would be little more than the sum of two first names. Thank you Papa — it is thanks to you that this thesis exists, and it is only natural that I dedicate it to you.

Thank you also to the one I met when I was more or less finishing my DEA, and the thesis was still something strange and otherworldly to me. Without Laurent Viennot to bring me back down to earth, I might still be searching for the Fourier transform of the Web graph. I still do not know how he managed to supervise a PhD student like me, stubborn and living on New York time, but it is thanks to his patience that I am able to write these lines today, and I will be eternally grateful to him. Thank you Laurent — the researcher —, and thank you Laurent — the friend.

I also wish to thank Michel Habib, who agreed to supervise me with full knowledge of what he was getting into and placed his complete trust in me. His unwavering support allowed me to practice Mediterranean-Parisian ubiquity during those few years. May he in turn enjoy the same freedom that I was able to have thanks to him.

Thank you to the reviewers of this thesis for giving me their time and attention, and for managing to endure the delays I imposed on them: thank you to Serge Abiteboul, who revealed the weaknesses of my thesis and helped me correct some of them; thank you to Pierre Fraigniaud for risking even his morality in the service of science.

I also wish to thank the other members of the jury, Alain Jean-Marie, whose corrections were very helpful to me, and Vincent Blondel, whose interest in my thesis particularly touched me. Thank you as well to François Baccelli, who unfortunately had to send his apologies at the last moment.

Thank you to all the researchers, webmasters, and ordinary internet users for all the data they were kind enough to send me by email when I needed it. The list is long, but I have by no means forgotten their contributions — quite the contrary.

Obviously, none of this would have been possible without the support of the countless unsung workers whom I had the opportunity to press into service, particularly during the writing phase. A loyal inner circle, they tirelessly proofread the successive drafts leading up to the present version. If there are fewer than twenty mistaeks per page, it is thanks to them.

The Montpellier team first. Fabien (the other one), whose thesis source code allowed me to go from to pages in less time than it takes to type “copy/paste” with a jackhammer. I cannot help but acknowledge that these acknowledgments would not have been possible without his contributions, and I wish to pay him a well-deserved tribute. Mohamed, for his part, was there for me every time I was not there myself, and I also do not forget that without his programming skills, I would never have crossed the million page mark within the allotted time.

The Parisian team next. Julien, who is unmatched when it comes to making a chocolate mousse with rinse-aid salt for people, and who was kind enough, along with Anamaria, to lend me a base camp for the summer of . Speaking of base camps, a big thank you to Fanfan. Her bed is too hard, but the dreams are beautiful. And I of course do not forget Mathilde, who overcame her handicap (being blonde and a literature student) to give me precious stylistic advice.

I also have a special thought for Danielle Croisy, from INRIA, although I cannot explain how she managed to put up with all those overdue travel orders.

Thank you to all the others whose support I have not forgotten. Thank you very many to Mickey and Thibaut for stopping by the LIRMM in December 2004. Thank you to the entire Halle Gorithme, with its rabbits, its crawlers, its pizzas, and its oysters.

Finally, a big thank you to my sister Nathalie, my aunt Marie-Paule, my niece Marion, and my nephew Quentin. After roaming the four corners of France and beyond, one comes to truly appreciate knowing that there is a place where one feels at home.