Comment puis-je cluster un graphique en Python?
Soit G un graphe. Si G est un ensemble de nœuds et des liens. J'ai besoin de trouver un moyen rapide d'une partition du graphe. Le graphique, je travaille maintenant a seulement 120*160 nœuds, mais j'ai peut-être bientôt à travailler sur un équivalent problème, dans un autre contexte (pas la médecine, mais aussi de développement de site web), avec des millions de nœuds.
Donc, ce que j'ai fait était de stocker tous les liens dans un graphe de la matrice:
M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))
Maintenant M est titulaire d'un 1 en position s,t, si le nœud s est connecté au nœud t. I assurez-vous que M est le symétrique de M[s,t]=M[t,s] et chaque nœud liens vers soi M[s,s]=1.
Si je me souviens bien, si je multiplie M avec M, le résultat est une matrice qui représente le graphique qui relie les sommets qui sont atteint à travers deux étapes.
Donc je continue sur multplying M avec lui-même, jusqu'à ce que le nombre de zéros dans la matrice ne diminuent pas plus longtemps. Maintenant, j'ai la liste des composants raccordés.
Et maintenant, j'ai besoin de cluster de cette matrice.
Jusqu'à maintenant, je suis assez satisfait de l'algorithme. Je pense que c'est facile, élégant, et assez rapide. J'ai du mal avec cette partie.
En fait, j'ai besoin de partager ce graphique dans ses composantes connexes.
Je peux passer par tous les nœuds, et de voir quels sont-ils connectés à.
Mais ce que sur le tri de la matrice de réordonner les lignes. Mais je ne sais pas si c'est possible de le faire.
Ce qui suit est le code pour l'instant:
def findzeros(M):
nZeros=0
for t in M.flat:
if not t:
nZeros+=1
return nZeros
M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))
for s in data.keys():
MatrixCells[s,s]=1
for t in data.keys():
if t<s:
if (scipy.corrcoef(data[t],data[s])[0,1])>threashold:
M[s,t]=1
M[t,s]=1
nZeros=findzeros(M)
M2=M*M
nZeros2=findzeros(M2)
while (nZeros-nZeros2):
nZeros=nZeros2
M=M2
M2=M*M
nZeros2=findzeros(M2)
Edit:
Il a été suggéré que j'utilise la décomposition SVD. Voici un exemple simple de le problème sur un 5x5 graphique. Nous allons utiliser ce depuis le 19200x19200 matrice carrée n'est pas facile à voir les grappes.
import numpy
import scipy
M=numpy.mat(numpy.zeros((5,5)))
M[1,3]=1
M[3,1]=1
M[1,1]=1
M[2,2]=1
M[3,3]=1
M[4,4]=1
M[0,0]=1
print M
u,s,vh = numpy.linalg.linalg.svd(M)
print u
print s
print vh
Il y a essentiellement 4 clusters ici: (0),(1,3),(2),(4)
Mais je ne vois pas comment le svn peut aider dans ce contexte.
Bonjour, merci pour passer le temps sur ma question. La question, explicite est: "Comment dois-je déterminer les composants qui sont connectés?" Je pensais que vous l'avez compris, et où simplement avoir du divertissement innocent.
Speroni: Envisager la réécriture de votre question pour la rendre plus simple, plus ciblée et plus claire. Une longue discussion est dur de suivre. Bref des exemples de code et une question très évidente, c'est mieux. Vous fournir un code, alors en demandant "comment dois-je déterminer..?" ne semble pas juste.
Merci, mais depuis que j'ai reçu la réponse que je cherchais, et depuis d'autres utilisateurs semblait comprendre la question, je pense que je vais rester dans cette. En Ce Qui Concerne, Pietro
OriginalL'auteur Pietro Speroni | 2009-03-17
Vous devez vous connecter pour publier un commentaire.
Pourquoi ne pas utiliser un vrai graphique de la bibliothèque, comme Python-Graph? Il a un fonction pour déterminer les composants connectés (si aucun exemple n'est fourni). J'imagine un dédié bibliothèque va être plus rapide que ce que ad-hoc graphique de code que vous avez concocté.
EDIT: NetworkX semble comme il pourrait être un meilleur choix que python-graphique; ses documentation (ici pour les composants qui sont connectés fonction) est certainement.
OriginalL'auteur kquinn
Dans SciPy vous pouvez utiliser matrices creuses. Notez également qu'il existe des moyens plus efficaces de la multiplication de la matrice par elle-même. De toute façon, ce que vous essayez de faire, par par SVD de la décomposition.
Introduction avec des liens utiles.
C'est SVD (Singlular la Décomposition en Valeur). Fondamentalement, pour quelque chose d'aussi grand que des millions de nœuds, vous aurez besoin d'approximation de l'algorithme, plutôt que d'une seule (de clustering de graphe est un problème NP-complet). L'Article a eu des liens vers les articles expliquer de tels algorithmes.
BTW. êtes-vous essayer de réinventer le PageRank ou le FRAPPE?
Pas vraiment. En ce moment, tout le tri des données qui appartiennent à laquelle biologiques de la cellule. Dans fuure j'ai un équivalent problème qui finira par générer un moteur de recherche. Mais pas sur les pages. Et pas en utilisant des liens. (Ne peut pas en dire plus à ce stade 🙂 ). En tout cas, félicitations! Bien repéré, LOL.
L'Analyse de la Sémantique latente, alors? 😉 Ok, je ne vais pas tirer la langue. Il suffit de garder à l'esprit que ce qui est possible à petite échelle, devient vraiment compliqué quand c'est gros. La plupart des algorithmes sur les graphes ont hight polynôme de complexité, il est donc fissiles à utiliser, puis sur 1mln nœuds.
OriginalL'auteur vartec
Il y a aussi graph_tool et networkit qui ont efficace des routines pour les composants connectés, et à la fois de stocker le réseau de manière efficace. Si vous allez travailler avec des millions de nœuds, networkx ne sera probablement pas suffisant (c'est de la pure python autant que je sache). Ces deux outils sont écrits en C++ peut donc traiter l'analyse de grands graphes avec des temps d'exécution raisonnable.
Comme Phil points, votre méthode aura horriblement long temps de calcul pour les grands graphes (nous parlons des jours, des semaines, des mois...), et votre représentation graphique d'un million de nœuds aurez besoin de quelque chose comme un million de gigaoctets de mémoire!
OriginalL'auteur drevicko
Voici quelques implémentation naïve, qui trouve les composants connectés à l'aide de parcours en profondeur d'abord de recherche, je l'ai écrit il y a quelques temps. Même si c'est très simple, elle s'adapte bien à des dizaines de milliers de sommets et d'arêtes...
OriginalL'auteur
Comme d'autres l'ont souligné, pas besoin de réinventer la roue. Beaucoup de réflexion a été mis en optimale les techniques de clustering. Ici est un cas bien connu programme de clustering.
OriginalL'auteur RexE
Trouver une optimale graphique de la partition est un problème NP-difficile, donc quel que soit l'algorithme, il va y avoir un rapprochement ou d'une heuristique. Il n'est pas surprenant, différents algorithmes de clustering produire (sauvagement) des résultats différents.
Python de mise en œuvre de Newman, la modularité de l'algorithme:
la modularité
Aussi: MCL, MCODE, CFinder, NeMo, clusterONE
OriginalL'auteur lynxoid
Semble qu'il y est une bibliothèque PyMetis, qui sera la partition de votre graphique pour vous, une liste de liens. Il devrait être assez facile d'en extraire la liste des liens à partir de votre graphique en le passant à l'original de votre liste de nœuds (pas la matrice de multiplier les dérivés).
Effectuer plusieurs fois M' = MM ne sera pas efficace pour les grands ordres de M. de la matrice complète-multiplier pour les matrices d'ordre N coûtera N multiplications et N-1 additions par élément, dont il existe N2, qui est O(N3). Si vous êtes à la mise à l'échelle "des millions de nœuds", qui serait O(1018) opérations par multiplication matrice-matrice, de qui vous voulez faire plusieurs.
En bref, vous ne voulez pas faire de cette façon. Le SVD suggestion de Vartec serait le seul choix approprié. Votre meilleure option est d'utiliser simplement PyMetis, et de ne pas essayer de réinventer graphique de partitionnement.
Je pense que la clé est de décider si vous voulez vous renseigner sur le partitionnement assez de réécrire le logiciel (probablement pas), ou si vous voulez juste pour la partition d'un graphe. Si vous décidez d'utiliser les solutions existantes, choisissez une bibliothèque et de l'utiliser. Chercher à le résoudre au plus haut niveau.
J'ai essayé d'installer PyMetis, mais il semble avoir un moment difficile dans l'installation. Il semble y avoir un fichier de configuration. La recherche de la solution la plus simple je doit installer à la place networkx. Merci, Pietro
OriginalL'auteur Phil H
La SVD algorithme ne s'applique pas ici, mais sinon, Phil H est correct.
OriginalL'auteur