Chp_2_1 Introduction To Social Media Mining

2.1 그래프 기초 

이장에서는 그래프를 이용한 표기법을 살펴보게 된다.
어떤 그래프던 두가지를 포함하는데 노드라 부르는 object와, 엣지(라인) 으로 관계를 이어주는 선, 이 2가지가 꼭 포함되게 된다.
수학적으로, 그래프 G는 페어로 기술하는데 G(V;E)로 기술한다, 이때 V는 노드를, E는 엣지를 의미한다.
2.1.1부터 노드와 엣지에 대한 정의를 내린다.

2.1.1 노드란?
모든 그래프에는 기본적 요소로 사용되는 블록이 있다.
모든 그래프에서 가장 중요한것은 노드이다.
교우관계를 표현하는 그래프가 있다고 할때, 노드는 사람을 의미하고, 노드끼리 연결되어 있다면 그건 서로가 친구라고 할수있다.
문맥에 따라서, 이런 노드들을 정점이나 행위자로 부른다.
예를들면,웹 그래픽에서, 노드는 웹사이트를, 노드간의 연결은 해당 사이트 간의 링크를 의미한다.
소셜 셋팅에서 이런 노드들은 행위자라고 부른다.
수학적 노드들을 다음과같이 표현 가능하다, 이때 V가 노드 vi로 1<=i<=n 사이에 있을때 싱글노드라고 부른다.
절대값 v=n 일때 그래프의 크기라 부르며 이는 그림 2.1에서 볼때 n=7이다.

그림 2.2: 방향성 그래프와 비 방향성 그래프. 원은 노드를, 선이나 화살표는 엣지로 연결됨을 의미한다.


2.1.2 엣지, 모서리,선

그래프에서 다른 중요한점은 엣지이다.
엣지는 노드들을 이어주는 역할을 한다.
소셜 미디어에서, 노드들이 사람처럼 각각의 속성을 의미한다면 , 엔지는 노드간을 연결하게 되는데 이를 사회적 관계로 대입해서 생각할수 있다.
엣지는 보통 E를 사용해서 표현하고 ei가 1에서 m 사이에 존재한다, 엣지와 엣지의 규모는 |E|로 표현하게 된다.
그림 2.1에서, 라인들이 각 노드에 연결되어 있는것을 볼수있다, 이때 m=8임을 알수 있다.
엣지는 노드간의 최종 목적지를 나타내는데, e(v1; v2)((v1; v2))을 보면 엣지 e는 노드 v1과 v2의 사이에 연결되어 있다.
엣지는 방향성을 가질수 있는데, 하나의 노드에서 다른 노드로 연결되어 있을때 방향성을 가진다면 역방향은 성립하지 않는다.
엣지가 방향성이 없다면 해당 엣지는 양방향성이라고 말할수 있다.
그림 2.2를 살펴보자, 엣지 e(v1,v2)와 e(v2; v1) 는 방향성이 없이 서로 연결되어 있기 때문에 같은 엣지라고 볼수있다.
이런 그래프상에서 엣지는 방향성이 없는 엣지, 그리고 이런 그래프를 비 방향성 그래프라고 부른다.
반대로, 엣지에 방향성이 있는 경우 e(v1; v2) 와 e(v2; v1)는 같은 엣지가 아니다.
그래프 2.2를 살펴보면 엣지에 방향성이 있는것을 볼 수 있는데,이런 상황은 방향성을 가진 그래프라고 부른다.
방향성을 가진 엣지는 화살표를 사용해서 그린다.
방향성 그래프에서, 엣지 e(vi; vj)는 i에서 j까지 화살표를 이용해 방향성을 나타내고 있는것을 볼 수 있다.
엣지의 시작과 끝은 같은 노드일수 있는데, 이런엣지를 "루프" 나 "self-link" 라고 하는데 표현하면 e(vi; vi) 로 나타낼수 있다.
vi의 어떤 노드도, 방향성이 없는 그래프이다, 이때 엣지를 통해 연결되어 있는 노드의 집합을 "이웃" 이라고 하며 N으로 나타낸다.
그림 2.1에서 보면 Jade의 이웃 N은 jeff와 juan으로 볼수 있다.
방향성 그래프에서, 노드 Vi와 연결된 incomming 이웃과 outgoing 이웃을 확인 할수 있다.
그림 2.2 a에서 v2의 incoming 이웃은 v3 outgoing 이웃은 v1,v3임을 확인할수 있다.


2.1.3 Degree와 Degree 분배
엣지의 Degree를 정의할때 몇개의 엣지가 하나의 노드로 연결되어 있는지를 보고 판단하게 된다.
노드의 Degree를 표현할때 로 표현한다.
방향성이 있는 엣지 상황은 2가지로 볼수 있는데 노드가 in-degree를 가질때(자신 노드쪽으로 들어오는 방향) 와 out-degree (자신 노드에서 나가는 방향) 로 나뉠수 있다.

