Chapter4. Community Structure in Networks

투빅스 13기 이예지

이번 강의는 community structure in network와 detection of communities에 대해 다룬다.

Community Structure in Networks

community structure란 매우 조밀하게(densely) 연결되어 있는 노드의 셋을 구분짓는 것이라고 할 수 있다.

[그림 1.]을 보면 네트워크에서 3개의 군집이 형성되어 있다. 우리는 이것을 자동적으로(automatically) 찾을 수 있는 알고리즘이 필요하다.

알고리즘에 들어가기 전에, 왜 네트워크에서 이러한 형태의 군집이 생성되는지 살펴보겠다.

Granovetter's Answer

"사람들은 어떻게 새로운 구인구직 정보를 찾는가?", "그리고 소셜 네트워크는 여기서 어떤 역할을 했는가?"

Granovetter는 사람들이 새로운 구직 정보를 구하는 방식이 매일 만나는 친한 친구들이 아닌, 매우 드물게(rarely) 만날 수 있는 지인을 통해 얻게 된다고 말했다.

이러한 관계를 생각했을 때, 네트워크에서의 연결관계(link) 두 가지 관점으로 나뉘어진다.

Structural : Friendships span different parts of the network
즉, 링크가 네트워크의 어떤 부분을 연결하고 있는
Interpersonal : Friendship between two people is either strong or week
즉, 링크가 친한 친구들과 같은 강한 연결관계를 갖고 있는지 혹은 지인과 같은 상대적으로 약한 연결관계를 갖고 있는지

이를 이해하기 위해 다음을 살펴보자.

Triadic Closure

(a, b)와 (a, c) 둘 중 어떤 엣지가 연결될 가능성이 높은가?

직관적으로 (a,b)가 (a,c)보다 더 그럴 법하다는 것을 알 수 있다. 이는 a와 c는 3-hop 관계이지만, a와 b는 두 개의 common neighbor를 갖고 있다.

First point : Structure

구조적으로(structurally) embedded edges(densely)는 사회적으로 매우 강한 관계를 갖는다. ([그림 4.]의 S 참고) 서로 다른 네트워크를 연결하고 있는 엣지(long-range edges)는 사회적으로 약한 관계를 갖는다. ([그림 4.]의 W 참고)

Second point : Information

long-range edges는 주변 지인(네트워크 구조적으로 거리가 있는 사람들)에게 새로운 정보를 얻을 수 있도록 해준다. structurally well embedded edges 매우 중복된(redundant) 정보만을 가지고 그 네트워크 안을 돌 것이다. (즉, 정보이론 관점에서 new information은 얻기 힘들다는 것이다.)

Edge Overlap

네트워크에서 얼마나 많은 친구들(nodes)을 공유하고 있는가(overlap)에 대한 정보를 나타내는 수치가 있다. 구하는 식은 [그림 5.]와 같다.

common neighbor를 공유할수록 값이 1에 가까울 것이다.
common neighbor를 공유하지 않을수록 값이 0에 가까울 것이다.

Network Communities

이제부터 community structure in network에 대해 알아보고, community를 찾을 수 있는 알고리즘에 대해 대해 알아보자.

우리는 네트워크에서 어떠한 그룹(노드의 셋, 클러스터, 모듈 등)을 찾고싶으며, 그 그룹은 매우 강한 연결성을 가지고(즉, a lot of edges) 있어야한다는 전제를 가지고 있다.

Modularity Q

community를 찾기 위해, 우리는 우선 modularity를 알 필요가 있다.

modularity Q란?

얼마나 네트워크가 커뮤니티로 잘 나누어졌는가(*partitioning)에 대한 수치

Q = community s의 edge 수 - 기대되는 community s의 edge 수

이 수치가 클수록(즉, edge수 차이가 클수) 우리는 매우 strong group이라고 할 수 있다.

*partitioning이란, 하나의 노드가 어떠한 그룹(community)에 속하도록 네트워크를 쪼개는 것이라고 할 수 있다.

따라서, "기대되는 community s의 edge 수"를 찾기 위해 우리는 모델을 만들 필요가 있다.

