有向图的厄米邻接矩阵

Question

我正在尝试找到一种Python式的方法来计算Python中的埃尔米特邻接矩阵，但我真的很挣扎。埃尔米特邻接矩阵的定义如下图所示：

其工作原理如下。假设我们有两个名为

i

和

j

的节点。如果存在从

i to j

和

j to i

出发的有向边，则位置 [ i, j ] 处对应的矩阵值应设置为 1。如果仅存在来自

i to j

的有向边，则位置 [i, j] 处的矩阵元素应设置为 +i。如果仅存在来自

j to i

的有向边，则位置 [i, j] 处的矩阵元素应设置为 -i。所有其他矩阵值均设置为 0。

我无法找到一种明智的方法来制作这个埃尔米特邻接矩阵，该矩阵不涉及逐个迭代我的节点。有什么建议吗？

Answer 1

我认为没有内置功能，所以我拼凑了自己的矢量化解决方案：

import numpy as np
import networkx as nx

# Create standard adjacency matrix
A = nx.linalg.graphmatrix.adjacency_matrix(G).toarray()

# Add to its transpose and convert from sparse array
B = A + A.T

# Get row index matrix
I = np.indices(B.shape)[0] + 1

# Apply vectorised formula to get Hermitian adjacency matrix
H = np.multiply(B/2 * (2*I)**(B%2), 2*A-1).astype(int)

说明

让我们从有向图开始：

我们首先使用

nx.linalg.graphmatrix.adjacency_matrix()

创建法线邻接矩阵，得到以下矩阵：

>>> A = nx.linalg.graphmatrix.adjacency_matrix(G).toarray()
[[1, 1, 0, 1, 0, 1, 0, 0],
 [1, 0, 0, 1, 0, 0, 1, 0],
 [1, 1, 1, 1, 0, 1, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 1, 0, 0, 0, 0],
 [1, 1, 0, 0, 1, 0, 1, 1],
 [0, 1, 0, 0, 1, 0, 0, 1],
 [0, 0, 0, 0, 1, 0, 0, 0]]

然后我们可以将此矩阵添加到其转置中，在每个有来自

2

的有向边的位置上给出

i to j

，反之亦然，在仅存在这些边之一的每个位置上给出

1

，在每个不存在边缘的位置都有一个

0

：

>>> B = A + A.T
>>> B
[[2, 2, 1, 1, 1, 2, 0, 0],
 [2, 0, 1, 2, 0, 1, 2, 0],
 [1, 1, 2, 1, 0, 1, 0, 0],
 [1, 2, 1, 0, 1, 0, 0, 0],
 [1, 0, 0, 1, 0, 1, 1, 1],
 [2, 1, 1, 0, 1, 0, 1, 1],
 [0, 2, 0, 0, 1, 1, 0, 1],
 [0, 0, 0, 0, 1, 1, 1, 0]]

现在，我们要对矩阵应用一个函数，以便

0

映射到

0

，

2

映射到

1

，

1

映射到行号

i

。我们可以使用

np.indices()

来获取行号，以及以下等式：

x/2 * (2*i)**(x%2)

，其中

i

是行号，

x

是元素。最后，我们需要将不存在边

ij

的位置的元素乘以

-1

。这可以向量化如下：

>>> I = np.indices(B.shape)[0] + 1
>>> H = np.multiply(B/2 * (2*I)**(B%2), 2*A-1).astype(int)
>>> H
[[ 1,  1, -1,  1, -1,  1,  0,  0],
 [ 1,  0, -2,  1,  0, -2,  1,  0],
 [ 3,  3,  1,  3,  0,  3,  0,  0],
 [-4,  1, -4,  0, -4,  0,  0,  0],
 [ 5,  0,  0,  5,  0, -5, -5, -5],
 [ 1,  6, -6,  0,  6,  0,  6,  6],
 [ 0,  1,  0,  0,  7, -7,  0,  7],
 [ 0,  0,  0,  0,  8, -8, -8,  0]]

按要求。

我们可以通过使用简单的迭代节点方法来检查这是否正确：

>>> check = np.zeros([8,8])
>>> for i in G.nodes:
        for j in G.nodes:
            if (i, j) in G.edges:
                if (j, i) in G.edges:
                    check[i-1, j-1] = 1
                else:
                    check[i-1, j-1] = i
            else:
                if (j, i) in G.edges:
                    check[i-1, j-1] = -i
                else:
                    check[i-1, j-1] = 0
>>> (check == H).all()
True