[PYTHON] Distribution des valeurs propres de la matrice laplacienne

Réseau (graphique)

Le réseau (graphe) appelé dans la théorie des graphes est un ensemble de nœuds (entreprise, auteur, acteur) et un lien (relation commerciale, vue dans la relation commerciale d'une entreprise, la relation de co-auteur d'un article et la relation de co-vedette d'un acteur). C'est une paire de l'ensemble $ E $ de co-auteur et de co-vedette), et est exprimé comme $ G = (V, E) $. Aussi, nous traitons ici des graphiques simples (graphiques qui n'ont pas d'auto-boucles ou de côtés multiples).

A titre d'exemple, le réseau $ G $ dans lequel la société A et la société B entretiennent une relation commerciale et la société B et la société C entretiennent une relation commerciale est illustré. La fonction de génération de réseau utilise networkx de python.

import networkx as nx

G = nx.Graph()

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

nx.draw_networkx(G)

Matrice adjacente

La matrice adjacente est un format de matrice qui montre à quel nœud le lien du graphique est connecté.

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

La matrice adjacente de l'exemple est la suivante.

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

Lorsque le réseau n'est pas orienté, la matrice adjacente est une ** matrice symétrique **.

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

Commande

La commande $ k_i $ est le nombre total de liens auxquels le nœud $ i $ est connecté. En d'autres termes, c'est la somme des colonnes (ou lignes) de la matrice adjacente.

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

L'ordre de chaque exemple est le suivant.

import numpy as np

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

Une matrice $ D $ dans laquelle les valeurs de chaque ordre sont des composantes diagonales est appelée une ** matrice d'ordre **.

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

En outre, [Supplément de prise de contact](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)), et les conditions suivantes sont maintenues.

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

print(np.sum(degree))
#4.0

** Ordre moyen ** est la valeur moyenne des liens s'étendant à partir d'un certain nœud. En d'autres termes, si le nombre de nœuds du réseau est $ n $

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

Matrice laplacienne

La matrice laplacienne $ L $ est la différence entre la matrice d'ordre et la matrice adjacente.

L = D - A

Puisque la matrice d'ordre $ D $ est $ 0 $ autre que la composante diagonale, $ L $ est également une ** matrice symétrique ** lorsque $ G $ est un réseau non dirigé.

L'exemple de matrice laplacienne est

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 de la matrice laplacienne

La matrice laplacienne n'est pas une matrice régulière. La somme des colonnes (ou lignes) de la matrice laplacienne est entièrement égale à 0.

Par conséquent, une matrice pseudo inverse est créée en utilisant une décomposition en valeurs singulières. La matrice laplacienne étant une matrice symétrique, la décomposition en valeurs propres est utilisée.

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

Où $ P = \ bigr (, P_i , \ bigr) $ correspond à la valeur unique $ \ lambda _i $ C'est une matrice du vecteur propre $ P _i $ qui a subi une orthogonalisation normale.

Par conséquent, en considérant la matrice inverse de $ L $, considérez ** valeur propre **.

Valeur unique de la matrice laplacienne

Trouvez la valeur propre de l'exemple.

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

Considérons ici la matrice laplacienne en ** réseau complexe ** (réseau avec un grand nombre de nœuds et de liens). Le modèle utilisé ici est le modèle Erdős – Rényi (modèle qui génère des liens de manière probabiliste) Est. Ajustez le nombre de nœuds à 5000 et l'ordre moyen à 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)

Les valeurs propres obtenues sont représentées par un histogramme.

import matplotlib.pyplot as plt

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

De cette manière, on peut voir qu'il existe une valeur propre de 0. De plus, toutes les valeurs propres autres que 0 valeurs propres prennent des valeurs positives et la régularité peut être lue dans la distribution des valeurs propres.

Par conséquent, la régularité de la matrice inverse de la matrice laplacienne doit également être lue dans ce modèle.

Les références

『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" Traduit par Junichi Yamashita, Hyundai Mathematics Co., Ltd.