--> null model을 정의할 필요가 있다.

Null model : Configuration Model

Real network $G$ 는 n개의 노드와 m개의 엣지를 가지고 있으며, 우리는 random graph인 $G^{'}$ 을 아래와 같이 구성하고자 한다.

$G$ 와는 동일한 degree distribution을 가지고 있지만, uniformly random하게 연결성을 갖고있다.
multi-graph

노드 i, 노드 j의 degree를 $k_{i}\; and\; k_{j}$ 라고 할 때, 기대되는 엣지의 수는 $k_{i}\times {k_{j}\over 2m}$ 이다.

여기서, $k_{i}\times {k_{j}\over 2m}$ 에서 ${k_{j}\over 2m}$ 는 j와 연결될 확률이라고 생각하면 될 것이다. 노드 i의 degree가 $k_{i}$ 이므로, 노드 i의 각각의 엣지들이 노드 j와 연결될 확률 (multi-graph이므로)을 곱해주면 $k_{i}\times {k_{j}\over 2m}$ 이 유도된다.

( $2m$ : 엣지가 m개일 때, 각각의 엣지는 노드 기준으로 2번씩 count 됨.)

위의 기대값이 맞다고 가정할 경우, 전체 엣지의 수를 추정하면 정확하게 m이 나오게 된다. 이에 따라 유도된 수식이 적절함을 알 수 있다.

자세한 유도 내용은 [그림 7.] 아래쪽에 나와있다.

위에서 "기대되는 community s의 edge 수"를 구하는 방법을 배웠으니, 이제 다시 modularity로 돌아가보자.

우리가 세운 null model에 따라 Q는 다음과 같이 정의될 수 있다.

Q(G,S)={1\over2m}\sum_{s\in{S}}\sum_{i\in{S}}\sum_{j\in{S}}(A_{ij}-{k_{i} k_{j}\over 2m})

이때, m개의 엣지를 가진 그래프가 가질 수 있는 엣지의 합이 최대 $2m$ 였으므로, $2m$ 으로 나누어주게 되면 Q는 -1과 1사이의 값을 가지게 된다. (normalizing factor)

(강의 중 질문 Q = -.5와 Q =.5를 찾는 것이 동일한 problem인가? --> 이는 dual problem이 아니기 때문에 동일하다 할 수 없다. )

Louvain Algorithm

우리는 어떻게 communities in network를 찾을 수 있을까?

Louvain algorithm 매우 빠른 휴리스틱 알고리즘이다. ( $O(n\;log\:n)$ )

hierarchical로 community를 찾는 방식이며, dendrogram으로 hierarchy를 표현할 수 있다.

modularity를 최대화를 하는 것이 목적이2단계로 나눠진다.

Phase 1:
- 가장 처음은 각각의 노드가 single community라고 각한다.
- 노드의 community를 계속 바꿔나가면서 modularity의 증가량( $\Delta Q$ )을 살펴본다.
- 더이상 modularity가 개선되지 않는다면 종료한다.
Phase 2:
- Phase 1에서 찾은 community들 각각을 뭉쳐, single super-node를 만든다.
- Phase 1으로 돌아간다.

$\Delta Q=\Delta Q(i\rightarrow C)+\Delta Q(D\rightarrow i)$

$\Delta Q(i\rightarrow C):$ 노드 i를 'C' community 추가시켰을 때 Q의 증가량

$\Delta Q(D\rightarrow i):$ 'D' community 에서 노드i를 제거시켰을 Q의 증가량

따라서 modularity의 증가량을 계산하기 위해 위의 2가지 값을 알아야 한다.

[그림 11.]이 Louvain algorithm을 매우 잘 나타내고 다.

Detecting Overlapping Communities: BigCLAM

우리 주변에 고등학교 동창, 대학교 동기, 회사 동료 등 다양한 그룹이 있다. 이때, 고등학교 동창이 나와 같은 대학교에 진학했다면 고등학교 동창이 동시에 나의 대학교 동기일 것이다.

이처럼 네트워크에서도 다양한 community가 존재하고, 이때 community들은 discrete하기보다는 overlap된다. 이는 인접행렬(adjacency matrix)에서도 확인할 수 있다. 만약 community가 discrete하다면 [그림 12.]의 위의 그림처럼 겹치는(overlap) 부분이 존재하지 않을 것이다. 반대로, 한 노드가 여러 community에 속할 수 있다면 [그림 12.]의 아래의 그림처럼 겹치는 부분이 존재할 t이다.

네트워크에서 이러한 community를 찾기 위해 2가지 스텝으로 진행된다.

Step 1)
- graph를 generative할 수 있는 모델을 정의한다. (AGM)
Step 2)
- Step 1)에서 AGM에서 data가 generative됐다 가정한다.
- AGM이 G를 generative하도록 파라미터를 학습시킨다.
- 이때, 모델의 파라미터는 노드가 community에 얼마나 속해있을지에 대한 것이다.

