community evolution & evaluation

Community analysis란 아래 3가지를 분석하는 것인데,

지난 community analysis 1~3에서는 community detection에 대해서 

정리한 내용임

 

이번 contents는 community evolution & evaluation에 대해 정리하고자 함.

 

 

community evolution

 

Network Growth Patterns

1. Network Segmentation

2. Graph Densification

3. Diameter Shrinkage

 

 

1. Network segmentation

시간에 지남에 따라서 아래의 3개의 component로 쪼개지는 현상을 보임

1. Giant Component: As network connections stabilize,

a giant component of nodes is formed, with a large proportion of network nodes

and edges falling into this component.

2. Stars: These are isolated parts of the network that form star structures.

A star is a tree with one internal node and n leaves.

3. Singletons: These are orphan nodes disconnected from all nodes in the network.

 

 

2. Graph Densification

시간에 따라 edge의 개수는 node보다 더빨리 증가함

1<= a <=2

edge는 v의 알파승만큼에 비례해서 증가함

위의 식에서 log를 씌우면 선형적 증가성을 보임

 

 

3. Diameter shrinking

두 노드를 연결하는 최단거리가 시간이 지남에 따라 줄어듬

(SNS에서 6단계만 건너면 모두 연결 됨)

 

 

Community Evolution는  

expand, shrink, dissolve의 단계를 거침

아래 그림은 community의 다양한 성장 단계를 보여 줌

 

community evaluation

 

perfect community: 동일한 멤버로 이루어진 community일 때

Fig1. perfect community가 아님

 

 

2가지 평가방법이 있음

• Evaluation with ground truth

 - network 알고리즘 개발한 뒤 테스트 할 때 사용

• Evaluation without ground truth (real-world)

- real-world와 얼마나 유사한지 볼 때 사용

- 신뢰 coefficient는 groud truth가 없음

 

 

평가 measures

– Precision and Recall, or F-Measure

– Purity

– Normalized Mutual Information (NMI) - 생략

둘 다 1에 가까우면 성능이 좋은 것임

위의 벤다이어그램(Fig1)을 통해 계산해보면 아래와 같음

F = 2PR/(P+R)

교재에 나오는 예제 꼭 풀어보기!!

 

Purity 

k: 클러스터의 개수 = 2

N: 총 node(member수) = 14 (6+8)

L1: +로만 구성된 것 = 7

L2: x로만 구성된 것 = 8

Cluster1에서의 max값은 5, 

Cluster2에서 max 값은 6

→ purity = (6+5)/14 = 0.78

 

purity의 단점: 각각의 cluster가 원소1개이면 purity가 1이 됨

극단적으로 cluster가 작게 쪼개졌을 때 1인 값을 가지게 됨

- points가 singleton이면 purity의 값이 의미 없어짐

- 특정 cluster가 다른 cluster에 비해 너무 크면 purity의 값이 의미 없어짐