Master 2013 2014
psar
Etudes sur la dissémination d’information dans les réseaux sociaux


Site :Equipe Regal
Lieu :LIP6
Encadrant : Pierre Sens, Ruijing Hu,
Dates :31/01/2014 au 12/05/2014


Description

Nombre d’étudiants : 1 ou 2

Contexte :

Le but de ce projet est d’étudier les performances d’un algorithme pour la dissémination d’information lorsque celui-ci est déployé sur des réseaux présentant des caractéristiques structurelles variées.

Mots-clés : dissémination d’information, graphes, Internet, réseaux sociaux, clustering.

Présentation :

La dissémination d’information de type broadcast, dans laquelle un nœud du réseau tente de transmettre une information à tous les autres nœuds, est une problématique essentielle pour beaucoup d’applications réparties. La performance de ce protocole dépend bien sûr de la structure du réseau sur lequel il est déployé. Le but du projet est de comprendre comment la densité locale des réseaux influe sur l’efficacité de cet algorithme. Pour ce faire, nous proposons de calculer différentes métriques liées à la performance des protocoles de diffusions (comme la latence ou la complexité en message) lorsque ceux-ci sont déployés sur des réseaux présentant des structures différentes (par exemple un sous-ensemble du réseau Internet ou d’un réseau social issu de Flickr). On se concentrera en particulier sur la densité locale, propriété capturée généralement par la notion de clustering.

Déroulement :

Dans un premier temps, l’étudiant se familiarisera avec une bibliothèque C permettant la représentation de grands graphes. Ceci permettra l’analyse de la structure de différents réseaux (Internet, Flickr) à travers le calcul d’un ensemble de caractéristiques statistiques liées à la topologie, en particulier la distribution des degrés et le coefficient de clustering. Dans un second temps, l’étudiant calculera les performances de l’algorithme de diffusion de type flooding sur ces réseaux. On pourra par exemple calculer la latence et la complexité de messages observées en moyenne lorsqu’une source tente de propager une information à l’ensemble des nœuds du réseau.

Pré-requis : bon niveau en C et en algorithmique sur les graphes.