Quelles sont les différences entre les algorithmes de détection communautaire d'igraph?

voici un bref résumé des algorithmes de détection de communauté actuellement mis en œuvre dans igraph:

• edge.betweenness.community est un processus de décomposition hiérarchique où les arêtes sont enlevées dans l'ordre décroissant de leur arête entre les scores (c.-à-d. le nombre de chemins Les plus courts qui passent par un bord donné). Ceci est motivé par le fait que les arêtes reliant les différents groupes sont plus susceptibles d'être contenues dans plusieurs plus court les chemins simplement parce que dans de nombreux cas, ils sont la seule option pour passer d'un groupe à un autre. Cette méthode donne de bons résultats mais elle est très lente en raison de la complexité computationnelle des calculs de l'intervalle entre les arêtes et parce que les scores d'intervalle doivent être recalculés après chaque enlèvement d'arête. Vos graphes avec ~ 700 sommets et ~3500 arêtes sont autour de la limite supérieure de taille des graphes qui sont réalisables pour être analysés avec cette approche. Un autre inconvénient est que edge.betweenness.community construit un le dendrogramme complet et ne vous donne aucune indication sur l'endroit où couper le dendrogramme pour obtenir les groupes finaux, de sorte que vous devrez utiliser une autre mesure pour décider cela (par exemple, le score de modularité 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é d'une manière avide. Initialement, tous les sommets fait partie d'une communauté distincte, et les communautés sont fusionnées de façon itérative de sorte que chaque Fusion est localement optimale (c.-à-d. donne la plus grande augmentation de la valeur actuelle de la modularité). L'algorithme s'arrête lorsqu'il n'est pas possible d'augmenter la modularité, de sorte qu'il vous donne un groupement ainsi que d'un dendrogramme. La méthode est rapide et c'est la méthode qui est généralement jugé comme une première approximation car il n'a pas de paramètres à régler. Cependant, il est connu pour souffrir d'une limite de résolution, c'est-à-dire que les communautés situées en dessous d'un seuil de taille donné (en fonction 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 promenades aléatoires. L'idée générale est que si vous effectuez des promenades aléatoires sur le graphique, alors les promenades sont plus susceptibles de rester dans la même communauté parce qu'il y a seulement quelques bords qui mènent à l'extérieur d'une communauté donnée. Walktrap tourne court marches aléatoires de 3-4-5 étapes (selon l'un de ses paramètres) et utilise les résultats de ces marches aléatoires à la fusion 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. Il est un peu plus lent que l'approche Rapid greedy mais aussi un peu plus précis (selon la publication originale).

• spinglass.community est une approche de la physique statistique, basée sur le soi-disant modèle Potts. Dans ce modèle, chaque particule (c'est-à-dire le sommet) peut être dans l'un des états de spin c , et les interactions entre les particules (c'est-à-dire les bords du graphique) spécifient quelles paires de Sommets préféreraient rester dans le même état de spin et lesquelles préféreraient 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 à la fin définissent les communautés. Les conséquences sont comme suit: 1) Il n'y aura jamais plus de c communautés à la fin, bien que vous pouvez mettre c à aussi haut que 200, qui est susceptible d'être suffisant pour vos fins. 2) Il peut y avoir moins de communautés c à la fin car certains états de spin peuvent devenir vides. 3) Il n'est pas garanti que les noeuds dans les parties complètement distantes (ou disconencées) des réseaux aient des états de spin différents. Cela est plus susceptible d'être un problème pour graphiques déconnectés seulement, donc je ne m'inquiéterais pas à ce sujet. La méthode n'est pas particulièrement rapide et non déterministe (à cause de la simulation elle-même), mais a un paramètre de résolution ajustable qui détermine les tailles des amas. Une variante de la méthode spinglass peut également tenir compte des liens négatifs (c.-à-d. des liens dont les points terminaux préfèrent être dans des communautés différentes).

• leading.eigenvector.community est une approche hiérarchique descendante qui optimise la la modularité fonctionne à nouveau. Dans chaque étape, le graphique est divisé en deux parties de façon que la séparation elle-même produit une augmentation significative de la modularité. La séparation est déterminée en évaluant le premier vecteur propre de la matrice dite de modularité, et il y a aussi une condition d'arrêt qui empêche les groupes étroitement connectés d'être divisés plus loin. En raison des calculs propres au secteur impliqués, il pourrait ne pas fonctionner sur des graphes dégénérés où le solveur ARPACK eigenvector est instable. Sur graphes non-dégénérés, il est probable qu'il donne un score de modularité plus élevé que la méthode de greedy rapide, bien qu'elle soit un peu plus lente.

• label.propagation.community est une approche simple dans laquelle chaque noeud est attribué une des étiquettes k . La méthode procède ensuite de manière itérative et affecte de nouveau les étiquettes aux noeuds de manière à ce que chaque noeud prenne l'étiquette la plus fréquente de ses voisins de manière synchrone. La méthode s'arrête lorsque l'étiquette de chaque noeud 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 (qui est décidé au hasard), donc on devrait exécuter la méthode un grand nombre de fois (disons, 1000 fois pour un graphique) et puis construire un étiquetage de consensus, qui pourrait être fastidieux.

igraph de 0,6 comprendra également l'état-of-the-art Infomap communauté algorithme de détection, qui est basé sur l'information de la théorie des principes; il tente de constituer un groupement qui fournit la plus courte description longueur pour une marche aléatoire sur le graphe, où la description longueur est mesurée par le nombre de bits par sommet nécessaire à l'encodage de la trajectoire d'une marche aléatoire.

de toute façon, je dirais probablement fastgreedy.community ou walktrap.community comme première approximation et ensuite évaluer d'autres méthodes quand il s'avère que ces deux ne sont pas appropriés pour un problème particulier pour une raison quelconque.