Network (graph)

A network (graph) called in graph theory is a set of nodes (company, author, actor) $ V $ and a link (business relationship, as seen in the business relationship of a company, the co-authorship relationship of a paper, and the co-starring relationship of an actor. It is a pair of set $ E $ of co-authorship and co-starring), and is expressed as $ G = (V, E) $. Also, here we deal with simple graphs (graphs that do not have self-loops or multiple edges).

As an example, the network $ G $ in which company A and company B have a business relationship and company B and company C have a business relationship is illustrated. The network generation function uses python's networkx.

import networkx as nx

G = nx.Graph()

G.add_edge('A', 'B')
G.add_edge('B', 'C')

nx.draw_networkx(G)

Adjacency matrix

The adjacency matrix is a matrix format that shows which node the link of the graph is connected to.

A = \Bigr(\,A_{ij}\,\Bigr) =\left\{
\begin{array}{ll}
1 & (if\,node\,j\,and\,i\,is\,connected) \\
0 & (otherwise)
\end{array}
\right.

The adjacency matrix of the example is as follows.

adjacency = nx.to_numpy_array(G)
print(adjacency)
#array([[0., 1., 0.],
#       [1., 0., 1.],
#      [0., 1., 0.]])

When the network is undirected, the adjacency matrix is ** symmetric matrix **.

A_{ij} = A_{ji} \;(if \,G\,is\,undirected)

Degree

The degree $ k_i $ is the total number of links to which the node $ i $ is connected. In other words, it is the sum of the columns (or rows) of the adjacency matrix.

k_i = \sum_{l=1}A_{il}

Each order of the example is as follows.

import numpy as np

degree = np.sum(adjacency, axis=1)
print(degree)
#array([1., 2., 1.])

A matrix $ D $ in which the values of each degree are diagonal components is called a ** degree matrix **.

D = \Bigr(\,D_{ij}\,\Bigr) =\left\{
\begin{array}{ll}
k_i &
(i = j) \\
0 & (i ≠ j)
\end{array}
\right.

Also, [Handshake Supplement](https://ja.m.wikipedia.org/wiki/%E6%AC%A1%E6%95%B0_(%E3%82%B0%E3%83%A9%E3%83) % 95% E7% 90% 86% E8% AB% 96))) means that:

\sum_{i=1}k_i = 2|E|

print(np.sum(degree))
#4.0

** Average order ** is the average value of links extending from a certain node. In other words, if the number of nodes in the network is $ n $

<k> = \frac{\sum_{i=1}k_i}{n} = \frac{2|E|}{n}

Laplacian matrix

The Laplacian matrix $ L $ is the difference between the degree matrix and the adjacency matrix.

L = D - A

Since the degree matrix $ D $ is $ 0 $ other than the diagonal component, $ L $ is also a ** symmetric matrix ** when $ G $ is an undirected network.

The example Laplacian matrix is

laplacian = nx.laplacian_matrix(G)
print(laplacian)#Sparse Matrix
#  (0, 0)	1
#  (0, 1)	-1
#  (1, 0)	-1
#  (1, 1)	2
#  (1, 2)	-1
#  (2, 1)	-1
#  (2, 2)	1

Inverse matrix of Laplacian matrix

The Laplacian matrix is not an invertible matrix. This is because the sum of the columns (or rows) of the Laplacian matrix is all 0.

Therefore, a pseudo inverse matrix is created using singular value decomposition. Since the Laplacian matrix is a symmetric matrix, eigenvalue decomposition is used.

L = P\, \Lambda \,P^T

Where $ P = \ bigr (, P_i , \ bigr) $ corresponds to the eigenvalue $ \ lambda _i $ It is a matrix of the eigenvector $ P _i $ that has been orthonormalized.

Therefore, when considering the inverse matrix of $ L $, consider the ** eigenvalue **.

Eigenvalues of Laplacian matrix

Find the eigenvalues of the example.

laplacian = laplacian.toarray() # sparse to array
eig = np.linalg.eigh(laplacian)
print(eig)
#array([9.99658224e-17, 1.00000000e+00, 3.00000000e+00])

Here, consider the Laplacian matrix in a ** complex network ** (a network with a large number of nodes and links). The model used here is Erdős–Rényi model (model that probabilistically generates links) Is. Adjust the number of nodes to 5000 and the average order to 10.

n = 5000
p = 10 / n

Ger = nx.fast_gnp_random_graph(n, p)

laplacian = nx.laplacian_matrix(Ger)
laplacian = laplacian.toarray()

eig = np.linalg.eigh(laplacian)

The obtained eigenvalues are represented by a histogram.

import matplotlib.pyplot as plt

plt.hist(eig[0], bins=100)
plt.show()

In this way, it can be seen that there is one eigenvalue 0. In addition, all eigenvalues other than 0 eigenvalues take positive values, and regularity can be read in the distribution of eigenvalues.

Therefore, the regularity of the inverse matrix of the Laplacian matrix should be read in this model as well.

References

『Network Science by Albert-László Barabási』（http://networksciencebook.com) 『Laplacian Matrix』（https://www.sciencedirect.com/topics/computer-science/laplacian-matrix ） Howard Anton (1979) "Anton's Easy Linear Algebra" Translated by Junichi Yamashita, Hyundai Mathematics Co., Ltd.

[PYTHON] Distribution of eigenvalues of Laplacian matrix