Kusee's Blog: Chp_3_2 Network Measures

3.2 추의적과 상호주의의 정의 (Transitivity and Reciprocity)

종종 소셜 미디어 네트워크에서 사람들의 특정 행동을 관찰할 필요가 있다.
그중 하나를 꼽자면 연결행동(linking behavior)을 들수있다.
연결행동 (linking behavior)이란 소셜 그래프에서 엣지가 어떻게 연결되어 있는지 결정하는 것이다.
이장에선, 두가지 측정법으로 추의적과 상호주의를 살펴보고 분석해 볼것이다.
두가지 방법론은 방향성 그래프에서 사용되고 있다, 또한 추의적은 비-방향성 그래프에서도 적용될 수 있다.

3.2.1 추의적 (Transitivity)의 정의

추의적에서, 연결행동을 분석해 그것이 타동적인 행동으로 보이는지 여부를 판단한다.
수학적으로 표현하면 추의적 관계는

으로 적을수 있다.

전시성을 가지는 연결행동은 다음과 같이 표현할수 있다.

그림 3.8 : 추의적 연결

추의적 연결

v1,2,3 이라는 3개의 노드가 있다고 가정해보자.
노드 v1,2와 노드 v2,3을 잇는 엣지를 볼때, 만약 노드 v3,1을 있는 노드 역시 존재한다면 추의적 연결을 가지고 있다고 정의할수 있다.

덜 형식적인 환경에서 살펴보면

추의적이란 "내 친구의 친구는 내 친구다" 로 쉽게 표현이 가능하다.
**3단 논법처럼 a-b이다 b-c이다 따라서 a-c이다 라는 의미같다**

정의에서 보여주듯, 추의적 행동은 최소 3개의 엣지가 필요하다.
이 3개의 엣지에서, 이 관계에 참여하는 노드들은 삼각형의 형태를 이룬다고 볼수 있다.
밀집된 그래프에서 보여주는 높은 추의적은, 완전 그래프의 형태로 볼수 있다.
그러므로, 우린 추의적을 측정함으로서 그래프가 얼마나 완전한지 판단할수 있다.
이현상을 측정 하기위해서는 "전역 클러스터링 계수(global clustering coefficient)" 와 "지역 클러스터링 계수(local clustering coefficient)" 를 측정하면 가능하다.
"전역 클러스터링 계수"는 네트워크에 대해 계산하고 "지역 클러스터링 계수"는 노드에 의해 계산된다.

클러스터링 계수(Clustering Coefficient)

추의적 클러스터링 계수의 측정은 비-방향성 그래프에서 이루어 진다.
삼각형 형태에서 추의적이 발견 되었을때, 노드 v1,2를 잇는 엣지와 노드 v2,3를 잇는 엣지를 측정하면 길이가 2임을 확인할수 있고 나머지 노드 v1,3를 잇는 엣지가 존재함으로써 삼각형의 형태 임을 측정할수 있다.
그러므로, 글러스터링 계수 C는 다음과 같이 정의된다

또한, 삼각형의 개수를 셀수도 있다는데

모든 삼각형에는 길이 2의 닫힌 경로가 8개 있기 때문에 3.49와 같이 수식을 변경할수 있다

이 방정식에서, 3열은 3개의 노드로 구성된 집합이며, 2개의 엣지(열린 삼각형,미완성 삼각형) 이거나 3개(완전한 삼각형) 엣지이다.
각각의 상황은 다음을 기준으로 나뉘게 되는데

1. 노드가 다르거나
2.노드는 같은데, 이 연결 트리플은 있거나 누락되거나 다른 상황이다.

예를 들면 노드 vi,j,k 와 vj,k,i 가 다를때를 살펴보자, 이건 노드 k,i를 이어주는 엣지 e와 노드 i,j를 이어주는 엣지가 사라졋을 때를 의미한다.
동일한 문맥으로,노드 k,i를 이어주는 엣지 e가 동일하다면 노드 i,j,k 와 노드 k,j,i 가 같다고 볼수 있다.
삼각형에 3개의 엣지가 있을때 , 엣지 한개가 소실될 가능성이 있다, 그러므로 하나의 삼각형에서 3개의 다른 삼각형의 형태를 만들수 있다.
따라서 방정싱 3.50에서 볼수 있듯이 삼각형의 수는 분자의 인수에 3을 곱해서 만든다.

클러스터링 계수는 전체 네트워크에 대해 계산된다는 점에 주의해야한다.

예시 3.11. 그래프 3.9를 기반으로한 클러스터링 계수 구하기 적용

클러스터링 계수는 지역적으로도 구할수 있다.
다음에 나올 챕터에서 단일 노드에 대한 값을 구해볼 것이다.

그림 3.9 : 전역 클러스터링 계수의 예시 (Global Clustering Coefficient).

지역 클러스터링 계수(Local Clustering Coefficient)의 정의.

지역 클러스터링 계수가 노드 수준에서의 추의성을 측정할수 있다.
일반적으로는 비 방향성 그래프에서 사용한다, 이것은 노드 v에 인접한 이웃이 얼마나 강력하게 연결되어 있는지 추정할수 있다.
계수는 다음과 같이 정의 할 수 있는데

비방향성 그래프에서 ,노드 Vi에 이웃인 Di에 해당하는 분모는

과 같이 작성할수 있다.
예시 3.12. 그림 3.10에서 보여주는 지역 클러스터링 계수의 변화

그림 3.10: 다른 그래프에서 지역 클러스터링 계수의 변화. 얇은 선은 이웃간의 연결을 의미한다. 두꺼운 라인은 이웃을 가리키며, 점선은 소실된 연결을 의미함.

그림 3.11 : 상호 연결된 엣지 상황.

노드 v1.
얇은 선은 v1이 이웃과 연결되어 있음을 보여주고 있다.
점선은 이웃과 연결될 가능성이 있음을 보여주며, 실선은 현제 이웃과 연결되어 있음을 보여주고 있다.
노드가 이웃과 연결되어 있을때, 지역 클러스터링 계수는 0이 된다, 그리고 모든 이웃이 연결되어 있다면, 최대값이 되며

이 된다.

3.2.2 상호 의존성의 정의 (Reciprocity)

상호 의존성(Reciprocity)이란 추의성(transitivity)의 단순한 버젼이라 할수있다, 왜냐하면 길이 2짜리 닫힌 루프이기 때문이다, 또한 이 현상은 방향성 그래프에서만 관찰이 가능하다.
공식적으로, 노드 v가 노드 u와 연결되어 있다면, u와 v역시 연결되어 있기 때문에 상호 적이라 볼수 있다.
텀블러와 같은 마이크로 블로깅 사이트를 예를 들면, 이 노드는 “mutual followers.” 라고 알려져 있으며, 비공식 적으로 상호주의를 설명하면 다음과 같이 표현이 가능하다.

"네가 내 친구가 되면 나역시 너의 친구다"
그림 3.11 을 보면 그래프 상에서 v1과 v2의 상호 연결을 보여주고 있다.

상호주의는 그래프에 있는 상호간의 노드 쌍의 수를 계산 하는 것이다.
모든 방향성 그래프에서 최대 |E|=2 의 쌍을 가질수 있다.
물론 이건 모든 엣지가 상호 상호의존 관계를 지닐때 이루어진다.

그러므로, 이값은 정규화에 사용할수 있다.
상호 의존성은 인접행렬 A를 이용해 계산해 낼수 있다.