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

Question

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

节点是字符串。

例如：

Apple Banana 65 橙苹果32

Answer 1

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

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

这将返回表单的数据框

In [2]: data  
Out[2]:  
        0       1   2  
0   Apple  Banana  65  
1  Orange   Apple  32

让我们采用第一列和第二列来收集节点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替换，每次出现的Orange都被2替换（根据变量nodes）。

为了构建邻接矩阵，让我们导入另一个着名的包（scipy）

from scipy.sparse import coo_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]])

注意：上面的邻接矩阵指的是加权和有向图（即，从Apple到Banana的边缘存在，但是从Banana到Apple没有边缘）。如果需要加权和无向图（即，如果存在从Apple到Banana的边缘，那么从Banana到Apple存在边缘），只需转置上述邻接矩阵

M_symmetric = M + M.T

哪里

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