在Python中如何将加权边列表转换为邻接矩阵？

Question

数据存在于excel文件中，第一列表示第一个节点，第二列表示第二个节点，第三列包含权重。在

节点是字符串。在

例如：

Apple Banana 65
Orange Apple 32

Answer 1

首先要做的是导入Excel文件。最简单的方法是使用pandas：

import pandas
data = pandas.read_excel("path/to/edgelist", header=None)

这将返回窗体的数据帧

^{pr2}$

让我们用第一列和第二列来收集节点ID

nodes = data.iloc[:, 0].tolist() + data.iloc[:, 1].tolist()

因此

In [4]: nodes
Out[4]: [u'Apple', u'Orange', u'Banana', u'Apple']

让我们排序并删除重复项（排序无论如何都不是强制的）

nodes = sorted(list(set(nodes)))

并且nodes现在有了

In [8]: nodes
Out[8]: [u'Apple', u'Banana', u'Orange']

让我们用一个连续的数字ID映射每个节点（字符串），以提供邻接矩阵

nodes = [(i,nodes[i]) for i in range(len(nodes))]

并且nodes现在有了

In [10]: nodes
Out[10]: [(0, u'Apple'), (1, u'Banana'), (2, u'Orange')]

现在字符串到整数的映射已经完成，让我们在原始数据帧（data）中用其对应的ID替换每个字符串

In [15]: for i in range(len(nodes)):
    ...:     data = data.replace(nodes[i][1], nodes[i][0])

现在data的形式是

In [16]: data
Out[16]:
   0  1   2
0  0  1  65
1  2  0  32

所以您可以看到，Apple的每一次出现都被0替换了，Banana的每一次出现都被1替换了，并且每一次出现的od Orange都被替换为2（根据变量nodes）。在

为了构建邻接矩阵，让我们导入另一个众所周知的包（scipy）

from scipy.sparse import coo_matrix 

并创建一个coordinate-based sparse matrix

M = coo_matrix((data.iloc[:,2], (data.iloc[:,0],data.iloc[:,1])), shape=(len(nodes), len(nodes)))

这将创建一个稀疏的邻接矩阵（对于节点多、边少的图形，内存占用较少）。如果你需要一个稠密的邻接矩阵，那么

M = M.todense()

其中M的最后一个形式是

matrix([[ 0, 65,  0],
        [ 0,  0,  0],
        [32,  0,  0]])

注：上述邻接矩阵指的是一个加权有向图（即从苹果到香蕉存在一条边，但从香蕉到苹果没有边）。如果需要一个加权无向图（也就是说，如果从苹果到香蕉存在一条边，那么从香蕉到苹果存在一条边），只需将上述邻接矩阵转置即可

M_symmetric = M + M.T 

在哪里

In [38]: M_symmetric
Out[38]:
matrix([[ 0, 65, 32],
        [65,  0,  0],
        [32,  0,  0]])