Vincent BLONDEL, TFE pour 2008-2009

Cette page se trouve à l'adresse: http://www.inma.ucl.ac.be/~blondel/tfe2008.html
Captcha: distinguer hommes et ordinateurs
Encadrement: Vincent Blondel

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 de calcul humain distribué. 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.
GSM et réseaux sociaux
Encadrement: Vincent Blondel, en collaboration avec le groupe de recherche Large graphs and networks

Depuis quelques années, la disponibilité de vastes bases de données sur les communications entre détenteurs de gsm permet d'éclairer l'analyse des réseaux sociaux sous un jour radicalement neuf. Des hypothèses sociologiques vieilles de plusieurs décénies sont aujourd'hui mises à l'épreuve d'analyses précises. Dans le cadre de projets récents nous avons effectué des premières analyses d'un réseau de mobilophonie de plusieurs millions d'utilisateurs et de près d'un milliard de communications. De nombreuses questions passionantes restent ouvertes. 


Figure: Représentation de communautés d'utilisateurs de GSM en Belgique (en rouge francophones, en vert néerlandophones).

Références
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Fast unfolding of community hierarchies in large networks. arXiv:0803.0476 
Renaud Lambiotte, Vincent D. Blondel, Cristobald de Kerchove, Etienne Huens, Christophe Prieur, Zbigniew Smoreda, Paul Van Dooren, A gravity model for the geographical dispersal of mobile communication networks. arXiv:0802.2178
Détection d'agents dans des graphes 
Encadrement: Vincent Blondel avec Raphaël Jungers

Un agent se déplace dans un graphe en empruntant les arêtes du graphe. Chaque arête possède une certaine couleur et à chaque déplacement de l'agent on observe la couleur de l'arête empruntée. On désire localiser l'agent dans le graphe en se basant uniquement sur la suite des couleurs émises. Dans certains graphes cette localisation est toujours possible (le graphe est dit "observable"), dans d'autres elle ne l'est pas. Le graphe de gauche est observable: toute observation de longueur 3  permet de déterminer la position de l'agent (par exemple, après l'observation vert-rouge-vert, l'agent doit être en bas à droite). Par contre le graphe de droite n'est pas observable (pourquoi?).

Dans un graphe observable [1], on désire donc connaître la position de l'agent dans le graphe. Dans un graphe traçable [2], on s'intéresse par contre à la trajectoire complète de l'agent et on souhaite que le nombre de trajectoires compatibles avec les couleurs observées n'augmente pas trop rapidement. Dans le graphe de gauche il y a 5 trajectoires compatibles avec l'observation rouge-rouge-vert, mais combien y en a-t-il dans le pire des cas pour une observation de longueur 10, 30 ou n?

Dans ce mémoire on s'intéressera à différents aspects liés au graphes observables et aux graphes traçables. Les possibilités liées à ce sujet sont multiples: l'étudiant pourra implémenter les récents résultats présentés dans la littérature, ou proposer de nouvelles applications pour ces concepts. Il pourra également rééchir à certaines généralisations, ou tenter de répondre à certaines questions en suspens, telle que la complexité de la construction d'un graphe traçable.

Références
[1] R. M. Jungers and V. D. Blondel. Observable graphs. Submitted, 2007.
[2] V. Crespi, G. V. Cybenko, and G. Jiang. The theory of trackability with applications to sensor networks. To appear in ACM Transactions on Sensor Networks, 2008.
Alan Turing et le chaos
Encadrement: Vincent Blondel avec Jean-Charles Delvenne

Voici septante ans, Alan Turing inventait la théorie de l'ordinateur et des algorithmes. Son message fondamental était révolutionnaire: le comportement à long terme d'un algorithme est impossible à prédire (on dit: indécidable).

Dans les années septante, on découvrit partout dans la nature le chaos: des systèmes très simples à quelques variables dont toutes les trajectoires sont instables. C'est l'effet papillon: un battement d'aile ici s'amplifie et dégénère en une tempête là-bas. Il est donc impossible de prédire le comportement à long terme d'un système chaotique. Les esprits hardis se sont donc mis à rêver: Et si le chaos et l'indécidabilité étaient la même chose? Ou du moins, se rejoignaient? Aujourd'hui la question n'est pas encore tranchée faute, notamment, de définition précise des termes.

L'objet du mémoire consiste à se faire une opinion sur le sujet et la défendre, par une clarification des termes ou la démonstration de nouveaux liens entre ces concepts dans des cas particuliers. Ce mémoire requiert un goût prononcé pour les mathématiques.
La thermodynamique des gens
Encadrement: Vincent Blondel avec Jean-Charles Delvenne

La physique est surprenante, ces temps-ci. On la pensait cantonnée à l'étude des systèmes simples et inertes, comme deux planètes, voire un gaz parfait. Voilà qu'elle se mêle de comprendre le vivant, à toutes les échelles. Prenons un graphe social: les noeuds sont des gens, et les arêtes indiquent les liens de connaissance (défini, par exemple, par les coups de téléphone: voilà quelque chose de bien mesurable). On pourrait aussi  prendre le graphe des pages web, avec les hyperliens comme arêtes. On peut transformer ce graphe en un système physique: les soubresauts d'une particule fictive qui se déplace au hasard de noeud en noeud du graphe ressemblent étonnament à des fluctuations thermiques. On applique alors quelques concepts simples chers au coeur des physiciens - énergie, entropie ou transformée de Fourier - pour analyser les propriétés du graphe social, par exemple: Quelles sont les pages les plus populaires ? Existe-t-il des communautés de gens qui sont peu intégrées au reste de la société?

Les mêmes questions, avec un sens différents, peuvent être posées pour d'autres types de graphes, par exemple les atomes d'une protéine: Quels sont les atomes les plus mobiles de la molécule? etc.

Ainsi apparaissent de nouveaux algorithmes pour analyser les grands graphes. Leur science est balbutiante. Le but du mémoire sera d'étudier les méthodes de la physique pour l'étude des graphes sociaux et biologiques. Selon les goûts, il prendra une tournure théorique ou numérique.

Similarité dans les graphes. Application à l'extraction de motifs biologiques
Encadrement: Vincent Blondel, 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).