Vincent BLONDEL
TFE pour 2006-2007
Cette page se trouve à l'adresse: http://www.inma.ucl.ac.be/~blondel/tfe2006.html
Les étudiants intéressés par les sujets de mémoire repris plus bas peuvent m'envoyer un courriel à l'adresse: vdb@mit.edu. Je ne serai pas présent à l'UCL avant août 2006.
Captcha: distinguer hommes et ordinateurs 

Un captcha est un programme qui génère automatiquement des tests que la plupart des humains passent sans difficultés alors que les programmes informatiques actuels n'y parviennent pas. Ainsi par exemple les humains décodent sans difficulté le texte déformé suivant alors qu'un ordinateur n'y parvient pas de manière systématique.
 
Les premiers captchas ont été introduits il y a quelques années et sont utilisés aujourd'hui, par exemple par Yahoo! ou Skynet, pour éviter l'ouverture automatique d'un grand nombre d'adresses email gratuites. Les applications potentielles des captchas sont nombreuses; ils permettent par exemple d'éviter des "votes automatiques" sur internet et ils pourraient être utilisés pour combattre le spam en exigeant d'un émetteur qu'il s'identifie comme humain en résolvant un captcha pour chaque envoi.
Dans d'autres contextes, la difficulté d'automatiser de telles tâches de reconnaissance (reconnaissance d'image, de voix, de spam, etc.) de manière automatique est un frein à la réalisation de ces tâches à grande échelle. Des auteurs ont proposé récemment d'effectuer ces tâches de manière distribuée par des humains soit en formulant le problème de reconnaissance comme un jeux, soit en utilisant la tâche de reconnaissance comme moyen de micro-paiement. Ainsi par exemple les jeux interactifs Peekaboom (voir http://www.peekaboom.org) et esp (http://www.espgame.org) sont des jeux qui permettent à leurs concepteurs d'obtenir des descriptions d'images comme résultat de jeux sur internet. Pour des micro-paiements, on peut imaginer qu'en échange de l'obtention du fichier électronique d'un article de journal ou en échange du déchargement d'un morceau de musique il soit demandé d'effectuer une petite tâche de reconnaissance vocale.
Ces différents exemples illustrent l'apparition d'un nouveau paradigme en informatique. Dans le cadre de ce mémoire, on s'intéressera à une description de l'émergence de ce nouveau paradigme et on s'intéressera tout particulièrement aux premières tentatives de description formelle.

Références

Pour les captchas, voir les pointeurs au départ du site http://www.captcha.net/

L. von Ahn, M. Blum, N. Hopper and J. Langford. CAPTCHA: Using hard AI problems for security. In
Advances in CryptologyEurocrypt '03 (Volume 2656 of Lecture Notes in Computer Science), pages 294311, 2003.

Secure Distributed Human Computation, Gentry, Ramzan, Stubbledine, Financial Cryptography
and Data Security, 2006.
Construction et représentation de réseaux sociaux
En collaboration avec le groupe de recherche Large graphs and networks

Des méthodes innovantes ont été proposées ces dernières années pour récolter de l'information sur les réseaux sociaux, pour identifier des communautés dans ces réseaux et pour en obtenir des représentations. Ainsi, par exemple, des chercheurs américains ont proposés en 2005 une représentation des liens entre les membres du congrès américain basée sur leur appartenance à des groupes de travail. Nous proposons d'étudier certaines de ces méthodes et d'analyser un réseau social particulier relatif au monde économique belge.


 


Références

 Pour des références générales sur les réseaux voir les liens au départ de http://mit.edu/vdb/www/6.977/

Community Structure in the United States House of Representatives
Mason A. Porter, Peter J. Mucha, M. E. J. Newman, A. J. Friend, Feb 2006.
 http://arxiv.org/abs/physics/0602033

 Modularity and community structure in networks
M. E. J. Newman, 2006
http://arxiv.org/abs/physics/0602124
Google, chaînes de Markov et thermodynamique
Mémoire encadré conjointement avec Jean-Charles Delvenne

En 1998, Brin et Page introduisent l'algorithme du PageRank, coeur du moteur de recherche Google. Cet algorithme considère un surfeur qui se balade sur le Web de la façon suivante: il part d'une page quelconque, et suit à chaque étape un hyperlien au hasard parmi ceux qu'il trouve sur la page. On calcule alors la fréquence avec laquelle chaque page est visitée, qui est une mesure de la qualité de la page. Cela revient à transformer le Web en une chaîne de Markov dont on calcule la distribution d'équilibre.
On considère à présent la variante suivante du PageRank. Les probabilités de transition de cette chaîne de Markov sont modifiées de manière à maximiser son entropie, c'est-à-dire à rendre le comportement du surfeur maximalement imprévisible. On calcule à nouveau la probabilité d'équilibre.
L'objectif du TFE consiste à comprendre l'algorithme, étudier ses propriétés, le comparer au Pagerank, et explorer d'autres applications au-delà de la classification des pages Web. Les travaux peuvent prendre une tournure théorique ou expérimentale.
Similarité dans les graphes. Application à l'extraction de motifs biologiques
En collaboration avec le groupe de recherche Large graphs and networks

 Plusieurs mesures de similarité dans les graphes et réseaux ont été proposées ces dernières années et les liens que ces définitions entretiennent entre elles ne sont pas clairement identifiés. Dans ce mémoire, nous souhaitons présenter les différentes mesures de manière unifiée, fournir une interprétation pour certaines d'entre-elles au moyen de marches aléatoires et, finalement, envisager l'application de certaines de ces méthodes pour l'extraction de motifs dans des réseaux biologiques.
Références
Vertex similarity in networks
E. A. Leicht, Petter Holme, M. E. J. Newman
Phys. Rev. E 73, 026120 (2006).
Vincent D. Blondel, Anahí Gajardo, Maureen Heymans, Pierre Senellart, Paul Van Dooren
A measure of similarity between graph vertices. With applications to synonym extraction and web searching
SIAM Review, 46:4, pp. 647-666, 2004.

R Milo, S Shen-Orr, S Itzkovitz, N Kashtan, D Chklovskii & U Alon,
Network Motifs: Simple Building Blocks of Complex Networks
Science, 298:824-827 (2002).
Effet de la topologie d'un réseau sur la propagation d'épidémies
En collaboration avec le groupe de recherche Large graphs and networks
Collaboration éventuelle avec A. Ganesh (Microsoft Research, Cambridge)
Un grand nombre de phénomènes sont modélisés par la propogation d'épidémies sur des réseaux. Dans certains cas l'épidémie n'est pas souhaitée (comme dans le cas d'un virus ou d'un virus informatique) et on recherche alors des stratégies optimales pour éviter ou atténuer la propagation (par vaccination par exemple); dans d'autres cas le souhait peut être d'obtenir une propagation aussi rapide que possible (par exemple lorsqu'il s'agit de transmettre rapidemment une information à toute une population). Dans ce mémoire on réalisera d'abord un compte-rendu des approches possibles de tels phénomènes. On s'intéressera ensuite à la quantification, pour un modèle particulier, de la vitesse de propagation de l'épidémie et la dépendance de cette vitesse pour différentes topologies de réseau ("random", "scale-free", "small-world"). On considèrera ensuite la possibilité d'étendre les résultats actuels à une situation dans laquelle le réseau évolue avec le temps. Une première analyse de ce problème semble faire apparaître de nouvelles questions qui se lient de manière élégante à des résultats récents obtenus pour le calcul du rayon spectral conjoint.

Références

The effect of network topology on the spread of epidemics, A. Ganesh, L. Massoulié, D. Towsley, Proc. IEEE Infocom, 2005.

Designing a Contact Process : The Piecewise-Homogeneous Process on a Finite Set with Applications, Aaron Wagner and Venkat Anantharam, Stochastic Processes and their Applications, Vol. 115, No. 1, pp. 117 -153, January 2005.

Efficient algorithms for deciding the type of growth of products of integer matrices, Raphaël Jungers, Vladimir Protasov, Vincent D. Blondel, Preprint, 2006

Physique et informatique

Le professeur M. Mézard est sur le point de publier un livre (disponible sur le web gratuitement à l'adresse http://ipnweb.in2p3.fr/~lptms/membres/mezard/, voir aussi la référence plus bas) intitulé: Constraint Satisfaction Networks in Physics and Computation. L'ouvrage est passionnant et ouvre de nombreuses perspectives innovantes à la frontière entre physique et informatique théorique. Presque chaque chapitre du livre peut faire l'objet d'une introduction à un sujet de mémoire. Nous avons un intérêt tout particulier pour les aspects liés à la propagation de croyance ("belief propagation") ainsi qu'aux développements relatifs aux fascinants verres de spin ("spin glasses").

Référence

Passing Messages Between Disciplines, Marc Mézard, Science 19 September 2003, Vol. 301. no. 5640, pp. 1685 - 1686