> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter4.-community-structure-in-networks.md).

# Chapter4. Community Structure in Networks

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

##  Community Structure in Networks

![\[그림 1.\]](/files/-M3P_zCzV-C0bj1f0Ot1)

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

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

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

## Granovetter's Answer

![\[그림 2.\]](/files/-M4w-qpeOsfPhOV5waTf)

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

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

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

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

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

#### Triadic Closure

![\[그림 3.\]](/files/-M3PaNNynj2xvdXKBIql)

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

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

![\[그림 4.\]](/files/-M4w4t5LyREe06KyQ4eK)

* 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.\]](/files/-M3PbaXLs0xEl9c3n_2r)

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

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

## Network Communities

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

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

## Modularity Q

![\[그림 6.\]](/files/-M3PdEVenQcChy3D-X81)

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

&#x20;**modularity Q란?**

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

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

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

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

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

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

## Null model : Configuration Model

![\[그림 7.\]](/files/-M3PdOagfe-BTILiPPEz)

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이 나오게 된다. 이에 따라 유도된 수식이 적절함을 알 수 있다.&#x20;

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

![\[그림 8.\]](/files/-M3PeLZkDlaQXyEjzLSr)

위에서 "*기대되는 **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.\]](/files/-M4wlX7rQyuG0qe_TuMy)

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

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

![\[그림 10.\]](/files/-M4wnql3IoiKSvGCJzLL)

$$\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.\]](/files/-M4wpriKmOSpmvQ_VREl)

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

## Detecting Overlapping Communities: BigCLAM

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

![\[그림 12.\]](/files/-M4x4FtP6EjojwK0d6zG)

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

![\[그림 13.\]](/files/-M4x8vrrk7FzYMjdccIK)

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

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

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

![\[그림 14.\]](/files/-M4xDTN-Dzosb93d0-QT)

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

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

![\[그림 15.\]](/files/-M4xmWHpLYvlmnFkYMKo)

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

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

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

![\[그림 16.\]](/files/-M4xp6Jphd438JIUqh1b)

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

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

![\[그림 17.\]](/files/-M4xpwpNq9L80PUcBH_i)

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

![\[그림 18.\]](/files/-M4xqpMRVRmVIF_CCH2Q)

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

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

![\[그림 19.\]](/files/-M4xs7Q4K1R094nGRAsP)

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

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

![\[그림 20.\]](/files/-M4xtFBTXAhA1kMlfkww)

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

#### Membership

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

![\[그림 21.\]](/files/-M4xvlUWdWpvdHFusBmR)

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

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

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

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

![\[그림 22.\]](/files/-M4xxH-lrRZTGdZg4Cct)

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

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

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

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

![\[그림 23.\]](/files/-M4y0AlxDfo7FC6A3bCG)