Détection de communautés dans les réseaux sociaux

Teven Le Scao, Dimitri Lozeve

Détection de communautés : le problème

Plan

  1. Visualisation d'une méthode : la méthode de Louvain
  2. Stochastic Block Model
  3. Le problème de la recommandation : Prestashop

Visualisation d'une méthode : la méthode de Louvain

Modularité

$$ Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(C_i, C_j) $$

Intérêts de la méthode de Louvain

dendrogram

Intérêts de la méthode de Louvain

$$ \mathcal{O}(n \log n) $$ vs $$ \mathcal{O}(n \log^2 n) $$ vs $$ \mathcal{O}(n^2) $$

Limitations de la modularité

Modularité

$$ Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(C_i, C_j) $$

Stochastic Block Model

Modèles de graphes aléatoires

Erdös-Rényi
Stochastic Block Model
Test standard pour les méthodes de clustering
$\longrightarrow$ Remise en cause
$$ \deg(x) = \sum_{j=1}^k X_j $$ où $\;\; X_j = \mathrm{Binom}\left(\left|B_j\right|, P_{ij}\right) $
youtubedegree

Le problème de la recommandation : Prestashop

users
degreeusers

Validation croisée

  1. Masquer une partie des arêtes
  2. Appliquer une méthode de clustering sur le réseau "train"
  3. Mesurer la proportion d'arêtes "test" dont les deux extrémités sont à l'intérieur d'un cluster

Graphe des blocs