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.
