mardi 16 avril 2013

Compte Rendu MARAMMI 2012


Ci-après quelques notes prises sur les différents présentations lors de la conférence MARAMI 2012.


Réseaux dynamiques : de l’analyse à la modélisation
Au début de la journée Alain Barrat parlait sur les réseaux dynamiques qui sont un type de réseaux dont les arcs entre nœuds change dynamiques (ex. sont créé et détruit dynamiquement dans le temps). L’utilisation de ces graphes a été dans le cadre d’une étude des interactions physiques (ex. durée de l’interaction) entre plusieurs personnes dans différentes contexte (ex. hôpital, musée, conférence). Pour capturer des informations sur personnes qui étaient en interaction, un dispositif particulier a été utilisé (aussi il est breveté !). Les capteurs sont en forme de badges à base de RFID afin de détecter le badge de l’autre personne en face, ils disposaient d’émetteur radio pour remonter à chaque intervalle (ex. 20s) les identifiants des badges de personne en face. Une fois les infos agrégés, ils sont analysés pour mesurer la durée des interactions.
Les applications peuvent être par exemple détection d’étudiant d’une même classe.
Plus d’information sur http://www.sociopatterns.org/

En pause, j’ai parlait avec un doctorant qui bossait sur les réseaux sociaux, ils avaient un graphe de Twitter (>20M de nœuds et >1G d’arcs) l’étude est basique en terme d’opération sur les graphes mais la difficulté réside dans la gestion des données (sauvegarde sur une base + parcours). Apparemment, la base graphe par excellence Neo4j (que j’ai utilisé pour l’intégration avec l’ASE) ne peut supporter de tels volumes, du coup ils ont optés pour une base plus performantes Dex Graph DB.

Triclustering pour la détection de structures temporelles dans les graphes
Un thésard d’Orange Labs présentait une méthode clustering basé sur la transformation (synthétisation) de graphes à un graphe image (après regroupement de nœuds).
Dans l’état de l’art, il a présenté la technique de base appelée « Blockmodeling » qui consiste à représenter le graphe en matrice ensuite réorganiser les lignes/colonnes pour faire apparaître des blocs représentant les nœuds à regrouper.
L’expérimentation a été menée sur des stations vélib de Londres, ou différentes stations ont été regroupées selon leur profil (i.e. débit de vélo sortant).

Supervised rank aggregation approach for link prediction in complex networks
Le but de l’étude est de prédire des liens entre nœuds, ce qui peut être utilisé dans des la recommandation.
La présentation était théorique car s’agit d’une proposition d’algo.

Détection de communauté dans les réseaux de téléphonie mobile
Vincent Blondel (UCL) présentait la méthode de Louvain qui l’a développé pour le partitionnement (clustering) de graphe. Cette méthode est devenue très utilisée dans la détection de communauté dans un graphe (ex. LinkedIn InMaps). Elle est implémentée par plusieurs outils (ex. Gephi).
Méthode de Louvain
La méthode construit des communautés en bottom-up, i.e. commence par les nœuds en les considérant tous des communautés ensuite regroupe les nœuds adjacents de façon à améliorer une mesure de modularité du graphe. Cette est répétée jusqu’à ne plus pouvoir améliorer le score de modularité.
A ce niveau les communautés créées sont replacé par des super-nœuds pour créer un graphe de niveau supérieur sur lequel la procédure précédente est répétée.
Ainsi la méthode permet la création de communauté hiérarchique (i.e. l’utilisateur à la possibilité de zoomer sur le graphe !).
Après présentation de la méthode, il a présenté des études ou la méthode a été appliquée :
·         Analyse de réseau de criminalité en Belgique (les nœuds représentent des criminels, un arc entre deux nœuds signifies que les deux criminels sont impliqués dans un même faits), le graphe a été construit par des données sur 5 ans.
·         Analyse d’appels téléphoniques mobile de Belgique (MOBISTAR) sur 6 mois.
·         Analyse d’appels téléphoniques mobile de France è les communautés crées permettaient sont au niveau des régions (au lieu des départements).
Il parlait aussi de challenge proposé par Nokia Research et Orange (D4D : Data for Developpment) qui offrait aux chercheurs des données d’utilisation de mobile principalement en Afrique (ex. côte d’ivoire) si le projet correspondaient aux besoins marketing de l’entreprise.

Détection de communautés chevauchantes dans les graphes bipartis
La présentation portait sur les graphes bipartis où on a deux groupes de nœuds et un nœud ne peut avoir d’arc qu’avec les nœuds d’un autre groupe. L’exemple d’étude porté sur les photos de mariage. L’approche à pour but de détecter des partitions recouvertes.

Une nouvelle mesure pour l’évaluation des méthodes de détection de communauté
L’étude propose une nouvelle mesure d’évaluation de communauté meilleure que celle généralement utilisée « pureté de partition ». Le problème de celle-ci c’est qu’elle affecte potentiellement le même score pour deux partitions bien que sur l’une un nœud important pour la communauté a été mal classé.
La mesure proposée prend en compte l’importance topologique des nœuds qui représente le nombre d’arc sortant d’un nœud, la pureté nodale est égale à 1 pour un nœud bien classé et 0 pour un nœud mal classé.
Pour évaluation de l’approche, l’auteur prenait plusieurs algorithmes de clustering avec utilisation des deux mesures. Le résultat montrait que l’approche pénalise le partitionnement qui classe mal un nœud important (au centre) au profit de nœud moins important au bord de la partition.

Détection de communautés dans des réseaux scientifiques à partir de données relationnelles
L’étude portée sur les graphes dont les nœuds peuvent avoir des attributs, dans ce cas il s’agit de graphes sur la participation de chercheurs à deux conférences ayant deux sessions.

Caractérisation de la structure communautaire d’un grand réseau social
Les auteurs montrent que la plupart des algorithmes de partitionnement (y compris celui de Louvain) donnent de mauvais résultat (des fausses communautés) pour certain type de graphes (ex. graphe grille) à cause de la mesure qui est utilisé pour mesurer la qualité d’un partitionnement.
Pour montrer cela, leur étude portait sur les cœurs de communautés qui sont obtenu en appliquant plusieurs fois (~100 fois) un algorithme de partitionnement, ensuite renforcer (proportionnellement au nombre de co-apparition) les liens entre les nœuds qui apparaissent dans la même communauté souvent.

Apprentissage et ciblage publicitaire
Une personne de Numsight venait présenter l’eco-système de publicité dans le web qui est composé des sites web, des AD server, des marchés des AD. Ainsi que leur approche qui est basé sur l’analyse des sites web afin de les tagger en catégories (ex. mode, sport) et sous-catégorie (ex. club, foot). Aussi, l’approche est basée sur le profiling des utilisateurs en agrégeant plusieurs informations (ex. site web consultés, mot clé utilisé dans des moteurs de recherche donnée par google !) afin de déterminer le projet de l’utilisateur (ex. achat de voiture ou réparation, voyage touristiques ou affaire).

Wolfram Mathematica
Après une personne de wolfram donnait un tutoriel sur l’utilisation de leur produit mathematica !

Here is a link to the conference presentations.

Aucun commentaire:

Enregistrer un commentaire