직관적인 이해를 돕고자 [그림 14.]을 살펴보자.

왼쪽의 그림에 A, B는 communities이고, 바텀에 있는 것은 네트워크의 노드들이다. community와 노드가 연결되어 있다면, 해당 노드가 그 community에 속한 것이다.

여기서의 issue는 "그렇다면, 어떻게 edges를 design할 것인가?"이다. 이에 따라 각각의 community c는 파라미터 $p_{c}$ 를 갖고 있고, 이것은 어떤 노드가 c community와 연결된 확률을 나타낸다. 는 랜덤성을 가지므로, community 와 노드가 연결이 될까?에 대한 물음은 앞면이 나올 확률이 $p_{c}$ 인 동전을 던지는 것과 같다. 노드는 multiple communities를 가질 수 있으므로, 각각의 노드는 앞면이 나올 확률이 다른 동전을 여러 던지게 된다.

$p(u,v)$ :노드 u, 노드 v가 연결될 확률

$M_{u} \cap M_{v}$ : 노드 u, 노드 v의 common communities

노드 u, 노드 v가 연결될 확률은 두 노드의 공통된 커뮤니티에 속하지 않을 확률을 모두 곱한 뒤(product) 1에서 빼주는 이다. 즉, 두 노드가 동시에 모든 공통 커뮤니티에 속하지 않을 확률을 빼주면 적어도 하나의 공통 커뮤니티에 속할 확률이라고 할 수 있다.

Pros of AGM: [그림 16.]과 같이 3가지의 케이스를 모두 커버할 수 다.

Cons of AGM: Community의 개수가 알려져야 한다. (아마 $p_{c}$ 가 파라미터이므로, 미리 c의 개수를 정정해놔야하는 같다.)

지금까지 우리는 [그림 17.]의 이분그래프에서 네트워크를 생성하는 방향으로 말했지만, 실제로는 주어진 네트워크에서 이분그래프(어떤 노드가 어떤 커뮤니티에 속하는지)를 만들어내는 F를 찾아야 한다.

우리는 F에서 생성된 network가 G이길 바란다. 즉, G를 잘 만들어낼 수 있는 F를 찾아내야 한다.

이것을 위해 우리는 (1) F가 주어졌을 때 G가 나올 확률을 구해야하고, 이 확률을 (2) 최대화시키는 F를 찾아야 한다.

(1) F가 주어졌을 때 G가 나올 확률은 [그림 19.] 아래의 식과 같다.

Model F가 주어졌을 G가 generated 확률은 각각의 independent cell을 베르누이 가정을 하여 likelihood를 구하면 된다.

[그림 19.]로부터 (2) 최대화시키는 F 를 유도하기 해 [그림 20.]을 펴보자.

Membership

$F_{u}$ 는 $F$ 에서 row vector이고, $F_{uA}$ 란, 노드 u의 row vector를 이루고 있는 어떤 차원의 스칼라 값이다.즉, $F_{uA}$ 노드 u가 community A에 속할 확률로 $F$ 에서 어떤 cell의 값이다. 이 값이 클수록 노드 u가 A에 속할 확률이 커진다.