La détection de communautés avec Pajek 3.6

La toute nouvelle version de Pajek réserve de bonnes surprises aux explorateurs de graphes complexes.

Les nouveautés dont il est question ici ont été ajoutées au logiciel entre Mai 2012 et Septembre 2012.

Deux algorithmes de détection de communautés ont été implémentés:

Network/Create Partition/Communities

-Louvain method

Le premier algorithme s’appuie sur la méthode de Louvain [1]. Cette méthode est bien adaptée aux graphes valués, y compris s’ils sont signés. Comme pour beaucoup d’algorithmes de clustering (ou détection de communautés), la qualité du partitionnement est optimisée par maximisation de la fonction de modularité [2].  L’indice de modularité mesure la différence entre la densité d’un graphe (ou sous-graphe) donné et la densité d’un graphe aléatoire possédant les même caractéristiques (nombre et poids des liens).

Principe

Maximiser la fonction de modularité pour partitionner un graphe revient à s’assurer que le nombre et le poids des liens est plus important à l’intérieur des partitions qu’entre les partitions. Pour l’exprimer autrement, il faut que la densité intra-communautaire dépasse la densité inter-communautaire.

La méthode de Louvain est « bottom-up » et multi-niveau. Au lancement de l’algorithme, tous les sommets appartiennent à une partition différente. Ils sont regroupés, par itération, dans des partitions de modularité optimale. Arrivé à une première situation d’optimum, le processus se poursuit au niveau supérieur : chaque partition est traitée comme un sommet et ainsi de suite. L’opération continue jusqu’à ce qu’il n’y ait plus aucun gain de modularité possible.

Avantage

Cette approche permet d’échapper au défaut de la modularité connu sous le nom de « limite de résolution » [3]. Si le fait d’associer une partition du premier niveau avec une autre devait engendrer une perte de modularité, cette association ne serait pas réalisée par la méthode de Louvain. De ce fait, les petites structures dotées d’une bonne modularité ne risquent pas d’être noyées dans des structures plus grandes et moins significatives. C’est ce qu’il risquerait d’arriver avec un algorithme « top-down » appliqué à un trop grand graphe.

Inconvénient

Le défaut connu de la méthode provient de la sensibilité du résultat à l’ordre de traitement des sommets. L’ordre dans lequel les sommets sont considérés a une influence sur le partitionnement. De ce fait, il peut être utile de procéder à des permutations pour s’assurer de la robustesse du résultat [4]. L’autre piste est d’imposer un ordre qui tienne compte des caractéristiques du réseau [5].

En plus de l’algorithme classique de Louvain,  Pajek propose une variante (avec rafinement multi-niveau) qui tend à donner de meilleurs résultats pour les grands graphes [6]. La méthode de Louvain est également disponible dans les logiciels Gephi et NetworkX ainsi que dans la librairie igraph du logiciel R, l’algorithme étant plus rapide sur Pajek que sur Gephi.

-VOS Clustering

La méthode de détection de communauté VOS optimise une autre fonction de qualité que la fonction de modularité: la fonction dite de VOS clustering [7]. Il s’agit d’une variante pondérée de la modularité qui a été pensée pour le traitement des données bibliométriques. Cette technique donne moins de poids qu’une méthode classique aux sommets à très haut degré. Contrairement à la méthode de Louvain, elle dépend d’un algorithme « « top-down« . Pour cette raison, le seul moyen d’échapper au problème de limite de la résolution consiste à faire varier le paramètre de résolution.

Cette méthode convient en fait aux graphes pour lesquels la valeur des liens rend compte de l’importance de la similarité entre les sommets. Ses concepteurs ont souhaité que soit associé à l’algorithme de clustering un algorithme de visualisation faisant appel au même principe mathématique. Cette approche unifiée permet d’éviter qu’ils y ait des incohérences entre le résultat du processus de clustering et la représentation graphique de ce résultat.

Tout naturellement, Pajek propose aussi l’algorithme de visualisation VOS. Il fonctionne sur le principe de l’optimisation de la fonction de qualité dite de VOS mapping. Étant donné la proximité des deux méthodes de détection, il n’est surement pas impensable d’utiliser le VOS mapping pour représenter un graphe partitionné suivant la méthode de Louvain.

Aller plus loin

Une comparaison des deux méthodes de détection est accessible sur: http://mrvar.fdv.uni-lj.si/pajek/community/LouvainVOS.htm

Des précisions sur l’utilisation de ces méthodes avec Pajek se trouvent aussi sur le site: paramétrage, évaluation de la qualité du partitionnement, représentation graphique du résultat.

Depuis l’interface graphique de Pajek, un raccourci vers le logiciel VOSviewer offre la possibilité d’obtenir rapidement une représentation  élégante du partitionnement.

Ci-dessous, un exemple à partir des données de collaborations scientifiques néerlandaises (Source: Web of Science 2006-2008):

Références
[1] V. Blondel, J.-L. Guillaume, R. Lambiotte, et E. Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics, vol. 2008, no 10, sept. 2008.
[2] Il existe de nombreuses autres méthodes de détection de communautés. Pour avoir un aperçu de l’existant: S. Fortunato, « Community detections in graphs », Physics and Society, vol. 2010, no 486, p. 75-174.
[3] S. Fortunato et M. Barthélemy, « Resolution limit in community detection », Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no 1, p. 36-41, janv. 2007.
[4] V. Blondel, G. Krings, et I. Thomas, « Régions et frontières de téléphonie mobile en Belgique et dans l’aire métropolitaine bruxelloise », Brussels studies, no 42, oct. 2010.
[5] P. De Meo, E. Ferrara, G. Fiumara, et A. Provetti, « Generalized Louvain method for community detection in large networks », under review, 2011. URL: http://www.emilio.ferrara.name/wp-content/uploads/2011/07/isda2011-k-path.pdf
[6] R. Rotta et A. Noack, « Multilevel local search algorithms for modularity clustering », Journal of Experimental Algorithmics, vol. 16, no 2.3, 2011.
[7] L. Waltman, N. J. van Eck, et E. C. M. Noyons, « A unified approach to mapping and clustering of bibliometric networks », Journal of Infometrics, vol. 4, no 4, p. 629-635, oct. 2010.