2.1 쾨니히스베르크의 다리
즉, 시작 노드와 끝 노드에만 홀수개의 링크가 있어야 한붓그리기가 가능하다.
이 오일러의 증명에서 그래프 이론이 시작되었다.
2.2 네트워크와 그래프
네트워크는 노드 + 링크로 이루어진다.
- 노드(Node or Vertex): 시스템의 구성성분 목록
- Number of node : N은 시스템의 구성성분 수 또는 네트워크의 크기라고 부른다.
- 링크(Link or Edge): 직접적인 상호작용을 나타내는 부분
- Number of Link: L은 노드 사이의 총 관계수를 의미한다. (2,4)링크는 노드 2번과 4번을 연결해준다.
네트워크의 방향성
- 방향성 네트워크(Directed Network): 모든 링크가 방향이 있을 때
- 방향성 없는 네트워크(Undirected Network): 모든 링크가 방향이 없을 때
네트워크 이론을 시스템에 적용하려면 노드와 링크를 선택하기 전, 문제에서 어떤 형태의 링크와 노드가 중요한지 고려해야 한다.
2.3 링크수, 평균 링크수, 링크수 분포
노드의 핵심 속성은 다른 노드에 연결된 링크의 수를 나타내는 링크수(Degree)이다.
2.3.1 링크 수
2.3.2 평균 링크수
Avarage Degree
2.3.3 링크수 분포
2.4 인접행렬
네트워크를 완전히 기술하기 위해서는 네트워크의 링크를 모두 추적해야 한다.
가장 단순한 방법은 전체 링크의 목록을 사용하는 것으로 예를 들어{(1,2),(1,3),(2,3),(2,4)} 와 같이 고유한 링크를 나열할 수 있다.
수학적인 이유로 네트워크를 인접 행렬(adjacency matrix)로 표현할 때가 있다.
방향성 없는 네트워크에서 인접 행렬의 0이 아닌 성분의 수는 링크 수의 2배이다.
2.5 현실 네트워크의 성김(Sparse)
현실 네트워크들의 노드 수(N)과 링크 수(L)은 크게 차이날 수 있다.
N개의 노드가 있는 네트워크에서 전체 링크의 수는 0개부터 크기 N인 완전 그래프의 총 링크 수인 L_max까지 가능하다.
L_max = NC2로 N(N-1)/2로 나타낼 수 있으며, 완전 그래프에서 각 노드는 다른 모든 노드와 연결된다.
현실 네트워크에서 L << L_max, 즉 L이 L_max보다 현저히 작을 때, 성기다(Sparse) 라고 표현한다.
현실 네트워크는 대부분의 Aij = 0으로 희소 표현으로 나타난다. 그렇기에, 전체의 인접 행렬보다 링크의 목록(전체 인접 행렬보다 Aij가 0이 아닌 부분)을 저장하는 것이 메모리를 아낄 수 있는 방법이다.
2.6 가중치 네트워크
위에서는 모든 링크가 동일한 가중치, 즉 Aij = 1일 경우만 이야기했지만 대부분의 경우 링크(i,j)의 가중치가 wij인 가중치 네트워크를 연구한다.
예를 들어 전력망에서 가중치는 전송선을 따라 흐르는 전류의 양을 나타낸다.
가중치 네트워크에서 인접 행렬의 성분은 Aij = wij 와 같이 링크의 가중치를 표현한다.
가중치를 항상 적절하게 측정할 수는 없으므로, 이런 네트워크를 가중치 없는 네트워크로 근사한다.
2.7 이분 네트워크
이분 그래프(Biptartite Graph)는 노드가 서로소인 2개의 집합 U와 V로 구분되며, 모든 링크는 U노드에서 V노드로 이어진 네트워크를 의미한다.
모든 이분 네트워크에서 2개의 Projection(투영)을 만들 수 있다.
- 이분 표현에서 동일한 V 노드에 연결된 2개의 U노드를 링크로 연결
- 2개의 V 노드가 동일한 U 노드에 연결되면 V노드 2개를 링크로 연결
할리우드 배우 네트워크(U: 영화, V: 배우), 인간 질병 네트워크 등이 있다.
2.8 경로와 거리
네트워크에서는 물리적 거리가 경로 길이(Path Length)로 대체된다.
경로(Path): 링크를 따라 이어지는 길
길이(Lenght): 경로에 포함되는 링크의 수
2.8.1 최단경로
노드 i와 j 사이의 최단 경로는 가장 적은 수의 링크를 포함하는 경로를 뜻한다.
최단 경로는 i와 j 사이의 거리(distance)라고 한다. 동일한 길이의 d가 여러개 존재할 수 있다.
방향성 없는 네트워크에서 d_ij == d_ji이다.
방향성 네트워크에서는 d_ij =! d_ji이다.
최단 경로 길이와 이러한 경로의 수는 인접 행렬을 이용해 수학으로 구할 수 있고, 실제로는 너비 우선 탐색(BFS)알고리즘을 사용한다.
2.8.1.1 인접 행렬로 최단 경로 구하기
2.8.1.2 BFS로 최단 경로 구하기
BFS는 한 노드에서 시작해 그 노드의 이웃에 이름을 붙인다. 그 후, 원하는 목적지 노드에 도달할 때까지 이웃의 이웃으로 계속 동일한 작업을 수행한다. 여기서 목적지까지 도달하는데 필요한 물결 수아 거리를 알려준다.
BFS의 계산 복잡도는 O(N+L)이다. 이것은 모든 노드가 최대로 큐에 한번씩 들어가고, 모든 링크를 한번씩 거쳐가는 상황을 의미한다.
2.8.2 네트워크 지름
네트워크 지름(diameter)은 d_max로 쓰며, 네트워크의 가장 긴 최단경로를 의미한다.
2.8.3 평균 경로 길이
네트워크의 모든 노드 쌍에 대한 경로의 평균 거리를 의미한다. N개의 노드로 구성된 방향성 네트워크에서 <d>는 다음과 같다.
2.9 연결상태
네트워크는 연결상태를 보장해야 유용성이 생긴다.
연결된 덩어리를 찾을 때 수학적/알고리즘적 접근법이 도움즐 준다. 예를 들어 네트워크가 단절됐으면 인접 행렬은 모든 0이 아닌 성분이 대각선을 따라 놓인 정사각형 블록 안에만 있는 블록 대각 행렬로 표현이 가능하고, 이때 다른 모든 성분은 0이다. 각각의 정사각형 블록은 덩어리다.(다리가 추가된다면, 블록 대각 형태로 표현할 수 없다)
선형대수학적 방법을 사용하면 인접 행렬이 블록 대각인지 확인할 수 있으며, 연결된 덩어리를 찾는데 쓸 수 있다.
큰 네트워크에서 덩어리를 찾아낼 때는 BFS 알고리즘을 사용한다.
2.10 뭉침 계수
뭉침 계수: 주어진 노드의 이웃끼리 연결된 정도를 측정
링크 수가 k_i인 노드 i의 국소 뭉침 계수(local clustering coefficient)는 다음과 같다.
해당 게시물은 알버트 라슬로 바라바시,"네트워크 사이언스",이미진 등 교재를 바탕으로 작성된 글입니다.
