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.

 


4 réflexions au sujet de « La détection de communautés avec Pajek 3.6 »

  1. Bonjour;
    j’ai un problème de comment utiliser la fonction de modularité de Louvain pour de détection des communautés …S’il vous plaît pouvez vous me donnée un exemple mathématique réelle pour calculer la modularité d’un graphe ..
    La premier fonction de cette lien .
    https://en.wikipedia.org/wiki/Louvain_Modularity

    et
    merci infiniment

  2. Bonjour,

    Je suis avec intérêt votre carnet. Je me permets de commenter ce billet car je pense qu’il contient quelques imprécisions.

    La méthode « Louvain » est simplement une heuristique de maximisation de la modularité, alors que la limite de résolution que vous évoquez est un problème intrinsèque de la mesure. De ce fait, la seule raison pour laquelle la méthode Louvain pourrait éviter le problème de résolution de la mesure serait d’être sous-optimale et de ne pas trouver le maximum de modularité. Une solution sous-optimale pourrait ainsi ne pas fusionner des groupes qui sont intuitivement de bonnes communautés mais dont la fusion augmente la modularité (comme expliqué dans l’article de Fortunato et Barthélemy et contrairement à ce qu’on pourrait comprendre en lisant votre billet). Or, Louvain n’a en général pas ce comportement pour la bonne raison que c’est un algorithme glouton de fusion : s’il découvre une paire de groupes dont la fusion augmentera la modularité, il fera la fusion en question. Comme toute heuristique, Louvain est bien sur sous-optimal mais pas dans un sens qui le rend moins sensible au problème de résolution de la mesure.

    On peut s’amuser à utiliser les différents niveaux hiérarchiques fournis pour Louvain pour essayer de contrer la limite de résolution, mais il faut savoir que ce sont simplement des artefacts algorithmiques sans définition propre. Il est peu probable qu’ils correspondent à des structures effectives dans le graphe étudié.

    Il est étonnant d’ailleurs que la méthode Louvain connaisse un tel succès alors que pour un coût marginalement supérieur on fait mieux, comme l’ont montré Noack et Rotta (cf http://arxiv.org/abs/0812.4073v2). Je trouve assez ironique que Pajek présente cette méthode comme « Another version of Louvain community detection algorithm » alors que l’article de Noack et Rotta montre que la filiation est un peu plus complexe que ça : la méthode Louvain est très similaire à de nombreuses méthodes développées bien avant pour faire de la partition de graphes avec d’autres critères de qualité (des variantes de graph cut). La méthode Noack et Rotta est alors une transposition des techniques les plus avancées de partition de graphes à la maximisation de la modularité. Il y a donc des branches familiales parallèles et non pas une amélioration de Louvain par Noack et Rotta…

    Enfin, si on veut lutter contre le phénomène de limite de résolution, on peut simplement faire des clusters de clusters, comme je le fait ici : http://smf4.emath.fr/Publications/JSFdS/152_3/pdf/sfds_jsfds_152_3_34-65.pdf.

    En espérant que ces précisions pourront être utiles…

    Fabrice

    • Votre commentaire permet d’aller plus loin dans le détail et je vous en remercie. Il soulève de bonnes questions et, je l’espère ouvrira la discussion. Il y a tant d’algorithmes de partitionnement que l’utilisateur (comme moi) peut s’y perdre.

      Louvain ne fait fusionner deux groupes que s’il y a un gain de modularité et c’est ce qui est mis en valeur par Vincent Blondel. En plus, conscient du fait que certaines fusions peuvent cacher des groupes intéressants, ce dernier incite l’utilisateur à s’intéresser aux résultats intermédiaires
      (« les différents niveaux hiérarchiques fournis par Louvain »).

      Ce sont, si j’ai bien compris, les deux arguments que Vincent Blondel avance pour se prémunir de la question de limite de résolution (je n’avais pas précisé le second, merci de m’en donner l’occasion).
      Je retiens votre mise en garde:
      « Il faut savoir que ce sont simplement des artefacts algorithmiques sans définition propre et il est peu probable qu’ils correspondent à des structures effectives dans le graphe étudié » (mais le fait qu’ils aient une bonne modularité a un sens, non?).

      Enfin, sur la seconde méthode évoquée (VOS clustering), la documentation étant moins fournie que sur Louvain, commentaires et retours sont bienvenus.

      • Vous écrivez, ce qui est parfaitement exact, que « Louvain ne fait fusionner deux groupes que s’il y a un gain de modularité ». Or, comme je le disais au dessus, le problème est bien dans la modularité elle même, pas dans l’algorithme. Ce que Fortunato et Barthélemy appellent limite de résolution est l’existence de graphes dans lequel on observe clairement des modules et pour lesquels la classification optimale au sens de la modularité comprend moins de classes : certains modules naturels sont regroupés dans des classes dans la solution de modularité maximale. Dire qu’un algorithme de maximisation de la modularité peut lutter contre ce phénomène est simplement dire qu’il n’est pas optimal et qu’il ne trouve pas la meilleure solution. Fusionner des groupes tant que cela augmente la modularité n’est certes pas optimal, mais c’est aussi un bon moyen de rencontrer la limite de résolution puisque celle-ci est justement déclenchée (si je puis dire) par des fusions « contre nature » (mais parfaitement valides au sens de Louvain, par exemple).

        Le deuxième argument des concepteurs de Louvain est moins faux, mais il est dangereux parce que rien n’est vraiment garanti au sujet des niveaux intermédiaires. En particulier, on ne peut pas garantir que si deux classes sont fusionnées entre deux niveaux, la meilleure décomposition de la fusion en deux sous-classes serait effectivement les deux classes d’origine (j’espère être clair). C’est pourquoi il vaut mieux procéder comme le recommandent Fortunato et Barthélemy en construisant récursivement des partitions des classes du niveau le plus agrégé.

        Concernant VOS, je le découvre dans votre billet, je n’ai donc pas de commentaire particulier.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *