Détection de communautés dans les grands graphes de
terrain
Rushed Kanawati
LIPN, CNRS UMR 7030
Université Paris Sorbonne Cité
http://lipn.fr/∼kanawati
[email protected] October 31, 2016
R. Kanawati (LIPN) Détection de communautés October 31, 2016 1 / 69
Plan
1 Problématique
2 Identification de communautés
3 Partitionnement de graphe
4 Evaluation de communautés
R. Kanawati (LIPN) Détection de communautés October 31, 2016 2 / 69
Problématique
Communauté ?
Définition
Un sous-graphe dense faiblement lié au reste du graphe.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 3 / 69
Problématique
Communauté ?
Definition
Un sous-graphe dense faiblement lié au reste du graphe.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 4 / 69
Problématique
Intérêts
v Réseaux sociaux : identification de groupes d’amis
v Web : ensemble de pages web traitant un même thème,
v Réseaux biologiques : un ensemble de gènes dédiés à une même
fonction,
v etc.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 5 / 69
Problématique
Application
v Parallélisation
v Visualisation
v Compression
R. Kanawati (LIPN) Détection de communautés October 31, 2016 6 / 69
Problématique
Problèmes
v Identification de communauté : délimiter la communauté d’un
nœud.
v Partitionnement du graphe en N sous-graphes (communautés non
chevauchantes).
v Detection de communautés (potentiellement chevauchantes)
R. Kanawati (LIPN) Détection de communautés October 31, 2016 7 / 69
Identification de communautés
Identification de communautés
Exemple : communauté égo-centrée (LinkedIn)
R. Kanawati (LIPN) Détection de communautés October 31, 2016 8 / 69
Identification de communautés
Identification de communautés : approche générale
Contraintes
Vision partielle du graphe centré sur le nœud cible.
V =D ⊕S ⊕U
D : Ensemble de nœuds explorés
S : Ensemble de nœuds
partiellement explorés.
U : Ensemble de nœuds
non-explorés
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étection de communautés October 31, 2016 9 / 69
Identification de communautés
Identification de communautés : approche générale
1 C ← φ, B ← {n0 }, S ← Γ(n0 )
2 Q ← 0 /* Une fonction de qualité /
3 Tant que on peut améliorer Q faire
1 n ← argmaxn∈S Q
2 S ← S − {n}
3 D ← D + {n} /* D = C ∪ B*/
4 Mettre à jour B, S, C
4 Retourner D : la communauté de n0
R. Kanawati (LIPN) Détection de communautés October 31, 2016 10 / 69
Identification de communautés
Fonction de qualité : exemples I
La modularité locale R [Clauset05]
Bin
R= Bin +Bout
Bin =len(g.es.select( within=B))
Bout =len(g.es.select( between=(B,S)))
R. Kanawati (LIPN) Détection de communautés October 31, 2016 11 / 69
Identification de communautés
Fonction de qualité : exemples II
La modularité locale M
Din
M= Dout
Din =len(g.es.select( within=D))
Dout =len(g.es.select( between=(B,S)))
R. Kanawati (LIPN) Détection de communautés October 31, 2016 12 / 69
Identification de communautés
Fonction de qualité : exemples III
La modularité locale L
Lin
L= Lex où :
P
kΓ(i)∩Dk
i∈D
Lin = kDk
P
kΓ(i)∩Sk
i∈B
Lex = kBk
R. Kanawati (LIPN) Détection de communautés October 31, 2016 13 / 69
Partitionnement de graphe
Partitionnement de graphe
Définition
P = {P1 , . . . , Pn }, ∩i:1→n Pi = φ , ∪i:1→n Pi = V
Nombre de partitions : Nombre de Bell Bn = nk=1 Ckn Bn−1
P
R. Kanawati (LIPN) Détection de communautés October 31, 2016 14 / 69
Partitionnement de graphe
Approches
v Approches centrées groupes où des nœuds sont regroupés en
communautés en fonction de propriétés topologiques partagées.
v Approches centrées réseau où la structure globale du réseau est
examinée pour la décomposition du graphe en communautés.
v Approches centrées propagation qui appliquent souvent une procédure
d’émergence de la structure communautaire par échange de messages
entre nœuds voisins.
v Approches centrées graines où la structure communautaire est
construite autour d’un ensemble de nœuds choisis d’une manière
informée.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 15 / 69
Partitionnement de graphe
Approches centrées groupes
v Recherche de groupes denses :
v Cliques maximales
v γ-dense quasi clique.
v K-core : sous-graphe connexe maximal dans lequel le degré de
chaque nœud est supérieur ou égale à k
v ...
v Adéquat pour graphes denses
v Souvent NP-Complet.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 16 / 69
Partitionnement de graphe
Group-based approches
from Symeon Papadopoulos, Community Detection in Social Media, CERTH-ITI, 22 June 2011
R. Kanawati (LIPN) Détection de communautés October 31, 2016 17 / 69
Partitionnement de graphe
Example: Clique percolation
Suits fairly dense graph.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 18 / 69
Partitionnement de graphe
Approches centrées Réseau
v Algorithme de clustering
v Approches d’optimisation
v Approches basées sur la propagation locale
v Approches centrées graine
R. Kanawati (LIPN) Détection de communautés October 31, 2016 19 / 69
Partitionnement de graphe
Approche de clustering : Classification hiérarchique
Chaque sommet = communauté.
On itère jusqu’au avoir une seule communauté :
Calcule les distances entre chaque 2 communautés
Fusionner les deux communautés les plus proches
On obtient un dendrogramme de communautés.
Distance entre communautés : La distance minimale, maximale, ou
moyenne entre deux sommets des 2 communautés. Distance entre
barycentres des communautés.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 20 / 69
Partitionnement de graphe
Approches d’optimisation
v Définition d’une fonction de qualité de partition
v Application d’approches d’optimisation.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 21 / 69
Partitionnement de graphe
Fonction de qualité : La modularité
La modularité
1 XX di dj
Q(P) = (Aij − ) (1)
2m 2m
c∈P i,j∈c
(15+6)−(11.25+2.56)
Figure: Exemple de calcul de la modularité : Q = 25 = 0.275
R. Kanawati (LIPN) Détection de communautés October 31, 2016 22 / 69
Partitionnement de graphe
Optimisation : Algorithmique génétique
Une population de solutions : chaque individu est représenté par une
séquence de gènes
Evolution de la population par mécanismes de : croisement,
mutation et sélection naturelle.
Gène : vecteur d’affectation de communauté aux sommets.
Mécanismes de sélection : Modularité.
Intérêt : Parrallélisation facile.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 23 / 69
Partitionnement de graphe
Approches séparatives
igraph.Graph.community edge betweenness
Principe : A chaque itération retirer un lien inter-communuaté
Différents critères pour identifier un lien inter-communauté
Algo. de Girvan et Newman :la centralité d’intermédiarité.
Complexité O(m2 n).
Algo. de Fortunato : centralité d’information. L’efficacité d’un
graph E est donné par la moyenne de d1ij , La centralité d’une
arête (i, j) est donné par la diminution de E en retirant ce lien.
Complexité O(m3 n).
R. Kanawati (LIPN) Détection de communautés October 31, 2016 24 / 69
Partitionnement de graphe
Approche Agglomérative I
igraph.community multilevel
Chaque nœud est associé à une communauté
Répéter jusqu’à stabilisation :
pour chaque nœud i évaluer le gain de modularité ∆Q si i rejoint la
communauté
P
d’un noœud
P
voisin j P P
in +2ki,in tot +ki 2 ki 2
∆Q = ( 2m − ( 2m ) ) − ( 2min − ( 2mtot )2 − ( 2m ) )
P
in est la somme des poids des liens dans la communauté cible,
R. Kanawati (LIPN) Détection de communautés October 31, 2016 25 / 69
Partitionnement de graphe
Approche Agglomérative II
P
tot est la somme des liens adjacents aux nœuds de la
communauté cible,
ki,in est la somme des poids des liens reliant i à des nœuds de la
communauté cible.
(suite Répéter jusqu’à stabilisation)
i est ajouté á la communauté qui maximise le gain si ce gain est positif.
Remplacer le graphe actuel par le graphe de connexion de
communautés calculé comme suit :
Les nœuds sont les communautés
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étection de communautés October 31, 2016 26 / 69
Partitionnement de graphe
Approche Agglomérative III
R. Kanawati (LIPN) Détection de communautés October 31, 2016 27 / 69
Partitionnement de graphe
Optimisation de la modularité: Limites
Hypothèses
La meilleure partition est celle qui maximise la modularité
Si un graphe a une structure communautaire alors il est possible de
trouver une partition precise qui avec une modularité maximales.
Les partitions ayant des modularités élevées sont similaires entre elles.
Les trois hypothèses sont fausses [GdMC10, LF11].
R. Kanawati (LIPN) Détection de communautés October 31, 2016 28 / 69
Partitionnement de graphe
Modularité: limite de la résolution
m = R.3 Kanawati
: Max(LIPN)
Q = 0.675 tandisDétection
que la modularité de la partition
de communautés naturelle
October 31, 2016 29 / 69
Partitionnement de graphe
Distribution de la modularité
R. Kanawati (LIPN) Détection de communautés October 31, 2016 30 / 69
Partitionnement de graphe
Approches de propagation
Algorithm 1 Label propagation
Require: G =< V , E > a connected graph,
1: Initialize each node with unique label lv
2: while Labels are not stable do
3: for v ∈ V do
lv = arg max |Γl (v )| /* random tie-breaking */
l
4: end for
5: end while
6: return communities from labels
Γl (v ) : set of neighbors having label l
R. Kanawati (LIPN) Détection de communautés October 31, 2016 31 / 69
Partitionnement de graphe
Approche de propagation d’étiquettes
igraph.community label propagation
1 Chaque nœud est attribué une étiquette unique.
2 Chaque nœud propage son étiquette à ses voisins.
3 A réception, chaque nœud adopte l’étiquette majoritaire.
4 En cas de conflit, un nœud choisit une étiquette aléatoirement.
5 Deux approches : Propagation synchrone et propagation asynchrone.
Problème :
Stabilité des partitions retrouvées.
Solution : calcul de cœurs de communautés
R. Kanawati (LIPN) Détection de communautés October 31, 2016 32 / 69
Partitionnement de graphe
Label propagation
Avantages
I Complexité : O(m)
I Simplicité de Paralléllisation
Inconvénients
I Problème de convergence, d’oscillation.
I Problème de stabilité
Différentes exécutions donnent différentes
solutions pour un même réseau
R. Kanawati (LIPN) Détection de communautés October 31, 2016 33 / 69
Partitionnement de graphe
Label propagation: Convergence
I Asynchronous label update, [RAK07]
I Semi-synchronous label update (graph coloring + propagation by
color) [CG12].
I Accentuer le problème de instabilité !
I Plus difficile à paralléliser.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 34 / 69
Partitionnement de graphe
Robust Label propagation
I Label hop attenuation [LHLC09]
I Balanced label propagation [SB11].
I Multiplex approach !
I Ensemble clustering → cœurs de communautés
[OGS10, SG12, LF12].
R. Kanawati (LIPN) Détection de communautés October 31, 2016 35 / 69
Partitionnement de graphe
Cœurs de communautés I
v Etant donné N partitions d’un graphe G de n nœuds
v Calculer la matrice n × n de consensus C = cij où cij est la fréquence
de co-occurrence des nœuds i; j dans une même communauté.
v C est la matrice d’adjacence du graphe de consensus.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 36 / 69
Partitionnement de graphe
Cœurs de communautés II
R. Kanawati (LIPN) Détection de communautés October 31, 2016 37 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary I
R. Kanawati (LIPN) Détection de communautés October 31, 2016 38 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary II
R. Kanawati (LIPN) Détection de communautés October 31, 2016 39 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary III
R. Kanawati (LIPN) Détection de communautés October 31, 2016 40 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary IV
R. Kanawati (LIPN) Détection de communautés October 31, 2016 41 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary V
R. Kanawati (LIPN) Détection de communautés October 31, 2016 42 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary VI
R. Kanawati (LIPN) Détection de communautés October 31, 2016 43 / 69
Partitionnement de graphe
Cœurs de communautés
v Etant donné un seuil α ∈ [0, 1]
v Retirer du graphe de consensus les liens dont le poids ≤ α
v Les composantes connexes du graphe résultat sont les cœurs de
communautés
R. Kanawati (LIPN) Détection de communautés October 31, 2016 44 / 69
Partitionnement de graphe
Exemple : Club de Karaté de Zachary
R. Kanawati (LIPN) Détection de communautés October 31, 2016 45 / 69
Partitionnement de graphe
Label propagation preprocessing (EPP)
1 Appliquer l’algorithme LP n fois
2 Calculer les cœurs de communautés pour α = 1
3 Réduire le graphe en substituant chaque communauté par un simple
nœud.
4 Appliquer un algorithme de détection de communautés sur le graphe
réduit.
5 Expansion des résultats.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 46 / 69
Partitionnement de graphe
Approches centrées graine
Algorithm 2 General seed-centric community detection algorithm
Require: G =< V , E > a connected graph,
1: C ← ∅
2: S ← compute seeds(G)
3: for s ∈ S do
4: Cs ← compute local com(s,G)
5: C ← C + Cs
6: end for
7: return compute community(C)
R. Kanawati (LIPN) Détection de communautés October 31, 2016 47 / 69
Partitionnement de graphe
Seed-centric approaches
Table: Characteristics of major seed-centric algorithms
Algorithm Seed Nature Seed Number Seed selection Local Com. Com. computation
Leaders-Followers [SZ10] Single Computed informed Agglomerative -
Top-Leaders [KCZ10] Single Input Random Expansion -
PapadopoulosKVS12 Subgraph Computed Informed Expansion -
WhangGD13 Single Computed informed Expansion -
BollobasR09 Subgraph Computed informed expansion -
Licod [Kan11] Set Computed Informed Agglomerative -
Yasca [Kan14] Single Computed Informed Expansion Ensemble clustering
R. Kanawati (LIPN) Détection de communautés October 31, 2016 48 / 69
Partitionnement de graphe
L’algorithme LICOD
1 Déterminer l’ensemble des Leaders L
2 Répéter jusqu’à stabilisation ou max fois :
Chaque x ∈ V trie les communautés c ∈ C dans un ordre
décroissant selon le degré 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é placée en tête de
vecteur de préférence.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 49 / 69
Partitionnement de graphe
LICOD: Identification de Leaders
Pour chaque x ∈ V , calculer les propriétés suivantes prop(x):
Propriété locale: centralité de degré
Propriétés globales: centralité de proximité, centralité de
d’intermédiarité (?)
Autre: PageRank
Soit Fx = {y ∈ Γ(x) : prop(x) > prop(y )}
|Fx |
x est un Leader si |Γ(x)| > σ ∈ [0, 1]
R. Kanawati (LIPN) Détection de communautés October 31, 2016 50 / 69
Partitionnement de graphe
LICOD: Degré d’appartenance
Le degré d’appartenance d’un nœud v à une communauté c est donnée
par l’inverse du plus court chemin SP liant v à un des leaders de c:
1
appartenance(v , c) = (min SP(v ,x))+1
x∈COM(c)
R. Kanawati (LIPN) Détection de communautés October 31, 2016 51 / 69
Partitionnement de graphe
LICOD: Fusion des votes
Application des méthode de votes:
Méthodes de condercet non-consistantes: Majority, Borda
Méthodes 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étection de communautés October 31, 2016 52 / 69
Partitionnement de graphe
The YASCA algorithm
Algorithm 3 The Yasca community detection algorithm
Require: G =< V , E > a connected graph,
1: C ← ∅
2: S ← compute seeds(G) /* diverse seed nodes */
3: for s ∈ S do
4: Cs ← compute local com(s,G)
5: C ← C + (Cs , Cs )
6: end for
7: return Ensemble Clustering(C)
R. Kanawati (LIPN) Détection de communautés October 31, 2016 53 / 69
Partitionnement de graphe
Selection de graine
Diversité guidée par les attributs topologiques
Diversité basée sur la centralisé (Degrés , betweenness, . . . , etc)
Nœuds d’articulation + nœuds centrals dans le bi-connected core
Bi-connected core
Composant bi-connecté : A sous-graphe maximal qui reste connexe
après la suppression de n’importe quel nœud.
A bi-connected core: Un graphe connexe maximal après la
suppression de tous les compensates bi-connecté de taille 1.
Pont: Un composnat bi-connecté de taille 1 connexe à un
bi-connected core
Nœud d’articulation : L’intersection d’un pont et d’un bi-connected
core.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 54 / 69
Partitionnement de graphe
Yasca: Résultats
Comparative Results on benchmark networks : NMI
Nœus d’articulation + top15% nodes centrales dans le
bi-connected-core
R. Kanawati (LIPN) Détection de communautés October 31, 2016 55 / 69
Evaluation de communautés
Evaluation des algorithmes de détection de communautés
3 grandes approches :
Qualités structurelles des communautés retrouvées.
Comparaison avec une vérité de terrain.
Evaluation orientés tâches
R. Kanawati (LIPN) Détection de communautés October 31, 2016 56 / 69
Evaluation de communautés
Fonctions d’évaluation structurelle
La qualité de C = {S1 , . . . , Si } est donnée par :
P
f (Si )
i
Q(C) = (2)
|C|
f () est une fonction de qualité d’une communauté.
4 familles de fonctions de scoring :
Fonctions basées sur la connectivité interne.
Fonctions basées sur la connectivité externe.
Fonctions hybrides
Fonctions informées par des modèles.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 57 / 69
Evaluation de communautés
Fonctions d’évaluation de la connectivité interne
2×mS
Densité interne : f (S) = nS ×(nS −1)
2×mS
Degrés moyen : f (S) = nS
|{u:u∈S,|(u,v ),v ∈S|>dm }|
FOMD: Fraction over Median Degree : f (s) = nS ,
dm est le médian de degrés des nœuds dans V
|{u∈S}:∃v ,w ∈S:(u,v ),(w ,v ),(u,w )∈E |
TPR: Triangle Participation Ratio : nS
R. Kanawati (LIPN) Détection de communautés October 31, 2016 58 / 69
Evaluation de communautés
Fonctions d’évaluation de la connectivité externe
CS
Expansion : f (S) = nS
Cs
Cut : f (S) = nS ×(N−nS )
R. Kanawati (LIPN) Détection de communautés October 31, 2016 59 / 69
Evaluation de communautés
Fonctions hybrides
CS
Conductance : f (S) = 2mS +CS
MAX-ODF : Out Degree Fraction : f (S) = maxu∈S |{(u,v )∈E
d(u)
,v 6∈S}|
P |{(u,v )∈E ,v 6∈S}|
AVG-ODF : f (S) = n1S × d(u)
u∈S
R. Kanawati (LIPN) Détection de communautés October 31, 2016 60 / 69
Evaluation de communautés
Fonctions guidées par un modèle
La modularité : f (s) = 14 (mS − E (mS ))
E (mS ) le nombre attendu de liens dans un graphe aléatoire ayant la
même distribution de degrés.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 61 / 69
Evaluation de communautés
Comparaison avec une véritié de terrain
Principe : calculer une similarité (ou distance) entre une partition
calculée et une partition de référence.
La partition de référence peur être :
annotée par un expert
ou générée par un modèle.
Deux types de mesures :
Mesures basées sur le compte des accords.
Mesures basées sur la théorie de l’information.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 62 / 69
Evaluation de communautés
Mesures basées sur le comptes des accords
Soient U, V deux partitions d’un graphe G
Indice de Rand :
a pairs placés dans une même communauté selon U et V
b pairs placés en même communauté selon U et en différents
communauté selon V
c pairs placés en même communauté selon V et en différents
communauté selon V
d pairs placées en différentes communauté 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étection de communautés October 31, 2016 63 / 69
Evaluation de communautés
L’information mutuelle
Rappel : L’information mutuelle entre deux variables aléatoires X , Y
est : I (X , Y ) = H(X ) + H(Y ) − H(X , Y )
H(X ) = ni=1 p(xi ) × log ( p(x1 i ) )
P x
Normalisation : NMI (U, V ) = √ I (U,V )
H(U)H(V )
R. Kanawati (LIPN) Détection de communautés October 31, 2016 64 / 69
Evaluation de communautés
Problème de vérité de terrain
Existence de quelques graphes de benchmark (Zachary, Football, . . . ,
etc.),
Graphe de très petits tailles.
Difficile de trouver de grands graphes avec vérité de terrain.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 65 / 69
Evaluation de communautés
Benchmarks artificiels : Le modèle LFR
But : Génération d’un graphe composé d’un ensemble de k
communautés plus au moins interconnectés entre elles.
Algorithme :
Soit N le nombre de nœuds du graphe à générer. La distribution
de degrés est tirée selon une loi de puissance de paramètre γ tel
que le degrés d’un nœud est dans un intervalle [Kmin , Kmax ].
µ est un paramètre de connexion entre communauté : µ ∈ [0, 1]
La distribution des tailles de communautés suit une autre lois de
puissance de paramètre β.
Par itération : assigner un nœud à une communauté
aléatoirement choisi de sorte que la taille de la communauté soit
supérieur au degrés interne du nœud.
Si la communauté élue est complet on exclue un de ses membres
choisi d’une manière aléatoire. Le nœud exclu devint un nœud
non assigné.
L’algorithme s’arrête lorsque tous les nœuds sont assignés à des
R. Kanawati (LIPN) Détection de communautés October 31, 2016 66 / 69
Evaluation de communautés
Bibliography I
Gennaro Cordasco and Luisa Gargano, Label propagation algorithm: a semi-synchronous approach, IJSNM 1 (2012),
no. 1, 3–26.
B. H. Good, Y.-A. de Montjoye, and A. Clauset., The performance of modularity maximization in practical contexts.,
Physical Review E (2010), no. 81, 046106.
Rushed Kanawati, Licod: Leaders identification for community detection in complex networks, SocialCom/PASSAT,
2011, pp. 577–582.
, Yasca: An ensemble-based approach for community detection in complex networks, COCOON (Zhipeng Cai,
Alex Zelikovsky, and Anu G. Bourgeois, eds.), Lecture Notes in Computer Science, vol. 8591, Springer, 2014,
pp. 657–666.
Reihaneh Rabbany Khorasgani, Jiyang Chen, and Osmar R Zaiane, Top leaders community detection approach in
information networks, 4th SNA-KDD Workshop on Social Network Mining and Analysis (Washington D.C.), 2010.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 67 / 69
Evaluation de communautés
Bibliography II
Andrea Lancichinetti and Santo Fortunato, Limits of modularity maximization in community detection, CoRR
abs/1107.1 (2011).
, Consensus clustering in complex networks, Sci. Rep. 2 (2012).
Ian X.Y. Leung, Pan Hui, Pietro Lio, and Jon Crowcroft, Towards real-time community detection in large networks, Phys.
Phy. E. 79 (2009), no. 6, 066107.
Michael Ovelgönne and Andreas Geyer-Schulz, Cluster cores and modularity maximization, ICDM Workshops, 2010,
pp. 1204–1213.
Usha N. Raghavan, Roka Albert, and Soundar Kumara, Near linear time algorithm to detect community structures in
large-scale networks, Physical Review E 76 (2007), 1–12.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 68 / 69
Evaluation de communautés
Bibliography III
Lovro Subelj and Marko Bajec, Robust network community detection using balanced propagation, European Physics
Journal B 81 (2011), no. 3, 353–362.
Massoud Seifi and Jean-Loup Guillaume, Community cores in evolving networks, WWW (Companion Volume) (Alain
Mille, Fabien L. Gandon, Jacques Misselis, Michael Rabinovich, and Steffen Staab, eds.), ACM, 2012, pp. 1173–1180.
D Shah and T Zaman, Community detection in networks: The leader-follower algorithm, Workshop on Networks Across
Disciplines in Theory and Applications, NIPS, 2010.
R. Kanawati (LIPN) Détection de communautés October 31, 2016 69 / 69
