Implémentation et évaluation d'un algorithme rapide de recherche ...

Description

Implémentation et évaluation d'un algorithme rapide de recherche ...

Sujets

• Arts

Informations

• Publié par: alurenum
• Nombre de lectures: 182
• Langue: Français

Extrait

Projet de Master

file:///users/toulouse/boulot/enseignement/cgp/2008/projet/ev-projet-res...

Implémentation et évaluation d'un algorithme rapide de recherche de communautés dans des grands réseaux sociaux

Contexte Un réseaux social est un graphe dont les noeuds sont des individus ou organisations, connectés par des liens représentant une relation ``sociale'': appartenance à la même famille, échange de messages, goûts communs ... L'étude des réseaux sociaux est très active; elle intéresse depuis quelques décennies les chercheurs en sciences sociales et réuni depuis la fin des années 90 une importante communauté de chercheurs d'horizons divers, attirés tant par la découvertes d'intéressantes propriétés théoriques de ces structures que par la richesse des applications potentielles. Les applications Web 2.0 (Google Mail, MySpace, Facebook, ...) génèrent d'importants réseaux sociaux dont l'exploitation ne fait que débuter (applications au marketing par exemple). Un élément important dans l'analyse automatique des réseaux sociaux est la découverte de "communautés" d'utilisateurs. Une communauté est simplement un groupe de personnes (noeuds du réseau) fortement reliées. Objectif Le but du projet est d'implémenter et évaluer un (voire plusieurs) algorithmes de recherche de communautés dans de grands réseaux (jusqu'à quelques millions de noeuds). L'algorithme est décrit dans quelques articles scientifiques que vous devrez comprendre et mettre en oeuvre. Vous pourrez aussi étudier d'éventuelles implémentations déjà publiées sur le web.

Profil des étudiants

Ce projet plaira à des étudiants attirés par l'algorithmique et les démarches expérimentales, sachant lire l'anglais technique, et qui ne sont pas effrayés par les notations mathématiques (il ne s'agit pas de faire des maths, mais d'implémenter des méthodes parfois décrites en termes mathématiques...).

Contraintes techniques

L'algorithme de recherche de communautés sera codé en C ou C++. Il sera interfacé à un interpréteur du langage Python qui permetra de lancer les calculs et récupérer facilement les résultats: les entrées/sorties seront donc réalisées en Python, le code C ou C++ se contentera de réaliser les calculs.