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).