如何在 Python 中对图进行聚类?
-
19-08-2019 - |
题
设 G 是一个图。所以G是一组节点和一组链接。我需要找到一种快速的方法来划分图。我现在正在处理的图表只有 120*160 个节点,但我可能很快就会在另一个环境(不是医学,而是网站开发)中处理具有数百万个节点的等效问题。
因此,我所做的是将所有链接存储到图形矩阵中:
M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))
现在,如果节点 s 连接到节点 t,则 M 在位置 s,t 处保留 1。我确保 M 是对称的 M[s,t]=M[t,s] 并且每个节点链接到自身 M[s,s]=1。
如果我没记错的话,如果我将 M 乘以 M,结果是一个矩阵,表示连接通过两个步骤到达的顶点的图。
所以我继续将M与其自身相乘,直到矩阵中零的数量不再减少。现在我有了连接组件的列表。现在我需要对这个矩阵进行聚类。
到目前为止,我对这个算法非常满意。我认为它简单、优雅并且相当快。我在这部分遇到麻烦。
本质上,我需要将该图拆分为其连接的组件。
我可以遍历所有节点,看看它们连接到什么。
但是如何对矩阵进行排序并重新排序行呢?但我不知道是否可以做到。
以下是到目前为止的代码:
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)
编辑:
有人建议我使用SVD分解。这是 5x5 图上问题的一个简单示例。我们将使用它,因为使用 19200x19200 方阵不太容易看到簇。
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
这里基本上有 4 个集群:(0),(1,3),(2),(4),但我仍然看不到SVN在这种情况下如何提供帮助。
解决方案
为什么不使用真正的图形库,例如 Python图?它有一个 确定连通分量的函数 (尽管没有提供示例)。我想一个专用的库将会比你编写的任何临时图形代码更快。
编辑: 网络X 看起来它可能是比 python-graph 更好的选择;它是 文档(此处为连接组件功能) 当然是。
其他提示
下面是一些幼稚实现,它发现使用深度优先搜索时,我写前一段时间。虽然这是非常简单的,它扩展顶点以及上万和边......
import sys
from operator import gt, lt
class Graph(object):
def __init__(self):
self.nodes = set()
self.edges = {}
self.cluster_lookup = {}
self.no_link = {}
def add_edge(self, n1, n2, w):
self.nodes.add(n1)
self.nodes.add(n2)
self.edges.setdefault(n1, {}).update({n2: w})
self.edges.setdefault(n2, {}).update({n1: w})
def connected_components(self, threshold=0.9, op=lt):
nodes = set(self.nodes)
components, visited = [], set()
while len(nodes) > 0:
connected, visited = self.dfs(nodes.pop(), visited, threshold, op)
connected = set(connected)
for node in connected:
if node in nodes:
nodes.remove(node)
subgraph = Graph()
subgraph.nodes = connected
subgraph.no_link = self.no_link
for s in subgraph.nodes:
for k, v in self.edges.get(s, {}).iteritems():
if k in subgraph.nodes:
subgraph.edges.setdefault(s, {}).update({k: v})
if s in self.cluster_lookup:
subgraph.cluster_lookup[s] = self.cluster_lookup[s]
components.append(subgraph)
return components
def dfs(self, v, visited, threshold, op=lt, first=None):
aux = [v]
visited.add(v)
if first is None:
first = v
for i in (n for n, w in self.edges.get(v, {}).iteritems()
if op(w, threshold) and n not in visited):
x, y = self.dfs(i, visited, threshold, op, first)
aux.extend(x)
visited = visited.union(y)
return aux, visited
def main(args):
graph = Graph()
# first component
graph.add_edge(0, 1, 1.0)
graph.add_edge(1, 2, 1.0)
graph.add_edge(2, 0, 1.0)
# second component
graph.add_edge(3, 4, 1.0)
graph.add_edge(4, 5, 1.0)
graph.add_edge(5, 3, 1.0)
first, second = graph.connected_components(op=gt)
print first.nodes
print second.nodes
if __name__ == '__main__':
main(sys.argv)
正如其他人指出的那样,没有必要重新发明轮子。花了很多心思已经投入最佳的聚类技术。 这里是一个公知的聚类程序。
在SVD算法在这里不适用,但在其他菲尔H是正确的。