用Numpy数组表示图

Question

我正在接收以下格式的数据：

tail head
P01106  Q09472
P01106  Q13309
P62136  Q13616
P11831  P18146
P13569  P20823
P20823  P01100
...

有没有一种很好的方法将此数据格式化为带有numpy数组的图形？我希望使用此图计算PageRank。

到目前为止，我有

import numpy as np
data = np.genfromtxt('wnt_edges.txt', skip_header=1, dtype=str)

我当时在考虑使用Python中的“表示图形（数据结构）”中的图形数据结构，但在这种情况下似乎没有任何意义，因为我将进行矩阵乘法。

Answer 1

为了避免重新发明轮子，您应该按照注释和其他答案中的建议使用networkx。

如果出于教育目的，您想重新发明轮子，则可以创建一个邻接矩阵。所述的PageRank可以从该矩阵来计算：

PageRank值是修改后的邻接矩阵的主要右特征向量的条目。

由于邻接矩阵的每一行/列都代表一个节点，因此您需要枚举这些节点，以便每个节点都由一个从0开始的唯一数字表示。

import numpy as np

data = np.array([['P01106', 'Q09472'],
                 ['P01106', 'Q13309'],
                 ['P62136', 'Q13616'],
                 ['P11831', 'P18146'],
                 ['P13569', 'P20823'],
                 ['P20823', 'P01100']])


nodes = np.unique(data)  # mapping node name --> index
noidx = {n: i for i, n in enumerate(nodes)}  # mapping node index --> name

n = nodes.size  # number of nodes

numdata = np.vectorize(noidx.get)(data)  # replace node id by node index

A = np.zeros((n, n))
for tail, head in numdata:
    A[tail, head] = 1
    #A[head, tail] = 1  # add this line for undirected graph

这将导致以下图形表示A：

array([[ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.]])

例如，第5行第1列的0表示从节点5到节点0有一条边，对应于'P20823'-> 'P01100'。使用nodes数组从索引中查找节点名称：

print(nodes)
['P01100' 'P01106' 'P11831' 'P13569' 'P18146' 'P20823' 'P62136' 'Q09472'
 'Q13309' 'Q13616']

如果节点很多，连接很少，最好使用sparse matrixfor A。但是，首先尝试使用密集矩阵，并且只有在切换到稀疏状态时才会遇到内存或性能问题。