Approches de détection de communautés

D´etection de communaut´es dans les grands graphes de
terrain
Rushed Kanawati
LIPN, CNRS UMR 7030
Universit´
e Paris Sorbonne Cit´
e
http://lipn.fr/∼kanawati
[email protected]
February 4, 2014
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
1 / 52
Plan
1
Probl´
ematique
2
Identification de communauat´
es
3
Partitionnement de graphe
4
Evaluation de communaut´
es
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
2 / 52
Probl´
ematique
Communaut´e ?
D´efinition
Un sous-graphe dense faiblement li´e au reste du graphe.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
3 / 52
Probl´
ematique
Communaut´e ?
Definition
Un sous-graphe dense faiblement li´e au reste du graphe.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
4 / 52
Probl´
ematique
Int´erˆets
v R´eseaux sociaux : identification de groupes d’amis
v Web : ensemble de pages web traitant un mˆeme th`eme,
v R´eseaux biologiques : un ensemble de g`enes d´edi´es `a une mˆeme
fonction,
v etc.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
5 / 52
Probl´
ematique
Application
v Parall´elisation
v Visualisation
v Compression
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
6 / 52
Probl´
ematique
Probl`emes
v Identification de communaut´
e : d´elimiter la communaut´e d’un
nœud.
v Partitionnement du graphe en N sous-graphes (communaut´es non
chevauchantes).
v Detection de communaut´
es (potentiellement chevauchantes)
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
7 / 52
Identification de communaut´
es
Identification de communaut´es
Exemple : communaut´e ´ego-centr´ee (LinkedIn)
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
8 / 52
Identification de communaut´
es
Identification de communaut´es : approche g´en´erale
Contraintes
Vision partielle du graphe centr´e sur le nœud cible.
V =D ⊕S ⊕U
D : Ensemble de nœuds explor´es
S : Ensemble de nœuds
partiellement explor´es.
U : Ensemble de nœuds
non-explor´es
D =C ⊕B
C : Ensemble de nœuds dont tous
les voisins sont aussi dans D
B : Ensemble de nœuds de D qui
ont au moins un voisin dans S
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
9 / 52
Identification de communaut´
es
Identification de communaut´es : approche g´en´erale
1 C ← {n0 }, S ← Γ(n0 )
2 Q ← 0 /* Une fonction de qualit´e /
3 Tant que on peut am´eliorer Q faire
1
2
3
4
n ← argmaxn∈S Q
S ← S − {n}
D ← D + {n}
Mettre `a jour B, S, C
4 Retourner D : la communaut´e de n0
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
10 / 52
Identification de communaut´
es
Fonction de qualit´e : exemples I
La modularit´e locale R
Bin
Bin +Bout
R=
La modularit´e locale M
M=
Din
Dout
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
11 / 52
Identification de communaut´
es
Fonction de qualit´e : exemples II
La modularit´e locale L
L=
Lin
Lex
o`
u:
P
Lin =
kΓ(i)∩Dk
i∈D
kDk
P
Lex =
kΓ(i)∩Sk
i∈B
kBk
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
12 / 52
Partitionnement de graphe
Partitionnement de graphe
D´efinition
P = {P1 , . . . , Pn }, ∩i:1→n Pi = φ , ∪i:1→n Pi = V
2n partitions diff´erentes !
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
13 / 52
Partitionnement de graphe
Approches
v Approches centr´ees groupes o`
u des nœuds sont regroup´es en
communaut´es en fonction de propri´et´es topologiques partag´ees.
v Approches centr´ees r´eseau o`
u la structure globale du r´eseau est
examin´ee pour la d´ecomposition du graphe en communaut´es.
v Approches centr´ees propagation qui appliquent souvent une proc´edure
d’´emergence de la structure communautaire par ´echange de messages
entre nœuds voisins.
v Approches centr´ees graines o`
u la structure communautaire est
construite autour d’un ensemble de nœuds choisis d’une mani`ere
inform´ee.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
14 / 52
Partitionnement de graphe
Approches centr´ees groupes
v Recherche de groupes denses :
v Cliques maximales
v γ-dense quasi clique.
v K-core : sous-graphe connexe maximal dans lequel le degr´e de
chaque nœud est sup´erieur ou ´egale `a k
v ...
v Ad´equat pour graphes denses
v Souvent NP-Complet.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
15 / 52
Partitionnement de graphe
Approches centr´ees R´eseau
v Algorithme de clustering
v Approches d’optimisation
v Approches bas´ees sur la propagation locale
v Approches centr´ees graine
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
16 / 52
Partitionnement de graphe
Approche de clustering : Classification hi´erarchique
Chaque sommet = communaut´e.
On it`ere jusqu’au avoir une seule communaut´e :
Calcule les distances entre chaque 2 communaut´es
Fusionner les deux communaut´es les plus proches
On obtient un dendrogramme de communaut´es.
Distance entre communaut´es : La distance minimale, maximale, ou
moyenne entre deux sommets des 2 communaut´es. Distance entre
barycentres des communaut´e.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
17 / 52
Partitionnement de graphe
Approches d’optimisation
v D´efinition d’une fonction de qualit´e de partition
v Application d’approches d’optimisation.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
18 / 52
Partitionnement de graphe
Fonction de qualit´e : La modularit´e
La modularit´e
Q(P) =
di dj
1 XX
)
(Aij −
2m
2m
(1)
c∈P i,j∈c
Figure: Exemple de calcul de la modularit´e : Q =
R. Kanawati (LIPN)
D´
etection de communaut´
es
(15+6)−(11.25+2.56)
25
= 0.275
February 4, 2014
19 / 52
Partitionnement de graphe
Optimisation : Algorithmique g´en´etique
Une population de solutions : chaque individu est repr´esent´e par une
s´equence de g`enes
Evolution de la population par m´ecanismes de : croisement,
mutation et s´
election naturelle.
G`ene : vecteur d’affectation de communaut´e aux sommets.
M´ecanismes de s´election : Modularit´e.
Int´erˆet : Parrall´elisation facile.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
20 / 52
Partitionnement de graphe
Approches s´eparatives
igraph.Graph.community edge betweenness
Principe : A chaque it´eration retirer un lien inter-communuat´e
Diff´erents crit`eres pour identifier un lien inter-communaut´e
Algo. de Girvan et Newman :la centralit´e d’interm´ediarit´e.
Complexit´e O(m2 n).
Algo. de Fortunato : centralit´e d’information. L’efficacit´e d’un
graph E est donn´e par la moyenne de d1ij , La centralit´e d’une
arˆete (i, j) est donn´e par la diminution de E en retirant ce lien.
Complexit´e O(m3 n).
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
21 / 52
Partitionnement de graphe
Approche Agglom´erative I
igraph.community multilevel
Chaque nœud est associ´e `a une communaut´e
R´ep´eter jusqu’`a stabilisation :
pour chaque nœud i ´evaluer le gain de modularit´e ∆Q si i rejoint la
communaut´
voisin j P
P e d’un noœud
P
P
+2k
+ki 2
ki 2
in
tot 2
∆Q = ( in 2m i,in − ( tot
)
)
−
(
−
(
2m
2m
2m ) − ( 2m ) )
P
est la somme des poids des liens dans la communaut´e cible,
Pin
tot est la somme des liens adjacents aux nœuds de la
communaut´e cible,
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
22 / 52
Partitionnement de graphe
Approche Agglom´erative II
ki,in est la somme des poids des liens reliant i `a des nœuds de la
communaut´e cible.
(suite R´ep´eter jusqu’`a stabilisation)
i est ajout´e ´a la communaut´e qui maximise le gain si ce gain est positif.
Remplacer le graphe actuel par le graphe de connexion de
communaut´es calcul´e comme suit :
Les nœuds sont les communaut´es
Le poids d’un lien (u, v ) est la somme des poids des liens reliant
tous les nœuds de u aux nœuds de v
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
23 / 52
Partitionnement de graphe
Approche Agglom´erative III
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
24 / 52
Partitionnement de graphe
Approche de propagation d’´etiquettes
igraph.community label propagation
1 Chaque nœud est attribu´e une ´etiquette unique.
2 Chaque nœud propage son ´etiquette `a ses voisins.
3 A r´eception, chaque nœud adopte l’´etiquette majoritaire.
4 En cas de conflit, un nœud choisit une ´etiquette al´eatoirement.
5 Deux approches : Propagation synchrone et propagation asynchrone.
Probl`eme :
Stabilit´e des partitions retrouv´ees.
Solution : calcul de cœurs de communaut´es
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
25 / 52
Partitionnement de graphe
Cœurs de communaut´es I
v Etant donn´e N partitions d’un graphe G de n nœuds
v Calculer la matrice n × n de consensus C = cij o`
u cij est la fr´equence
de co-occurrence des nœuds i; j dans une mˆeme communaut´e.
v C est la matrice d’adjacence du graphe de consensus.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
26 / 52
Partitionnement de graphe
Cœurs de communaut´es II
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
27 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary I
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
28 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary II
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
29 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary III
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
30 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary IV
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
31 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary V
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
32 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary VI
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
33 / 52
Partitionnement de graphe
Cœurs de communaut´es
v Etant donn´e un seuil α ∈ [0, 1]
v Retirer du graphe de consensus les liens dont le poids ≤ α
v Les composantes connexes du graphe r´esultat sont les cœurs de
communaut´
es
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
34 / 52
Partitionnement de graphe
Exemple : Club de Karat´e de Zachary
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
35 / 52
Partitionnement de graphe
L’algorithme LICOD
1 D´eterminer l’ensemble des Leaders L
2 R´ep´eter jusqu’au stabilisation ou max fois :
Chaque x ∈ V trie les communaut´es c ∈ C dans un ordre
d´ecroissant selon le degr´e d’appartenance Px0
Pour chaque x ∈ V , calculer
Pxt = FusionVotes(Pyt−1 y ∈ {X } ∪ Γ(x))
Recalculer L
3 Retourner pour chaque nœud la communaut´e plac´ee en tˆete de
vecteur de pr´ef´erence.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
36 / 52
Partitionnement de graphe
LICOD: Identification de Leaders
Pour chaque x ∈ V , calculer les propri´et´es suivantes prop(x):
Propri´et´e locale: centralit´e de degr´e
Propri´et´es globales: centralit´e de proximit´e, centralit´e de
d’interm´ediarit´e (?)
Autre: PageRank
Soit Fx = {y ∈ Γ(x) : prop(x) > prop(y )}
x est un Leader si
R. Kanawati (LIPN)
|Fx |
|Γ(x)|
> σ ∈ [0, 1]
D´
etection de communaut´
es
February 4, 2014
37 / 52
Partitionnement de graphe
LICOD: Degr´e d’appartenance
Le degr´e d’appartenance d’un nœud v `a une communaut´e c est donn´ee
par l’inverse du plus court chemin SP liant v `a un des leaders de c:
1
appartenance(v , c) = (min
SP(v ,x))+1
x∈COM(c)
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
38 / 52
Partitionnement de graphe
LICOD: Fusion des votes
Application des m´ethode de votes:
M´ethodes de condercet non-consistantes: Majority, Borda
M´ethodes de condercet consistantes: Kemeny, local Kemeny
Exemple:
A>B>C >D
A>B>C >D
B>C >A>D
D>A>B>C
B>D>A>C
Borda → B > A > D > C > E
Kemeny → A > B > C > D > E
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
39 / 52
Evaluation de communaut´
es
Evaluation des algorithmes de d´etection de communaut´es
3 grandes approches :
Qualit´es structurelles des communaut´es retrouv´ees.
Comparaison avec une v´erit´e de terrain.
Evaluation orient´es tˆaches
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
40 / 52
Evaluation de communaut´
es
Fonctions d’´evaluation structurelle
La qualit´e de C = {S1 , . . . , Si } est donn´ee par :
P
f (Si )
i
Q(C) =
|C|
(2)
f () est une fonction de qualit´e d’une communaut´e.
4 familles de fonctions de scoring :
Fonctions bas´ees sur la connectivit´e interne.
Fonctions bas´ees sur la connectivit´e externe.
Fonctions hybrides
Fonctions inform´ees par des mod`eles.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
41 / 52
Evaluation de communaut´
es
Fonctions d’´evaluation de la connectivit´e interne
2×mS
nS ×(nS −1)
2×mS
nS
Densit´e interne : f (S) =
Degr´es moyen : f (S) =
FOMD: Fraction over Median Degree : f (s) =
dm est le m´edian de degr´es des nœuds dans V
TPR: Triangle Participation Ratio :
R. Kanawati (LIPN)
|{u:u∈S,|(u,v ),v ∈S|>dm }|
,
nS
|{u∈S}:∃v ,w ∈S:(u,v ),(w ,v ),(u,w )∈E |
nS
D´
etection de communaut´
es
February 4, 2014
42 / 52
Evaluation de communaut´
es
Fonctions d’´evaluation de la connectivit´e externe
Expansion : f (S) =
Cut : f (S) =
R. Kanawati (LIPN)
CS
nS
Cs
nS ×(N−nS )
D´
etection de communaut´
es
February 4, 2014
43 / 52
Evaluation de communaut´
es
Fonctions hybrides
Conductance : f (S) =
CS
2mS +CS
,v 6∈S}|
MAX-ODF : Out Degree Fraction : f (S) = maxu∈S |{(u,v )∈E
d(u)
P |{(u,v )∈E ,v 6∈S}|
AVG-ODF : f (S) = n1S ×
d(u)
u∈S
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
44 / 52
Evaluation de communaut´
es
Fonctions guid´ees par un mod`ele
La modularit´e : f (s) = 14 (mS − E (mS ))
E (mS ) le nombre attendu de liens dans un graphe al´eatoire ayant la
mˆeme distribution de degr´es.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
45 / 52
Evaluation de communaut´
es
Comparaison avec une v´eriti´e de terrain
Principe : calculer une similarit´e (ou distance) entre une partition
calcul´ee et une partition de r´ef´erence.
La partition de r´ef´erence peur ˆetre :
annot´ee par un expert
ou g´en´er´ee par un mod`ele.
Deux types de mesures :
Mesures bas´ees sur le compte des accords.
Mesures bas´ees sur la th´eorie de l’information.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
46 / 52
Evaluation de communaut´
es
Mesures bas´ees sur le comptes des accords
Soient U, V deux partitions d’un graphe G
Indice de Rand :
a pairs plac´es dans une mˆeme communaut´e selon U et V
b pairs plac´es en mˆeme communaut´e selon U et en diff´erents
communaut´e selon V
c pairs plac´es en mˆeme communaut´e selon V et en diff´erents
communaut´e selon V
d pairs plac´ees en diff´erentes communaut´e selon U et selon V.
a+d
rand = a+b+c+d
2
ARI = Cn(C(a+d)−[(a+b)(a+c)+(c+d)(b+d)]
2 2
n ) −[(a+b)(a+c)+(c+d)(b+d)]
E(ARI)=0
n!
rappel : Cnk = k!(n−k)!
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
47 / 52
Evaluation de communaut´
es
L’information mutuelle
Rappel : L’information mutuelle entre deux variables al´eatoires X , Y
est : I (X , Y ) = H(X ) + H(Y ) − H(X , Y )
P x
H(X ) = ni=1
p(xi ) × log ( p(x1 i ) )
Normalisation : NMI (U, V ) = √ I (U,V )
H(U)H(V )
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
48 / 52
Evaluation de communaut´
es
Probl`eme de v´erit´e de terrain
Existence de quelques graphes de benchmark (Zachary, Football, . . . ,
etc.),
Graphe de tr`es petits tailles.
Difficile de trouver de grands graphes avec v´erit´e de terrain.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
49 / 52
Evaluation de communaut´
es
Benchmarks artificiels : Le mod`ele LFR
But : G´en´eration d’un graphe compos´e d’un ensemble de k
communaut´es plus au moins interconnect´es entre elles.
Algorithme :
Soit N le nombre de nœuds du graphe `a g´en´erer. La distribution
de degr´es est tir´ee selon une loi de puissance de param`etre γ tel
que le degr´es d’un nœud est dans un intervalle [Kmin , Kmax ].
µ est un param`etre de connexion entre communaut´e : µ ∈ [0, 1]
La distribution des tailles de communaut´es suit une autre lois de
puissance de param`etre β.
Par it´eration : assigner un nœud `a une communaut´e
al´eatoirement choisi de sorte que la taille de la communaut´e soit
sup´erieur au degr´
es interne du nœud.
Si la communaut´e ´elue est complet on exclue un de ses membres
choisi d’une mani`ere al´eatoire. Le nœud exclu devint un nœud
non assign´e.
L’algorithme s’arrˆete lorsque tous les nœuds sont assign´es `a des
R. Kanawati
(LIPN)
D´
etection de communaut´
es
February 4, 2014
50 / 52
communaut´
es.
Evaluation de communaut´
es
TP 3
1 G´en´erer le graphe de club de Karat´e de Zachary :
ig.Graph.Famous("zachary")
2 Calculer les communaut´es locales des nœuds 0 et 33 en utilisant les
diff´erentes mesures de modularit´e locales R, M et L.
3 Comparer les communaut´es avec celles trouv´ees avec l’algorithme de
Girvan-Newman : community edge betweenness
(Question bonus) : Proposer une m´ethode de combinaison de trois
modularit´e locales.
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
51 / 52
Evaluation de communaut´
es
TP4
1 Tester les algorithmes de d´etection de communaut´e : Louvai,
edge-betweeness et label propagation sur les deux r´eseaux : Zachary,
football. Comparer les r´esultats.
2 Implementer l’algorithme de calcul de c:oe ur de communaut´es et
comparer le r´esultat obtenu sur football en utilisant label propagation
avec celui obtenu par louvain.
3 Implementer l’algorithme Licod
R. Kanawati (LIPN)
D´
etection de communaut´
es
February 4, 2014
52 / 52

Download Report