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.

Pourriez-vous préciser votre question. J'ai trouvé un "est-il possible" (ce qui est toujours répondu Oui, donc ça ne peut pas être votre vraie question) et une "je ne vois pas comment SVD peut aider à" ce qui n'est pas une vraie question. Quelle est votre question?
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