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

Question

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

节点是字符串。

例如：

苹果香蕉 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  

捷径：使用networkx

让我们首先加载 networkx 包

import networkx

然后，从data我们将边缘列表作为列表列表：

edgeList = data.values.tolist()

这样，我们得到

In [19]: edgeList
Out[19]: [['Apple', 'Banana', 65], ['Orange', 'Apple', 32]]

让我们创建一个空的(有向)图G：

G = networkx.DiGraph()

然后我们用一个简单的 for 循环添加边缘：

for i in range(len(edgeList)):
G.add_edge(edgeList[i][0], edgeList[i][1], weight=edgeList[i][2])

我们可以轻松地将邻接矩阵检索为

A = networkx.adjacency_matrix(G).A

读作一个简单明了的numpy数组

In [30]: A
Out[30]:
array([[ 0, 65,  0],
[ 0,  0,  0],
[32,  0,  0]], dtype=int64)

注：上述邻接矩阵是指加权和有向图(即从苹果到香蕉存在一条边，但从香蕉到苹果没有边)。如果需要加权和无向图(即，如果从Apple到Banana存在一条边，那么从Banana到Apple存在一条边)，只需使用

G = networkx.Graph()

而不是

G = networkx.DiGraph()

漫长的路：手动

让我们采用第一列和第二列来收集节点 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存在一条边)，只需转置上面的邻接矩阵

M_symmetric = M + M.T 

哪里

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