Chp_2_5 Introduction To Social Media Mining

연결성의 정의.
노드 vi에서 vj로 연결되어 있거나 vi에서 시작해서 vj로 이동 가능한 경로가 존재하는 경우.
어떤 노드의 쌍이 주어졌는데 그래프에 서로를 연결할수 있는 경로가 있는경우.
방향성 그래프에서, 두 노드가 방향성이 없이 연결되어 있을때를 약한 연결성을 가진다고 해석한다.
그래프가 강하게 연결되어 있는 상황은 두개의 노드의 쌍이 방향성을 따르면서 직접 연결되어 있을때 "strongly connected" 라고 부른다.
그림 2.9를 살펴보면 연결에 대한 예시를 볼수 있는데, 끊어진 연결, 약한연결, 강한연결을 그래프에서 볼 수 있다.


구성요소(Components)의 정의.
비 방향성 그래프에서 구성요소(Components)란 모든 노드의 쌍(pair) 사이에 경로가 존재하는 모든 그래프를 의미한다(pair를 주고 서로 어떻게든 이어지면 subgraph인것 같다).

그림 2.9: 그래프 상에서의 연결성.

(a)3개의 구성요소(component) 그래프 , (b)3개의 강한 연결성(Strongly Connected)을 지니는 그래프
그림 2.10: 방향성, 비방향성 그래프에서의 구성요소.
그림 2.10(a)를 보면 3개의 구성요소에서 비방향성 그래프를 보여주고 있다.
방향성 그래프에서 구성요소들이 강한 연결성을 지닌다면, 모든 노드의 쌍인 v와 u는, v에서 u로, 반대로 u에서 v로의 경로 역시 지니고 있음을 알수 있다.
만약 방향성 엣지를 비-방향성 엣지로 교채해서 구성요소를 구성한다면 약한 연결성을 지닌다고 할수 있다.
그림 2.10의 b를 보면 3개의 구성요소가 강하게 연결되어 있는것을 볼수있다.



최단 경로(Shortest Path)의 정의.
그래프가 연결되어 있는 상황에서, 어떤 노드의 쌍이던 다양한 경로가 존재할수 있다.
그런데 이중에 노드 v에서 u로 가는 가장 짧은 경로는 어떤것일까?
이런 상황을 최단 경로라 부른다.
GPS 경로 탐색에서 최단경로는 그 빛을 발하는데, 당연히 사용자는 목적지까지 빠르게 가고 싶어하기 때문이다. 

이번장에서는, 노드 i에서 j까지 가는 최단 경로를 살펴보게 된다, 그리고 (short2.1.png)라고 표기하자.
이웃 노드 i에 대한 대념을 알반화 시킬때 최단 경로를 사용하게 된다.
n-hop 이웃의 정의는 i노드에서 n번의 횟수로 방문이 가능한 노드들을 의미하게 된다.
이때, vi의 최단경로는 n보다 낮거나 같은경우를 지칭한다.


직경(Diameter)의 정의.
그래프에서의 직경(Diameter)이란 노드의 쌍에서 최단경로중 가장긴 경로의 길이를 의미한다.
이건 연결성 그래프에만 적용되는데, 당연히 최단 경로란 연결되지 않은 그래프에서는 존재할수 없기 때문이다(연결되지 않은 노드가 있는 상태의 그래프에서는 해당되지 않는 말이라는 의미).
일반적으로, 그래프 G에서, 직경(Diameter)은 다음과 같이 정의할수 있다.