J'ai un réseau qui est un réseau de graphes et c'est le réseau Email-Eu qui est disponible dans ici .
Cet ensemble de données contient l'ensemble de données réel, qui est un graphique d'environ 1005 nœuds avec les arêtes qui forment ce graphique géant. Il a également les étiquettes de vérité terrain pour les nœuds et ses communautés correspondantes (département). Chacun de ces nœuds appartient à l'un de chacun des 42 départements.
Je veux exécuter un algorithme de détection de communauté sur le graphique pour trouver le département correspondant pour chaque nœud. Mon objectif principal est de trouver les nœuds dans la plus grande communauté.
Donc, je dois d'abord trouver les 42 premiers départements (Communautés), puis trouver les nœuds dans le plus grand d'entre eux.
J'ai commencé avec Girvan-Newman Algorithm pour trouver les communautés. La beauté de Girvan-Newman est qu'il est facile à mettre en œuvre puisque chaque fois que je dois trouver le bord avec le plus grand écart et le supprimer jusqu'à ce que je trouve les 42 départements (communautés) que je veux.
J'ai du mal à trouver d'autres algorithmes de détection de communauté qui me permettent de spécifier le nombre de communautés / partitions dont j'ai besoin pour décomposer mon graphique.
Y a-t-il une fonction / technique de détection de communauté que je peux utiliser, qui me donne la possibilité de spécifier combien de communautés dois-je découvrir à partir de mon graphique? Toutes les idées sont très appréciées.
J'utilise Python et NetworkX.
3 Réponses :
Je ne suis pas entièrement sûr de ma réponse, mais vous pouvez peut-être essayer ceci. Êtes-vous au courant de la propagation des étiquettes? L'idée principale est que vous avez des nœuds dans le graphique qui sont étiquetés, c'est-à-dire qu'ils appartiennent à une communauté et que vous souhaitez donner des étiquettes à d'autres nœuds non étiquetés dans votre graphique. LPA répartira ces étiquettes sur le graphique et vous donnera une liste des nœuds et des communautés auxquelles ils appartiennent. Ces communautés seront les mêmes que celles auxquelles appartient votre ensemble étiqueté de nœuds.
Je pense donc que vous pouvez contrôler le nombre de communautés que vous souhaitez extraire du graphique en contrôlant le nombre de communautés que vous initialisez au début. Mais je pense qu'il est également possible qu'après la convergence de LPA, certaines des communautés que vous avez initialisées disparaissent du graphique en raison de la structure du graphique et du caractère aléatoire de l'algorithme. Mais il existe de nombreuses variantes de LPA où vous pouvez contrôler ce caractère aléatoire. Je crois que cette page de sklearn en parle.
Salut Siddhant, En fait, l'analyse que je veux ne doit pas commencer par des connaissances préalables disponibles dans l'étiquette de vérité terrain. Ainsi, il devrait trouver les communautés en se basant uniquement sur le graphique disponible.
Qu'en est-il du clustering de Louvain? il est implémenté dans la function de networkx best_partition. Le paramètre de résolution donne plus ou moins de communautés, mais vous ne pouvez pas spécifier comme un nombre. Une discussion a eu lieu sur ce paramètre ici .
Je l'ai essayé. Cependant, cela ne me permet pas de choisir le nombre de communautés dans lesquelles je dois me partitionner. Il partitionne en fonction du meilleur ajustement possible.
Umm autre essai, si vous pouvez trouver une métrique qui capture la distance entre deux nœuds (par exemple, le poids du bord ou le degré du nœud), vous pouvez exécuter kmeans dessus et finalement définir le nombre de clusters que vous voulez?
Une réponse (et une solution) (très) partielle à votre question consiste à utiliser l ' algorithme Fluid Communities implémenté par Networkx sous le nom asyn_fluidc .
Notez qu'il fonctionne sur des graphiques connectés, non dirigés et non pondérés, donc si votre graphique a n composants connectés, vous devez l'exécuter n fois. En fait, cela pourrait être un problème important car vous devriez avoir une sorte de connaissance préliminaire de chaque composant pour choisir le k correspondant.
Quoi qu'il en soit, cela vaut la peine d'essayer.
Vous pouvez essayer pysbm . Il est basé sur networkx et implémente différentes variantes de modèles de blocs stochastiques et de méthodes d'inférence.
Si vous envisagez de passer de networkx à un autre package graphique basé sur python, vous pouvez envisager de graph-tool , où vous pourrez utiliser le modèle de bloc stochastique pour tâche de clustering . Un autre package intéressant est igraph , vous pouvez consulter Comment regrouper un graphe en utilisant python igraph .
Les approches directement disponibles dans networkx sont plutôt démodées. Si vous recherchez des méthodes de clustering de pointe, vous pouvez envisager le clustering spectral ou Infomap. La sélection dépend de votre utilisation souhaitée des communautés déduites. La tâche consistant à déduire la vérité terrain à partir d'un réseau relève (approximativement) du théorème No-Free-Lunch, c'est-à-dire (à peu près) aucun algorithme n'existe, de sorte qu'il renvoie de «meilleures» communautés que tout autre algorithme, si nous faisons la moyenne toutes les possibilités.
Merci @ sparky05, j'ai passé une journée entière à essayer d'installer igraph et je n'ai pas réussi. J'ai vraiment du mal à le faire fonctionner.
C'est le problème des packages de graphes plus sophistiqués (mais plus rapides). L'installation d'igraph a et graph-tool n'est pas aussi simple que l'installation de networkx. Si vous avez le temps d'attendre après les vacances de Pâques, je connais un prochain package de clustering basé sur networkx, implémentant certaines variantes du modèle de bloc stochastique.
@Jan J'ai ajouté le lien vers le référentiel au cas où vous recherchiez toujours le clustering sans passer de networkx .
Merci mon cher, je vais l'essayer
Certaines méthodes de clustering proposées dans le package sk-learn vous permettent de regrouper votre graphique avec un nombre spécifié de clusters. Il pourrait y avoir un ajustement pour la détection de la communauté avec quelques petits ajustements sur le graphique.