有向图的埃尔米特邻接矩阵

Question

我正在尝试寻找一种 pythonic 方法来计算 Python 中的 Hermitian 邻接矩阵，但我真的很挣扎。 Hermitian 邻接矩阵的定义如下图所示：

它的工作原理如下。假设我们有两个名为 i 和 j 的节点。如果从 i to j 和 j to i 都有一条有向边，则位置 [ i, j ] 处的相应矩阵值应设置为 1。如果从i to j只有一条有向边，那么位置[i,j]处的矩阵元素应该设置为+i。如果只有来自 j to i 的有向边，则位置 [i, j] 处的矩阵元素应设置为 -i。所有其他矩阵值都设置为 0。

我想不出一个聪明的方法来制作这个 Hermitian 邻接矩阵，它不涉及一个接一个地遍历我的节点。有什么建议吗？

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]]

然后我们可以将这个矩阵添加到它的转置中，在每个有从 i to j 有向边的位置给我们 2，反之亦然，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

有向图的埃尔米特邻接矩阵

Hermitian Adjacency Matrix of Digraph

graph-theory

networkx

python-3.x

说明