Chapter4. Community Structure in Networks

투빅스 13기 이예지

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

Community Structure in Networks

[그림 1.]

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

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

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

Granovetter's Answer

[그림 2.]

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

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

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

• Structural : Friendships span different parts of the network

• 즉, 링크가 네트워크의 어떤 부분을 연결하고 있는

• Interpersonal : Friendship between two people is either strong or week

• 즉, 링크가 친한 친구들과 같은 강한 연결관계를 갖고 있는지 혹은 지인과 같은 상대적으로 약한 연결관계를 갖고 있는지

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

Triadic Closure

[그림 3.]

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

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

[그림 4.]

• 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

[그림 5.]

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

• common neighbor를 공유할수록 값이 1에 가까울 것이다.

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

Network Communities

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

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

Modularity Q

[그림 6.]

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

[그림 7.]

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.] 아래쪽에 나와있다.

[그림 8.]

위에서 "기대되는 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를 표현할 수 있다.

[그림 9.]

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

• Phase 1:

  • 가장 처음은 각각의 노드가 single community라고 각한다.

  • 노드의 community를 계속 바꿔나가면서 modularity의 증가량( $\Delta Q$ )을 살펴본다.
  • 더이상 modularity가 개선되지 않는다면 종료한다.

• Phase 2:

  • Phase 1에서 찾은 community들 각각을 뭉쳐, single super-node를 만든다.

  • Phase 1으로 돌아간다.

[그림 10.]

$\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.]

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

Detecting Overlapping Communities: BigCLAM

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

[그림 12.]

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

[그림 13.]

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

• Step 1)

  • graph를 generative할 수 있는 모델을 정의한다. (AGM)

• Step 2)

  • Step 1)에서 AGM에서 data가 generative됐다 가정한다.

  • AGM이 G를 generative하도록 파라미터를 학습시킨다.

  • 이때, 모델의 파라미터는 노드가 community에 얼마나 속해있을지에 대한 것이다.

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

[그림 14.]

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

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

[그림 15.]

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

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

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

[그림 16.]

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

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

[그림 17.]

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

[그림 18.]

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

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

[그림 19.]

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

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

[그림 20.]

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

Membership

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

[그림 21.]

[그림 15.]의 노드 u와 노드 v가 연결될 확률 다시 정의하면 [그림 21.]과 같다.

$F_{u}$ : 노드 u가 각각의 커뮤니티에 속할 확률을 가진 벡

$\exp{(F_{u}\cdot F_{v})}$ : 노드 u와 노드v가 각각의 커뮤니티에 동시에 속할 확률 (하나의 노드라도 어떤 커뮤니티에 할 확률이 0이라면 둘의 product는 0이다.)

(이때, 갑자기 확률을 정의하기 위해$\exp{(\cdot)}$ 이 등장하는데, 이곳을 참조하면 된다. 간단히 소개하자면 homomorphism을 만족하는 함수가 exponential이고, 이를 취해줌으로써 "동시에 발생할 확률"을 계산하는 것과 같다.)

[그림 22.]

우리의 목적은 음과 같았다.

• (1) F가 주어졌을 때 G가 나올 확률을 구해야하고, 이 확률을 (2) 최대화시키는 F를 찾고자 함.

[그림 19.]의 likelihood를 [그림 21.]을 이용하여 [그림 22.]처럼 정의할 수 있다. (log-likelihood이다. 대입만하면 매우 게 유도된다.)

결론적으로, 위의 log-likelihood를 최대로 만드는 F를 찾으면 되는 이다.

[그림 23.]