5.2 Modularité et intermédiarité
Une autre approche de détection de communautés est basée sur la notion d’intermédiarité d’une arête, exploitée par Girvan et Newman. La modularité est un concept qui permet de sélectionner le nombre de clusters.
5.2.1 Intermédiarité d’arête
La notion d’intermédiarité d’une arête ou edge betweenness est l’équivalent de l’intermédiarité d’un noeud (betweenness centrality). Le coefficient de l’intermédiarité de l’arête \(e\) est défini par \[B(e) = \sum_{i, j: i \neq j} \frac{g_{ij(e)}}{g_{ij}},\] où \(g_{ij}\) est le nombre de plus courts chemins de \(i\) à \(j\), et \(g_{ij}(e)\) le nombre de plus courts chemins de \(i\) à \(j\) qui passent par \(e\).
Intuitivement, les arêtes à forte intermédiarité sont des arêtes reliant des communautés plutôt que des arêtes internes à celles-ci.
L’algorithme de Girvan and Newman (2002) exploite cette propriété en retirant succéssivement les arêtes de plus forte intermédiarité. Après chaque suppression d’arête on évalue de nouveau toutes les intermédiarités d’arête. On procède ainsi jusqu’à isoler tous les noeuds.
C’est un algorithme de classification hiérarchique qui construit un dendrogramme.
Algorithme. Girvan-Newman.
Entrée: graphe \(G=(V,E)\)
Sortie: dendrogramme indiquant les clusterings emboîtés
Procédure:
On répète les deux étapes suivant tant que l’ensemble d’arêtes \(E\) n’est pas vide:
Calculer l’intermédiarité \(B(e)\) de toutes les arêtes \(e\in E\).
Retirer de \(E\) l’arête \(e^*\) avec la plus grande valeur: \(e^*:=\arg\max_{e\in E}B(e)\).
5.2.2 Modularité pour le choix du nombre de clusters
Avec l’algorithme de Girvan-Newman se pose la question sur le choix du nombre de clusters, ou autrement dit: où couper le dendrogramme ?
L’idée est de s’arrêter si pour pour chaque communauté, la "cohésion" intérieure est plus grande que ce que l’on obtiendrait "de façon aléatoire".
La modularité de la partition \((C_1, \ldots, C_K)\) est définie par \[\begin{equation*} \frac{1}{2|E|} \sum_{k=1}^K \sum_{(v_i, v_j) \in C_k} \left(\mathbb {1}_{(v_i, v_j) \in E} - \frac{d_i d_j}{2|E|}\right) \end{equation*}\] La modularité mesure la densité de connexion à l’intérieur des clusters et la compare à la densité entre les clusters. La modularité est une valeur dans \([-1, 1]\). Plus la modularité est grande, plus les arêtes sont "concentrées" dans les communautés. On va donc calculer la modularité à chaque itération et s’arrêter s’il n’y a pas d’amélioration.
La complexité de l’algorithme de Girvan-Newman est en \(O(|E|^2 n)\).
Pourquoi ne pas optimiser directement la modularité ?
Trouver la configuration avec la modularité maximum est un probleme NP complet.
Il existe plusieurs algorithmes pour approcher la solution. L’une des plus utilisée est la méthode de Blondel et al. (2008) (algorithme de Louvain): c’est une méthode d’optimisation locale. On tente d’associer un noeud à la même communauté que l’un de ses voisins. Le temps de calcul est quasi linéaire en la taille du graphe, de l’order \(O(|E|)\).
References
Blondel, Vincent D., Jean L. Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. “Fast Unfolding of Communities in Large Networks.” Journal of Statistical Mechanics: Theory and Experiment 99 (10): 7821–6.
Girvan, M., and M. E. J. Newman. 2002. “Community Structure in Social and Biological Networks.” Proceedings of the National Academy of Sciences 99 (12): 7821–6. https://doi.org/10.1073/pnas.122653799.