Communities

## Granovetter's theory

Granovetter's의 이론에서 edge에 대한 연결이 정의된다.

1. structure : strong한 관계와 weak한 관계가 있다.(여기서 weak는 존재는 하지만 밀집되어서 있지 않는 노드들)

2. infromation :  weak 부분이 정보를 교류하게 할 수 있는 중요한 역할을 한다.

Granovetter's theory

위 그림을 보면 직관적으로 이해할 수 있을 것이다.

## Edge Overlap

node i 에서 node j 로 갈 때 경로 경우의 수가 많으면 edge overlap이 높다고 표현한다. 이 때 i와 j의 직접연결은 제외한다. (weak edge는 edge overlap이 낮다)

edge overlap

Edge overlap은 다음 수식을 따른다.

$$ O_{ij} = \frac{| N(i) \cap N(j)/ \{i,j\} |}{|N(i) \cup N(j) / \{ i,j \} } $$

이러한 overlap 계수를 통해 graph는 Heterogeneity(edge의 중요도가 다 다름)함을 밝혀냄

 

## Network Communities

 

network communities

위 그래프에서 components는 1이고 communities는 3이다. 즉, 하나의 그래프에 dense 하게 모여 있는 부분ㅇ을 community라고 한다

## Modularity

modularity는 community를 측정하는 지표이다. 얼마나 많은 network들이 communitiy로 partition 되어 있는지 나타내주는 지표이다

Modularity는 Q로 표기되며 partition s의 edge와 random graph partition 의 s의 edge들의 기대값의 차의 합과 비례한다.

수식으로 나타내면 다음과 같다.

modularity

앞서 언급한 random graph는 null network configuration model 로 실제 networ와 degree의 개수는 같고, uniform하게 radom connection을 하는 것이다. 이는 degree distribution을 최대한 보존하면서 random graph를 생성하는 방식이다.

이 그래프에서 edge 개수에 대한 기대값은 node i와 node j 가 연결될 확률 x node i의 degree로 계산된다.

이를 수식으로 나타내면

$$ k_i \times \frac{k_j}{2m} $$

으로 나타내진다. 여기서 \( k_i \)는 node i 의 degree 개수이고 m은 총 edge의 개수이다. 여기서 2m인 이유는 undirected graph로 중복되서 세어지기 때문이다. 쉽게 생각하면 node들의 모든 degree = 2m 이라고 생각하면 된다.

이걸 기반으로 생성한 모든 random graph를 다 더하고 2로 나누면 mutligraph(=random graph) G' 안에 존재하는 edge의 기대값이 된다.

따라서 이는 m개가 나와서 edge 개수가 보장된다는 것을 증명할 수 있다.

 

이제 modularity를 계산해보자

아까 언급한 "partition s의 edge와 random graph partition 의 s의 edge들의 기대값의 차의 합과 비례한다." 의 말을 수식으로 나타내면 다음의 식으로 이뤄진다.

여기서 \( A_{ij} \)는 그룹 안에서 node i와 j가 연결되면 1, 아니면 0이 된다.

이와 같은 수식을 기반으로 마지막에 총 degree의 합으로 나눠주면 modularity Q는 [-1,1]의 범위로 normalization 하게 된다.

 

modularity는 보통 0.3보다 크면 Graph가 strong과 weak가 존재하는 구조라는 것으로 파악한다.