UNIT 38 그래프 분해하기

용어 정리

그래프 : 에지로 연결된 노드의 묶음
방향 그래프 : 그래프 안의 에지 중 하나라도 방향이 있는 그래프 (방향이란 A 노드에서 B 노드로는 연결되지만 그 반대는 성립되지 않는 경우)
멀티 그래프 : 그래프에 평행 에지들이 있는 그래프 (평행 에지란 노드 사이에 에지가 2개 이상 있는 경우)
가중치 그래프 : 가중치를 부여한 에지로 구성된 그래프, 가중치가 클수록 노드간 연결이 강하다.
노드의 차수(degree) : 그 노드에 연결된 에지의 개수. 방향 그래프에서는 입력 차수와 출력 차수의 계산이 가능
그래프 밀도 : 해당 그래프가 완전 그래프에 얼마나 가까운지 나타내는 지표. 완전 그래프란 모든 노드가 서로 연결되어 있는 그래프

방향 그래프 밀도 : $d = \frac{e}{n(n-1)}$ (e = 에지, n = 노드)

무방향 그래프 밀도 : $d = \frac{2e}{n(n-1)}$ (e = 에지, n = 노드)
그래프 행보(graph walk) : 하나의 에지 끝이 다른 에지의 시작으로 이어지는 에지의 시퀀스
경로(path) : 중복되지 않는 행보
루프(loop) : 폐쇄된 경로
(노드 사이의) 거리 : 두 노드를 연결하는데 필요한 최소한의 에지 개수(가중치가 있는 그래프에서는 이 정의가 통하지 않으며, 방향 그래프에서는 A-B의 거리가 B-A의 거리와 같지 않을 수도 있다)
그래프의 지름(diameter) : 두 노드간의 가장 먼 거리
(연결된) 컴포넌트 : 그래프 안에서 서로 경롤로 연결된 노드의 집합
거대하게 연결된 컴포넌트(GCC, Giant Connected Component) : 그래프 내에서 가장 큰 컴포넌트
브리지(bridge) : 그래프의 두 부분을 하나의 에지만 제거해서 반으로 자를 수 있을 때 그 에지를 브리지라고 함
클릭(clique) : 모든 노드가 서로 직접적으로 연결된 노드의 집합. 가장 큰 클릭은 최대 클릭, 더이상 다른 노드를 더해 확장할 수 없는 경우 극대 클릭. 완전그래프는 극대 클릭이다.
스타(star) : 하나의 노드가 다른 모든 노드에 연결되지만 다른 노드들은 서로 연결되지 않는 노드의 집합
이웃(neighborhood) : 노드 A에 직접적으로 연결된 모든 노드의 집합을 이웃이라 하며 G(A)로 표시한다.스노우볼링(snowballing)이라는 데이터 수집 기법의 핵심
스노우볼링(snowballing) : 무작위로 추출한 노드에서 에지를 따라 그 이웃으로, 또 그 이웃의 이웃(2차 이웃)으로 이동하며 데이터를 수집하는 기법
(로컬)클러스터링 계수(local clustering coefficient) : A에 직접 연결된 에지를 제외한 A의 모든 이웃의 에지 개수를 최대로 가능한 에지 개수로 나눈 값. 즉, A를 제외한 A의 이웃 그래프의 밀도. CC(A)로 표시
네트워크 커뮤니티 : 집합에서 노드 간 에지 개수가 집합 경계를 가로지르는 에지 개수보다 많은 노드의 집합

중심성

연결 중심성

A의 연결 중심성(degree centrality)은 A의 이웃 노드 개수로 A의 차수나 G(A) 크기와 같다. A가 가질 수 있는 가장 많은 이웃 수(n-1)로 나누어 스케일을 조정할 수 있다.

근접 중심성

A의 근접 중심성(closeness centrality)은 다른 모든 노드에서 A로 연결된 가장 짧은 경로의 평균 길이 $L_{AB}$에 역수를 취한 값이다.

$CC_{A} = \frac{n-1}{\sum_{B \ne A}^{}L_{BA}}$

매개 중심성

A의 매개 중심성(betweenness centrality)은 A를 제회한 모든 노드 쌍의 가장 짧은 경로 중에서 A를 포함하는 경로의 비율.

고유벡터 중심성

A의 고유벡터 중심성(eigenvector centrality)은 A에 근접한 모든 이웃의 고유벡터 중심성의 스케일된 합으로, 재귀적으로 구한다.

$ec_{A} = \frac{1}{\lambda}{\sum_{B \in G(A)}^{}ec_{B}}$

이전Swift - Swift의 guard문

다음Spring - bean 명명 규칙의 이해하기 1