community analysis 2

community detection algorithms

1. member 특성기반 detection (Member-based Community Detection)

(아래 community analysis1참고)

https://sarah0518.tistory.com/133

community analysis 1

2. 그룹속성 기반 detection 

이번에는 2번째인 그룹속성 기반 detection에 대해서 알아 볼 것임

 

Group-Based Community Detection

group property를 가지고 있는 것을 파악 하는 것

Group Properties:

I. Balanced: Spectral clustering

II. Robust: k-connected graphs

III. Modular: Modularity Maximization

IV. Dense: Quasi-cliques

V. Hierarchical: Hierarchical clustering

 

 

I. Balanced Communities

- graph clustering을 사용

- 그래프의 clustering을 만들기위해서 cutting을 하는데

여기서 the size of the cut은 cut이 가지고 있는 edge의 개수를 말함 

- min-cut problem:  min-cut은 imblanaced partition을 나타내는데 활용 됨

  (max-flow를 구하면 min-cut을 바로 구할 수 있음)

  max-flow를 구하면 min-cut을 바로 구할 수 있음- 노란색 라인

너무 극단적으로 쪼개짐.

이것 보다 더 좋은 방법이 ratio cut, normalized cut임(balance를 맞춰서 cut을 할 수 있음)

bar(Pi) = V- Pi

example) 아래내용 꼭 풀어보기!

작은게 더 좋은 것임, 27=13*2 + 1, 12=2*5+2

normalized cut은 edge의 개수를 반영하고, ratio cut은 단순히 node의 개수만을 반영함

 

 

spectral culstering

더 효과적으로 cutting하는 방법으로 spectral clustering 이 있음

ratio cut의 최소값을 찾기위해 활용됨

X matrix: 행은 노드, 컬럼은 community에 대한 멤버십을 의미

각 노드가 특정 community에 속하면 1, 아니면 0임

(실제 알아내려고 하는 것임, 어느노드가 어느 community에 속했는지 알기위함)

D matrix: 각노드의 degree를 대각요소에 가지고 있는 대각행렬

A matrix: adjacency matrix(인접행렬) 노드끼리의 연결 표시

X(t)AX: 는 community에 속한 노드의끼리의 연결 edge의 총 개수가 대각요소값에 들어있음

X(t)DX: 아래그림에서 파란색선 + 노란색 그룹안에있는 edge 총합(=X(t)AX)

X(t)(D-A)X: 는 community에 속한 노드가 다른 community와 연결되는 edge 개수( =cut(Pi, bar(Pi) )

(아래그림에서 파란색 선)

 

위의 빨간그룹 기준으로 X(t)(D-A)X의 대각원소 값은 2임 (노란색 선=2개)

 

ratio cut의 최소값을 찾기위해 활용됨 (아래 수식)

위의식을 아래와같이 더 간단히 표현할 수 있음

L=D-A, L: Unnormalized Laplacian

여기서 trace matrix의 총합이 최소가 되게 하는 X를 찾는것이 spectral clustering하는 목적임

 

참고로 L의 행의합, 열의합은 모두 0임

2개의 그룹으로 쪼개고 싶다면, 2번째의 igenvector를 가지고 음수인 부분/양수인 부분으로 쪼개면 됨

3개의 그룹으로 쪼개고 싶다면, 3번째의 ingenvector로 k-means의 k=3으로 놓고 돌리면 됨