Communautés dynamiques, diffusion et détection d'événements – CODDDE

Les graphes de terrain sont des réseaux d’interaction qui apparaissent dans de nombreux contextes du monde réel : en sociologie (réseaux d’amitié ou de collaboration),… ; en informatique (Internet, Web, réseaux de blogs, réseaux P2P),… ; en biologie (chaînes alimentaires, réseaux métaboliques, réseaux neuronaux),… ; dans le domaine de l’énergie et des transports (réseaux électriques, ferroviaires, aériens),… ; en économie, en linguistique et dans de nombreux autres domaines.

Le domaine émergent et prometteur de l’étude des graphes de terrain, et en particulier des réseaux sociaux, a donné lieu à un courant de travaux visant à identifier les propriétés de ces graphes, de décrire leur évolution et d’intégrer ces observations dans des modèles pertinents.
Ces propriétés sont utilisées comme paramètres clés pour l’étude de différents phénomènes tels que la robustesse, la diffusion d’information, d’opinions ou de virus. Ces questions sont très transversales puisque les phénomènes de diffusion peuvent se produire sur de nombreux types de réseaux sous la forme de maladies, d’idées, d’innovations, d’information ou de rumeurs.

Que l’on s’intéresse à l’évolution des graphes de terrain ou aux phénomènes de diffusion sur ces réseaux, on ne peut pas s’attendre à ce que cette dynamique soit uniforme, mais plutôt constituée d’une évolution de fond ponctuée d’événements marquants. Ces événements marquants peuvent correspondre à une activité anormale sur le réseau ; par exemple, les réseaux téléphoniques sont saturés le soir du Nouvel An, les réseaux de blogs réagissent parfois de manière inattendue à des événements particuliers (à certaines occasions, jusqu’à un pour cent de tous les blogs évoquent simultanément un même sujet). Les événements peuvent également être liés à des modifications soudaines de la topologie du réseau, par exemple une mise à jour des tables de routage consécutive à une panne. Etre capable de prédire de tels événements sur ces réseaux est un enjeu particulièrement stratégique.

Le projet CODDDE a pour objectif d’étudier les trois questions de recherche suivantes :
- Comment les graphes de terrain évoluent-ils au fil du temps ?
- Comment peut-on décrire, modéliser, voire prédire les phénomènes de diffusion qui s’y produisent ?
- Comment peut-on détecter et prévoir l’apparition d’événements exceptionnels dans ces graphes de terrain, en particulier les changements inattendus de structure ?
Afin de répondre à ces questions, une propriété essentielle des graphes de terrain sera exploitée : l’existence d’une structure communautaire dans ces réseaux. Les graphes de terrain sont en effet constitués de groupes de sommets fortement liés, ces groupes sont par contre peu connectés entre eux.

Le projet CODDDE proposera donc de nouveaux algorithmes de détection de communautés reflétant l’évolution des graphes de terrain. La connaissance de cette structure en communautés dynamiques permettra de mieux comprendre les phénomènes de diffusion et les événements inattendus qui se produisent dans ces réseaux.

La méthodologie et les algorithmes développés seront appliqués et validés sur un réseau social réel constitué de plus de 10000 blogs et media francophones, enregistrés quotidiennement depuis 2009 (comprenant tous les articles publiés et les liens entre ces articles) ainsi que des messages publiés sur twitter.

Afin d’atteindre ces objectifs au cours des 36 mois du projet, le consortium est constitué :
- de deux partenaires académiques ayant une grande expérience dans l’étude des graphes de terrain : l’équipe Complex Networks du LIP6-UPMC (Laboratoire d’Informatique de Paris 6 de l’Université Pierre et Marie Curie), et l’équipe LIP-ENS Lyon (Laboratoire d’Informatique du Parallélisme de l’École Normale Supérieure de Lyon),
- d’un partenaire industriel : la PME linkfluence, qui sera responsable de la collecte des données. De plus, l’expertise des analystes de linkfluence sera mise à profit pour la validation des résultats.