Hermitian Adjacency Matrix of Digraph

Question

I am trying to find a pythonic way to calculate the Hermitian adjacency matrix in Python and I'm really struggling. The definition of a Hermitian Adjacency matrix is shown in this image:

It works as follows. Lets say we have two nodes named i and j. If there is an directed edge going from both i to j and j to i, then the corresponding matrix value at location [ i, j ] should be set to 1. If there is only a directed edge from i to j, then the matrix element at location [i, j] should be set to +i. And if there is only a directed edge from j to i then the matrix element at location [i, j] should be set to -i. All other matrix values are set to 0.

I cannot figure out a smart way to make this Hermitian Adjacency Matrix that doesn't involve iterating through my nodes one by one. Any advice?

Answer 1

I don't think there's a built-in for this, so I've cobbled together my own vectorised solution:

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)

Explanation

Let's start with a directed graph:

We start by creating the normal adjacency matrix using nx.linalg.graphmatrix.adjacency_matrix(), giving us the following 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]]

We can then add this matrix to its transpose, giving us 2 in every location where there is a directed edge going from i to j and vice-versa, a 1 in every location where only one of these edges exists, and a 0 in every location where no edge exists:

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

Now, we want to apply a function to the matrix so that 0 maps to 0, 2 maps to 1, and 1 maps to the row number i. We can use np.indices() to get the row number, and the following equation: x/2 * (2*i)**(x%2), where i is the row number and x is the element. Finally, we need to multiply elements in positions where no edge ij exists by -1. This can be vectorised as follows:

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

As required.

We can check that this is correct by using a naïve iterate-through-nodes approach:

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