이런 변수는 와 로 표현이 가능하다.

소셜 미디어에서, degree는 친구의 수를 의미한다.
예를들어, 페이스북이라면, degree 는 친구들의 수를 의미한다, 트위터에서 in-degree와 out-degree 는 팔로워와 팔로우 수에 대응할수 있다(내가 팔로우 하는것과 타인이 팔로잉 해주는것은 다르기 때문).
방향성이 없는 그래프라면,모든 노드 degree의 합은 엣지의 두배와 같다는 식이 나온다.

=공식 2.1= 비 방향성 그래프에서 모든 degree의 합은 총 엣지수의 2배이다.
--(수식 2.3)

증명.
어떤 엣지가 2개의 최종 지점을 가지고 있을때, 그러므로 di 와 dj의 degree를 측정한다면 연결되는 노드는 vi와 vj이다, 그들 사이의 엣지는 1개로 di와 dj각각 1개씩 엣지의 카운트가 올라간다,그러므로 엣지가 제거된다면, di와 dj는 di-1 dj-1이 되기 때문에,최종 합은 (시그마k) 에서 (시그마k) dk-2가 된다.
따라서 모든 m degree를 제거하면, degree의 총합은 2m이 된다.
하지만, 우린 모든 엣지가 제거되면 degree의 총합이 0이 됨을 알고 있다, degree 총합은 2*m = 2|E| 이다.

보조정리 2.1.
비 방향성 그래프에서, 짝수의 노드는 홀수의 Degree를 갖는다.
증명은 이미 이전에했던 2|E|에서 처럼 합계가 균등하기 때문에 이전의 정리에서 도출이 가능하다.
그러므로 전체 합계에서 짝수의 노드의 degree를 제거할때, 홀수 degree의 노드의 총합은 짝수가 되어야 한다, 그러므로 정리하면 짝수의 노드의 상황에서는 홀수의 degree를 가진다.

보조정리 2.2.
어떤 방향성이 있는 그래프던, in-degree의 합이나 out-degree의 합은 언제나 같다.



증명
증명은 연습문제로 남긴다.

Degree 분배.
매우 큰 그래프 상황에서, 노드의 분배나 (degree 분배)는 매우 중요한 문제이다.
degree 분배는 네트워크를 공부한다면 매우 중요한 문제이다.(분배가 잘 안되면 특정 구간에 몰리는 등의 문제를 말하는것같음)
모든 분배는 해당 구성원에 의해 설계된다.
우리의 상황에서는, 이것들이 그래프 상에서 볼수있는 모든 노드의 degree이다.
degree 분배에서 pd에서 선택된 노드 v에 대한 d의 degree의 확율분포를 가지게 된다.
왜냐하면 pd의 확률분포는 최대 1까지의 범위에서 움직인다(확률의 총합은 언제나 1이기 때문)
n개의 노드가 있는 그래프에서 Pd는 다음과 같이 정의된다.


nd가 노드에 해당하는 degree를 의미한다면.
중요한것은, 일반적으로 degree 분배에 대한 히스토그램 그래프를 그릴때, x축은 degree를 의미하고, y축은 해당 degree를 가지는 노드의 수를 의미한다.


예시 2.1.
그림 2.1에서 표현되는 그래프를 살펴보면, d에 해당하는 degree분배 d={1,2,3,4}가 되는데, 이유는 4개의 노드가 degree 2를 가지기 때문이다, 그리고 degree 1,3,4 는 한번씩만 관찰되고 있다.

그림 2.3 : 미국과 전세계 사용자의 페이스북의 degree.
이 표를 보면 친구가 적은 사용자와 친구가 많은 사용자가 있음을 알수 있는데. 이건 power-law degree분포의 한 종류로 볼수 있다.


예시 2.2.
소셜 네트워킹 사이트에서, 친구관계는 큰 그래프를 생성할수 있다.
이 그래프에서, 노드는 각각의 개인을, 엣지는 친구관계를 의미한다.
이때 degree를 계산해서 도표를 만드고 x축은 degree y축은 각 노드에 해당하는 degree를 할당시킬수 있다.
2012년 페이스북 degree 분포 도표를 그림 2.3에서 볼수있다.
일반적으로 관찰되는 소셜 네트워킹 사이트의 트렌드는 접속 빈도가 적은 유저가 많고 친구가 매우많은 소수의 사용자가 있다는 것이다.
이건 일반적으로 power-law degree 분배라고 부른다.
이전에 말했던 것처럼, 어떤 그래프 G는 쌍으로 존재한다 G(V,E),여기서 V는 노드의 세트 E는 엣지의 세트이다.
엣지가 노드 사이에 있다면, 그래프와 sub그래프를 가진다고 할수 있다.
그래프 G(V; E)에서, 그래프 G0(V0; E0)은 그래프 G의 서브 그래프가 되는 조건은 다음 속성이 유지되는 경우를 볼수 있다.




그림 2.4:그래프를 행렬 행렬로 대응한 도표