Quelles sont les différences entre les algorithmes de détection de la communauté dans igraph?

Voici un bref résumé des algorithmes de détection de communauté actuellement implémentés dans igraph:

• edge.betweenness.community est un processus de décomposition hiérarchique dans lequel les arêtes sont supprimées dans l’ordre décroissant de leurs scores d’inter-bord (c’est-à-dire le nombre de chemins les plus courts passant par une arête donnée). Ceci est motivé par le fait que les arêtes connectant différents groupes sont plus susceptibles d’être contenues dans de multiples chemins les plus courts simplement parce que dans de nombreux cas, ils sont la seule option pour aller d’un groupe à un autre. Cette méthode donne de bons résultats, mais elle est très lente en raison de la complexité de calcul des calculs de disparité des contours et du fait que les scores d’intercessibilité doivent être recalculés après chaque suppression de bord. Vos graphiques avec ~ 700 sumts et ~ 3500 arêtes se situent autour de la limite supérieure de taille des graphes pouvant être analysés avec cette approche. Un autre inconvénient est que edge.betweenness.community construit un dendrogramme complet et ne vous donne aucune indication sur l’endroit où couper le dendrogramme pour obtenir les groupes finaux. Vous devrez donc utiliser une autre mesure pour en décider (par exemple, la modularité score des partitions à chaque niveau du dendrogramme).

• fastgreedy.community est une autre approche hiérarchique, mais elle est ascendante plutôt que descendante. Il tente d’optimiser une fonction de qualité appelée modularité de manière gourmande. Initialement, chaque sumt appartient à une communauté distincte, et les communautés sont fusionnées de manière itérative de sorte que chaque fusion soit localement optimale (c.-à-d. Qu’elle génère la plus grande augmentation de la valeur actuelle de la modularité). L’algorithme s’arrête lorsqu’il n’est plus possible d’augmenter la modularité, il vous donne donc un regroupement ainsi qu’un dendrogramme. La méthode est rapide et c’est la méthode qui est généralement utilisée en première approximation car elle n’a pas de parameters à régler. Cependant, il est connu qu’il souffre d’une limite de résolution, c’est-à-dire que les communautés au-dessous d’un seuil de taille donné (dépendant du nombre de nœuds et de bords si je me souviens bien) seront toujours fusionnées avec les communautés voisines.

• walktrap.community est une approche basée sur des marches aléatoires. L’idée générale est que si vous effectuez des promenades aléatoires sur le graphique, les promenades sont plus susceptibles de restr dans la même communauté car il n’y a que quelques arêtes qui mènent en dehors d’une communauté donnée. Walktrap exécute de courtes étapes aléatoires de 3-4-5 étapes (en fonction de l’un de ses parameters) et utilise les résultats de ces marches aléatoires pour fusionner des communautés séparées de manière ascendante, comme fastgreedy.community . Encore une fois, vous pouvez utiliser le score de modularité pour sélectionner où couper le dendrogramme. C’est un peu plus lent que l’approche rapide gourmande mais aussi un peu plus précis (d’après la publication originale).

• spinglass.community est une approche de la physique statistique, basée sur le modèle Potts. Dans ce modèle, chaque particule (ie sumt) peut être dans l’un des états de spin, et les interactions entre les particules (ie les arêtes du graphe) spécifient quelles paires de sumts préféreraient restr dans le même état de spin et lesquelles préfèrent avoir des états de spin différents. Le modèle est ensuite simulé pour un nombre donné d’étapes et les états de spin des particules définissent les communautés. Les conséquences sont les suivantes: 1) Il n’y aura jamais plus de c communautés à la fin, bien que vous puissiez définir c jusqu’à 200, ce qui est probablement suffisant pour vos objectives. 2) Il peut y avoir moins de c communautés à la fin car certains états de spin peuvent devenir vides. 3) Il n’est pas garanti que les nœuds situés dans des parties complètement distantes (ou déconnectées) des réseaux aient des états de spin différents. Il est plus probable que ce soit un problème uniquement pour les graphiques déconnectés, alors je ne m’inquiéterais pas de cela. La méthode n’est pas particulièrement rapide et non déterministe (en raison de la simulation elle-même), mais elle possède un paramètre de résolution ajustable qui détermine la taille des grappes. Une variante de la méthode de spinglass peut également prendre en compte les liens négatifs (c.-à-d. Les liens dont les points d’extrémité préfèrent se trouver dans des communautés différentes).

• leading.eigenvector.community est une approche hiérarchique descendante qui optimise à nouveau la fonction de modularité. À chaque étape, le graphique est divisé en deux parties de manière à ce que la séparation elle-même entraîne une augmentation considérable de la modularité. La division est déterminée en évaluant le premier vecteur propre de la masortingce dite de modularité, et il existe également une condition d’arrêt qui empêche la division supplémentaire des groupes étroitement liés. En raison des calculs de vecteurs propres impliqués, cela pourrait ne pas fonctionner sur les graphes dégénérés où le solveur ARPACK eigenvector est instable. Sur les graphes non dégénérés, il est probable que le score de modularité soit plus élevé que celui de la méthode gourmande rapide, même s’il est un peu plus lent.

• label.propagation.community est une approche simple dans laquelle chaque nœud se voit atsortingbuer l’une des k étiquettes. La méthode procède ensuite de manière itérative et réatsortingbue les étiquettes aux nœuds de manière à ce que chaque nœud utilise l’étiquette la plus fréquente de ses voisins de manière synchrone. La méthode s’arrête lorsque l’étiquette de chaque nœud est l’une des étiquettes les plus fréquentes dans son voisinage. Il est très rapide mais donne des résultats différents en fonction de la configuration initiale (ce qui est décidé aléatoirement), il faut donc exécuter la méthode un grand nombre de fois (disons 1000 fois pour un graphe) et construire un étiquetage consensuel fastidieux.

La version 0.6 inclura également l’algorithme de détection de la communauté Infomap, basé sur des principes théoriques de l’information; il essaie de créer un regroupement qui fournit la longueur de description la plus courte pour une promenade aléatoire sur le graphique, où la longueur de la description est mesurée par le nombre de bits par sumt attendu requirejs pour coder le chemin d’une marche aléatoire.

Quoi qu’il en soit, je ferais probablement une première approximation avec fastgreedy.community ou walktrap.community , puis d’évaluer d’autres méthodes s’il s’avère que ces deux méthodes ne conviennent pas à un problème particulier.

Un résumé des différents algorithmes de détection de communauté peut être trouvé ici: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Notamment, l’algorithme InfoMAP est un nouveau venu récent qui pourrait être utile (il supporte aussi les graphes dirigés).