<CS224W> Lecture 13. Community Structure in Networks

김경준·2022년 4월 19일

CS224W

목록 보기

13/17

Social network에서의 관계는 가까운 친구와 지인으로 나뉠 수 있다.
구직을 하는 과정에서 친한 친구보다는 지인으로부터 소개를 받는 경우가 많다.
Granovetter는 엣지의 사회적인 역할과 구조적인 역할의 관계를 다음과 같이 나타냈다.

Structure: Structually embedded(밀접하게 연결된) 엣지는 사회적으로도 강하게 연결되며 다른 part를 연결하는 logn-range 엣지는 사회적으로 약한 연결 관계에 있다.
Information: Long-range 엣지는 다른 part의 정보를 얻는데 용이하며 structually embedded 엣지는 정보의 접근이 어렵다.

Triadic closure = High clusetering coefficient
$B$ 와 $C$ 가 공통적으로 $A$ 를 친구로 두고 있을 때 $B$ 가 $C$ 와 만날 확률은 높아지고 서로를 비교적 더욱 신뢰할 수 있으며 $A$ 는 두 친구를 함께 데려올 수 있다.

오랜 기간 test 되지 않았던 Granovetter의 이론은 Onnela가 통화횟수을 edge weight로 정의하고 휴대폰 네트워크에 대해 분석함으로써 증명되었다.
$O_{ij}$ (Edge overlap)은 두 사람이 얼마나 많은 지인을 공유하는가에 대한 정보를 제공한다.
$O_{ij} =\frac{|(N(i) \cap N(j))-\{i, j\}|}{|(N(i) \cup N(j))-\{i, j\}|}$ , $N_i$ 는 노드 $i$ 의 이웃노드 집합
결과가 의미하는 바를 정확히 이해 못했지만 네트워크가 밀접하게 연결된 노드들의 집합들로 구성됨을 보인다고 한다..

Communities: 밀접하게 연결된 노드들의 집합
Modularity $Q$ : 네트워크가 communities로 얼마나 잘 나뉘었는지 측정하는 척도로 모든 partition에 대해 [group $s$ 내의 엣지의 수-기대 엣지의 수]의 합으로 정의한다.
$Q\propto \sum_{\boldsymbol{s} \in \boldsymbol{S}}$ [(# edges within group $s$ ) - (expected # edges within group $s$ )]

Modularity 계산 시 필요한 기대 엣지에 대한 비교 그래프를 생성한다.
$n$ 개의 노드와 $m$ 개의 엣지로 구성된 $G$ 로부터 동일한 degree 분포와 총 엣지의 수를 가지지만 uniformly random connections와 두 노드 사이의 multi edges가 가능한 $G'$ 을 만든다.
$k_i,k_j$ 의 degree를 가지는 노드 $i,j$ 의 기대 엣지 수는
$k_i \cdot \frac{k_j}{2m}=\frac{k_i k_j}{2m}$ 이다.
-> 노드 $i$ 에서 나가는 엣지들 $k_i$ 개가 노드 $j$ 로 향할 확률이 $k_j/2m$ 이기 때문. $2m$ 은 directed edges를 의미한다.
$G'$ 의 총 기대 엣지 수는 $G$ 와 동일하게 유지된다.
$\frac{1}{2} \sum_{i \in N} \sum_{j \in N} \frac{k_{i} k_{j}}{2 m}=\frac{1}{2} \cdot \frac{1}{2 m} \sum_{i \in N} k_{i}\left(\sum_{j \in N} k_{j}\right)=\frac{1}{4 m} 2 m \cdot 2 m=m$

같은 community의 노드들을 합쳐 하나의 super node로 표현한다.
Super node들 사이에 하나의 edge라도 있으면 연결한다.
두 super node 간의 edge 가중치는 community 간의 모든 edge 가중치들의 합이다.
Super graph를 구한 후에는 다시 phase 1으로 돌아가며 한 개의 community가 나올 때까지 반복한다.
2개의 communities를 가지는 그래프 -> 4개의 communities를 가지는 그래프와 같은 식으로 hierarchical structure를 만들 수 있다.

실세계에서 사람들은 고등학교 동창이면서 대학교 동창인 것처럼 community가 ovelap 될 수 있다.
인접행렬에서도 community가 겹치지 않는다면 위와 같겠지만 여러 community에 속할 수 있다면 아래와 같이 겹치는 부분이 생길 수 있다.
Overlapping communities는 2가지 step으로 진행된다.
1. Node community affiliations에 기반한 그래프 생성모델을 정의한다.(Community Affiliation Graph Model = AGM)
2. 그래프 $G$ 가 주어졌을 때, $G$ 를 만드는 최적의 AGM을 찾는다.

$p(u,v)$ : $u,v$ 가 서로 연결되어 있을 확률

$M_u \cap M_v:$ 노드 $u,v$ 의 공통 communities

$p_c:$ 어떤 노드가 $c$ community와 연결될 확률

위의 모델에서는 노드들이 어떠한 community에 속하는지에 대한 여부만 따졌지만 실제로는 overlapping communities이기 때문에 모든 node community membership의 strength를 구해야 한다.
$F_{uA}$ 는 community $A$ 에 대한 노드 $u$ 의 strength이며 $P_C(u,v)$ 는 노드 $u,v$ 가 community $C$ 에 의해 연결될 확률을 의미한다.
$F_{uC} \cdot F_{vC}$ 은 양수이므로 $P_C(u,v)$ 는 0~1 사이의 값을 가진다.
노드 $u,v$ 가 연결되어 있을 확률은 memberships의 strength에 비례한다.
노드 $u,v$ 는 여러 communities로 연결될 수도 있다.
$\Gamma$ 는 모든 communities의 집합을 의미한다.
$P_C(u,v)$ 를 풀어쓰면 $P(u,v)=1-exp(-F_u^TF_v)$ 가 되며 $P(G|F)$ 에 로그를 취해 strength의 내적에 대한 합 연산으로 objective function을 정의할 수 있다.