Netzwerk (Grafik)

Das in der Graphentheorie aufgerufene Netzwerk (Graph) besteht aus einer Reihe von Knoten (Unternehmen, Autor, Akteur) und einer Verknüpfung (Geschäftsbeziehung, wie sie in der Geschäftsbeziehung eines Unternehmens gesehen wird, der Koautorenbeziehung eines Papiers und der Co-Star-Beziehung eines Akteurs). Es ist ein Paar der Menge $ E $ (Co-Autorschaft und Co-Star) und wird ausgedrückt als $ G = (V, E) $. Auch hier beschäftigen wir uns mit einfachen Graphen (Graphen, die keine Selbstschleifen oder mehrere Seiten haben).

Als Beispiel wird das Netzwerk $ G $ dargestellt, in dem Unternehmen A und Unternehmen B eine Geschäftsbeziehung haben und Unternehmen B und Unternehmen C eine Geschäftsbeziehung haben. Die Netzwerkgenerierungsfunktion verwendet networkx von Python.

import networkx as nx

G = nx.Graph()

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

nx.draw_networkx(G)

Benachbarte Matrix

Die benachbarte Matrix ist ein Matrixformat, das zeigt, mit welchem Knoten die Verknüpfung des Graphen verbunden ist.

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

Die benachbarte Matrix des Beispiels ist wie folgt.

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

Wenn das Netzwerk ungerichtet ist, ist die benachbarte Matrix eine ** symmetrische Matrix **.

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

Auftrag

Die Reihenfolge $ k_i $ ist die Gesamtzahl der Links, mit denen der Knoten $ i $ verbunden ist. Mit anderen Worten ist es die Summe der Spalten (oder Zeilen) der benachbarten Matrix.

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

Die Reihenfolge der einzelnen Beispiele ist wie folgt.

import numpy as np

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

Eine Matrix $ D $, in der die Werte jeder Ordnung diagonale Komponenten sind, wird als ** Ordnungsmatrix ** bezeichnet.

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

Auch [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)), und das Folgende gilt.

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

print(np.sum(degree))
#4.0

** Durchschnittliche Reihenfolge ** ist der Durchschnittswert von Links, die sich von einem bestimmten Knoten aus erstrecken. Mit anderen Worten, wenn die Anzahl der Knoten im Netzwerk $ n $ beträgt

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

Laplace-Matrix

Die Laplace-Matrix $ L $ ist die Differenz zwischen der Ordnungsmatrix und der benachbarten Matrix.

L = D - A

Da die Ordnungsmatrix $ D $ außer der diagonalen Komponente $ 0 $ ist, ist $ L $ auch eine ** symmetrische Matrix **, wenn $ G $ ein ungerichtetes Netzwerk ist.

Die beispielhafte Laplace-Matrix ist

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 der Laplace-Matrix

Die Laplace-Matrix ist keine reguläre Matrix. Dies liegt daran, dass die Summe der Spalten (oder Zeilen) der Laplace-Matrix alle 0 ist.

Daher wird eine pseudoinverse Matrix unter Verwendung einer Singularwertzerlegung erzeugt. Da die Laplace-Matrix eine symmetrische Matrix ist, wird eine Eigenwertzerlegung verwendet.

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

Wobei $ P = \ bigr (, P_i , \ bigr) $ dem eindeutigen Wert $ \ lambda _i $ entspricht Es ist eine Matrix des Eigenvektors $ P _i $, die eine normale Orthogonalisierung erfahren hat.

Berücksichtigen Sie daher bei der Betrachtung der inversen Matrix von $ L $ den ** Eigenwert **.

Eindeutiger Wert der Laplace-Matrix

Finden Sie den Eigenwert des Beispiels.

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

Betrachten Sie hier die Laplace-Matrix in einem ** komplexen Netzwerk ** (Netzwerk mit einer großen Anzahl von Knoten und Verbindungen). Das hier verwendete Modell ist Erdős-Rényi-Modell (Modell, das wahrscheinlich Links generiert) Ist. Passen Sie die Anzahl der Knoten auf 5000 und die durchschnittliche Reihenfolge auf 10 an.

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)

Die erhaltenen Eigenwerte werden durch ein Histogramm dargestellt.

import matplotlib.pyplot as plt

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

Auf diese Weise ist ersichtlich, dass es einen Eigenwert von 0 gibt. Außerdem nehmen alle Eigenwerte außer 0 Eigenwerten positive Werte an, und die Regelmäßigkeit kann bei der Verteilung der Eigenwerte abgelesen werden.

Daher sollte auch in diesem Modell die Regelmäßigkeit der inversen Matrix der Laplace-Matrix gelesen werden.

Verweise

『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) "Antons einfache lineare Algebra" Übersetzt von Junichi Yamashita, Hyundai Mathematics Co., Ltd.

[PYTHON] Verteilung der Eigenwerte der Laplace-Matrix