네트워킹(차트)

그래프 이론에서 말하는 네트워크(그래프)는 회사의 거래 관계, 논문의 공저 관계, 배우의 공동 합작 관계에서 보이는 노드(회사, 작가, 배우)의 집합 $V달러와 링크(거래 관계, 공저 관계, 공동 공연)의 집합 $E의 한 쌍을 말한다.$G=(V,E)$. 그리고 간단한 도표를 처리합니다. (자기 순환과 다각적인 도표는 존재하지 않습니다.)
예를 들어 A회사와 B회사가 업무관계가 있고 B회사와 C회사가 업무관계가 있는 네트워크는 $G$G이다.
네트워크에서 생성된 함수는python의networkx를 사용합니다.

import networkx as nx

G = nx.Graph()

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

nx.draw_networkx(G)

인접 행렬

인접 행렬은 행렬 형식으로 도표 링크가 어느 노드와 연결되었는지 나타낸다.

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

그 인접한 대열은 아래와 같다.

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

네트워크가 방향을 정하지 않을 때, 인접 행렬은 대칭 행렬이다.

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

순서

단계 $ki$i, 노드를 연결하는 $i$i 링크의 총 수입니다.
즉 인접한 행렬의 열(또는 행)의 합이다.

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

예의 각 횟수는 다음과 같다.

import numpy as np

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

각 단계의 값은 대각 컴포넌트의 행렬이 됩니다$D$를 보조 행렬이라고 합니다.

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

또 아래는 악수로 구성됐다.

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

print(np.sum(degree))
#4.0

평균 단계는 어느 노드에서 연장된 체인의 평균값이다. 즉, 네트워크의 노드 수는 $n이다.

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

Laplaacian 매트릭스

라프라스 매트릭스 $L$L은 단계 매트릭스와 인접 매트릭스 사이의 차 매트릭스입니다.

L = D - A

매트릭스 $D$는 대각 성분 이외의 $0이기 때문에 $L과 $G가 비정상적인 네트워크일 때 대칭 매트릭스입니다.
그 라프라스 행렬은,

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

Laplaacian 매트릭스의 역 매트릭스

Laplaacian 매트릭스는 정규 매트릭스가 아닙니다.
따라서 기이한 값 분해를 사용하여 위역 행렬을 생성한다.
Laplaacian 매트릭스는 대칭 매트릭스이기 때문에 피쳐 값을 사용하여 분해합니다.

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

여기 $P=\bigr(\,P i\,\bigr)$는 고정값$\lambad대응
정규 정교화 고유 벡터 $P 진행줄을 서다.
따라서 $L의 역행렬을 고려할 때 피쳐 값을 고려할 수 있습니다.

Laplaacian 매트릭스의 특징 값

예를 구하는 것은 가치가 있다.

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

여기에는 복잡한 네트워크(노드 수, 링크 수가 큰 네트워크)의 Laplaacian 행렬이 고려됩니다.
여기에 사용된 모델은 Erdős–Rényi model(랜덤으로 체인을 생성하는 모델)이다.
노드 수 5000, 평균 단계 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)

직사각형으로 얻은 특징치를 표시하다.

import matplotlib.pyplot as plt

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

이를 통해 알 수 있듯이 하나의 특징값 0이 존재하는데 0특징값 이외의 특징값은 모두 양수를 취하고 특징값의 분포도 규칙성을 읽을 수 있다.
따라서 이 모델에서 라프라스 행렬의 역 행렬도 규칙성을 읽을 수 있다.

참고 문헌

『Network Science by Albert-László Barabási』( http://networksciencebook.com )
『Laplacian Matrix』( https://www.sciencedirect.com/topics/computer-science/laplacian-matrix )
호화드 앤턴(1979) 산하순역, 현대수학사