[SNS analysis]Network measures2

SNS Network measures를 하는 이유

1. Who are the central figures (influential individuals) in the network?

– 중심도 파악을 위해(Centrality)

2. What interaction patterns are common in friends? (interaction pattern을 찾기위해- level of interaction)

– Reciprocity(상호성) and Transitivity

– Balance and Status

3. Who are the like-minded users and how can we find these similar individuals?

– Similarity(유사도 측정을 위해)

 

 

이번에는 2번, 3번 항목을 알아보도록 하자.

 

 

Transitivity: 전이성

전이성이 높을 수록 graph가 dense하게 됨

-> 최극단으로 전이성이 아주 높게되면 complete graph가 됨(모두 연결된 그래프)

값이 크면 전이성이 높다고 할 수 있음

 

 

Clustering coefficient를 구하는 3가지 방법

(참고로 삼각형이 전이성을 구성하는 basic관계임)

1. path가 2인 모든 조합이 분모로(아래 그림에서 보라색으로 표현된 것)

 

--> 너무 조합이 많으므로 2번째 방법으로 보자

 

2. 삼각형을 구성하는 것

a-b-c와 c-b-a를 다르게 봄(순서중요)

 

3. 삼각형을 구성하는것

a-b-c와 c-b-a를 같게 봄(순서보다 connection이 중요)

단, i-j-k와 j-k-i는 다르다.

가장 구하기 쉬움

 

아래 그림은 3번의 방법의 예시임.

1-2-3, 2-3-1, 3-1-2 각각 곱하기 2해 줌

 

Triple이란? an ordered set of three nodes

1. open triple: connected by two edges

2. closed triple: connected by three edges

** triangle은 항상 3개의 triple을 가짐

**위의 그래프가 complete graph라면 Clustering coefficient=1

 

 

Local clustering coefficient

보통 방향성이 없는 graph에서 많이 사용

어느 특정 node의 neighbor들이 얼마나 storngly하게 연결되어있는지 보는 것

아래그림에서는 A기준으로 0/3이됨, 3이 되는 이유는 3개중에 2개를 만드는 조합이 3이므로

이 그림처럼 점선원의 빈공간(structural holes)이 있다면 local clustering coefficient는 0이 됨

 

 

Reciprocity(상호성)

: if you become my friend, I'll be yours

(방향성이 있는 그래프에서 사용)

transitivity의 간소화 방법이다.

삼각형이아닌 loop를 보는 방법

루프의 개수/전체 Edge의 절반

위의 식을 간소화 하면 아래와 같음

Tr(A)는 대각원소를 모두 더한 것

 

 

Balance

적과 친구의 정의에 일관성있는 relation인지 파악하는 것

친구는 1로, 적은 -1로 표시

이 값이 성립해야지 balance있다고 할 수 있음

balance를 측정하기 위해서는 cycle이 만들어져야함

 

 

status

그룹내에서 얼마나 prestigious한지 측정하는 것

status는 방향성이 있어야함

 

 

similarity

1. structural equivalence 측면에서의 유사도

2. Regular Equivalence 측면에서의 유사도

 

1. structural equivalence

공유하는 사람이 많으면 많을 수록 유사한 것임

형제는 structural equivalence가 높음

1에 가까울수록 유사성이 높음

 

 

structural equivalence를 측정하는 3가지 방법

a. Vertex similarity

b. Jaccard similarity (a를 합집합으로 normalize한 것)

c. Cosine similarity

유사도 계산 예시

 

단, 아래와 같은 경우 분자에 들어가는 교집합이 0이므로

0이라는 값으로 jaccard나 cosine 유사도가 0이되는 문제점이있음

--> 해결책: 자기자신의 노드를 분자에 포함시키는 것으로 해결 할 수 있음