[SMM 10] - Community Analysis(2)- Community evolution

Network and Community Evolution

- 시간이 지나면서 nework, community 어떻게 바뀌는지?

-  그 중에서도 바뀌지 않고 남아있는 부분은 어떤 것인지?

- 어떤 것들이 바뀔 수 있는지

 

How Networks Evolve?

1. Network Segmentation

2. Graph Densification

3. Diameter Shrinkage

 

network 변화의 경향성

1. Network Segmentation

Giant, stars, singletons

 

2. Graph Densification

• The density of the graph increases as the network grows(node-node connection 이 커짐)

– The number of edges increases faster than the number of nodes does

양 쪽에 log를 씌우게 되면,  이런식의 분포를 확인할 수 있음

• Densification exponent: 1 ≤ alpha ≤ 2:

– alpha = 1: linear growth – constant out-degree

– alpha = 2: quadratic growth – clique

 

3. Diameter Shrinking

• In networks diameter shrinks over time

 

How Communities Evolve?

Communities also expand, shrink, or dissolve in dynamic networks(evolution patterns)

 

Community Evaluation

community 평가

이질적인 노드가 들어왔을 때, 완벽하지 않은 community

 

2가지 평가 방법이 있음

•  Evaluation with ground truth

• Evaluation without ground truth (노답)

 

Evaluation with Ground Truth

• Measures

– Precision and Recall, or F-Measure

– Purity (순수도)

– Normalized Mutual Information (NMI)

 

Precision and Recall

P, R 1에 가까울 수록 community detection 이 잘됨, F- measure 사용 가능

Precision : 도출된 결과에서 얼마나 정확하게 정답이 회수가 되었는지

Recall : 정답 중 얼마나 정확하게 뽑아냈는지

 

Purity

기존 정답에 비해 얼마나 pure한지 평가

 

purity = 6+5 / 14 = 0.78

• k: the number of communities

• N: total number of nodes,

• L_j: the set of instances with label C in all communities

• C_i: the set of members in community i

 

Purity can be easily tampered by

purity가 1이 되었다고 해서 정확하게 cluster가 제대로 파악되었다고 할 순 없음

• Points being singleton communities (of size 1); or by

• Very large communities