[Study]Chapter 13. Community Structure in Networks
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
I. Community detection in networks
우리는 네트워크의 구조가 보통 아래와 같다고 본다.
Figure 1 : Network
Figure 1의 네트워크 구조에서 음영진 부분이 커뮤니티(군집)를 형성한다고 생각할 수 있다. 그렇다면 이러한 네트워크 구조에서 정보는 어떤 흐름으로 전달이 될까?
Figure 2 : Social Network, 군집내에서는 “short” link로 연결되어 있고, 군집간에는 “long” link로 연결이 되어있다.
Figure 2의 구조에서 “short-link”는 사회적으로 강하고, “long-link”는 사회적으로 약하다. 또다른 정보의 관점으로 다른 군집의 정보(1,2,3 node)를 모으도록(4 node) 한다.
1. Triadic closure
Figure 2에서 노드 쌍 (6,4)와 (6,2) 중에 어떤 쌍이 친구가 될 가능성이 높을까? 이는 두 노드 사이에 공통적인 노드를 가지고 있을때 그 가능성이 더 올라갈 것이다. 이러한 현상을 High clustering coefficient로 볼 수 있고, 두 노드가 하나의 노드를 공유하고 있을때, 두 노드는 공유하는 노드와 같은 거리에 있기에 만나기 쉬워지고, 동일한 노드를 공유하기에 서로를 신뢰할 수 있다. 그리고 공유하는 노드는 각 두 노드와의 결합을 해체하기 어렵기 때문에 같이 가져오는 것을 장려한다.
2. edge overlap
아래의 edge overlap을 통해 이러한 link의 강도를 측정한다. N(i)는 노드 i의 이웃 집합이고, 0에 가까울수록, edge는 local bridge가 된다.
\[O_{ij}=\frac{|(N(i)\cap N(j)-\{i,j\})|}{|(N(i)\cup N(j)-\{i,j\})|}\] Figure 3 : 각 네트워크의 edge overlap
아래와 같이 네트워크 구조의 overlap과 call 수와는 상관관계를 이루었다.
Figure 4 : 유럽 국가의 20%의 인구의 cell-phone 네트워크 연구인 Onnela et al. 2007로 interpersonal social connect를 overlap을 통해 증명하였따. (좌)strenth(#calls)에 기반하여 edge를 제거 (우) edge overlap에 기반하여 edge를 제거
II. Network communities
네트워크 커뮤니티는 많은 내부의 연결을 가지고 몇개의 외부의 연결을 가지는 노드들의 집합입니다. 이렇게 밀집되어 연결된 노드들의 그룹이 얼마나 잘 나뉘어졌는지를 측정하여 커뮤니티를 찾을 수 있습니다.
1. Modularity
Figure 5 : Modularity Q는 커뮤니티 그룹 S 내의 연결된 엣지 수에서 null-model을 사용하여 생성한 엣지 수의 차이를 고려합니다.
null-model 하에서 차수 분포와 전체 edge 수는 보존됩니다. 따라서, 동일한 차수 분포를 가지고 무작위로 연결된 되어 있는 null-model에서 기대 값을 계산합니다. null-model의 전체 기대 수는 방향 edge를 가정하여 \(\sum_{u \in N}k_u = 2m\)이 됩니다.
이를 차수 $k_i$, $k_j$를 가지는 노드 i와 j 사이의 기대되는 edge들의 수를 계산하면 두 노드간의 가능한 연결의 수를 곱한 후 전체 edge로 나누는 \(k_i \cdot \frac{k_j}{2m}=\frac{k_ik_j}{2m}\)와 같은 식이 계산됩니다.
Figure 6 : 괄호안의 좌측항은 실제 i와 j노드의 연결 수 이고 우측항은 null-model에서의 기대 연결 수 입니다.해당 값이 양수이면 edge들의 숫자가 기대 수를 초과했다는 의미로 0.3-0.7이 중요한 커뮤니티 구조를 의미
따라서, modularity를 최대화하면 커뮤니티를 식별할 수 있습니다.
Figure 7 : modularity를 위와 같이 새로 작성하여 Q를 최대화하여 커뮤니티를 식별할 수 있습니다.
III. Louvain Algorithm
탐욕적으로 modularity를 최대화 하는 알고리즘으로 $O(nlogn)$의 시간복잡도를 가지고, 가중 그래프를 지원하고 계층적 커뮤니티 제공합니다. 큰 네트워크에서 빠르고, 빠른 수렴과 높은 Q 결과으로 인해 넓게 사용됩니다.
Figure 8 : modularity 최적과 커뮤니티 집계를 반복
두가지 단계로 modularity가 수렴할때까지 반복합니다.
- modularity가 local change에서 node-communites 멤버쉽으로 최적화
- 식별된 커뮤니티는 super-node들에서 새로운 네트워크를 건설하게 aggregated됨.
1. Partitioning
각 노드에 구별되는 커뮤니티를 부여하고, 각 노드 i에서 두개의 계산을 수행하는 작업으로 하나는 이웃 j의 커뮤니티로 넣었을때의 변화인 modularity delta(\(\delta Q\))를 계산하고, 다른 하나는 j의 커뮤니티로 이동했을때 얻어지는 \(\delta Q\)가 가장 큰 값을 계산하는 것입니다.
위 계산은 Modularity Gain이 없어질때 까지 반복합니다.
Modularity Gain
Figure 9 : 노드 i를 D 커뮤니티에서 C 커뮤니티로 이동한 modularity의 변화량은 i를 D에서 제거하고, i를 C에 넣어서 얻어지는 변화량의 합과 같다.
Figure 10 : 커뮤니티 C의 Modularity Q(C)를 계산.
- $\sum_{in}:C$안의 노드들 사이의 링크 가중치의 합.
- $\sum_{tot}:C$ 안의 노드들의 모든 가중치 합.
- \(k_{i,in}\) : 커뮤니티 C와 노드 i 사이의 연결된 가중치의 합.
- $k_i$ : 노드 i의 모든 연결 가중치의 합.
Figure 11 : $\delta Q(C\rightarrow i \rightarrow C’)$의 분해과정
즉, 해당 과정은 아래와 같습니다.
- 현재 커뮤니티(C) 안의 각 노드 i에 대해서 최적의 커뮤니티(C’)를 계산
- C’ = $argmax_{C’}\delta Q(C\rightarrow i \rightarrow C’)$
- $\Delta Q(C\rightarrow i \rightarrow C’)$ > 0 이면, 해당 커뮤니티로 update
2. Restructuring
위의 Paritioning을 통해 각 커뮤니티를 연결하는 super-node를 얻게 됩니다. 해당 super-node 사이의 edge 가중치는 각 커뮤니티 사이의 모든 edge들의 가중치 합과 동일합니다.
Figure 12 : super-node의 가중치
3. Overview
Figure 13 : Louvain Algorithm Overview
IV. BigCLAM : Detecting Overlapping Communities
BigCLAM은 Community-Leveraged Attentive Message Passing on Networks의 약자로 커뮤니티 탐지 알고리즘 중 하나로 겹쳐져(overlapping)있는 상태의 커뮤니티를 탐지합니다.
Figure 14 : (좌) non-overlapping (우) over-lapping
커뮤니티 탐지 모델의 정의
그래프 생성 모델을 정의
AGM을 최적화하여 커뮤니티 찾기
최적의 AGM을 찾는 방법으로 커뮤니티를 찾게 됩니다.
1. AGM : Community Affiliation Graph Model
AGM은 그래프 생성 모델 중 하나로, community affiliation에서 모델 파라미터 ($V,C,M,{P_c}$)가 주어졌을때 노드가 여러 커뮤니티에 속할 수 있는 다중 커뮤니티 구조(non-overlapping, overlapping, nested 등)를 모델링하는데 사용됩니다.
Figure 15 : community affiliation에서 다중 커뮤니티 구조로 AGM이 모델링
노드 두 노드 u와 v가 여러개의 커뮤니티에 속해 있는 경우, 각 커뮤니티에 있는 노드들이 연결될 확률($p_c$)을 사용하여 첫 커뮤니티로 연결되지 않아도 다음 커뮤니티에서 추가적인 연결 기회를 얻게됩니다.
\[p(u,v) = 1 - \prod_{c\in M_u\cap M_v}(1-p_c)\]위처럼 두 노드 사이의 연결확률을 계산하는데, 이를 여러 커뮤니티의 멤버십 강도를 고려합니다.
Figure 17 : F는 그래프를 생성하는 확률 모델로 베이지안 정리를 통해 그래프 G가 주어졌을때, F의 likelihood를 최대화하여 추정하는 MLE를 사용하여 F를 추정합니다.
그래프 G와 각 노드 간의 멤버십 강도 F가 주어졌을때, 각 graph에 존재하는 edge들의 연결 확률 곱과 존재하지 않는 edge들의 비연결 확률을 곱하여 그래프 G의 발생확률 $P(G|F)$를 얻을 수 있습니다.
\[P(G|F) = \prod_{(u,v)\in G}P(u,v)\prod_{u,v\notin G}(1-P(u,v))\]위에서 봤듯이 $P(u,v)$는 멤버쉽의 강도(즉, 그래프 확률 모델델)를 사용하여 커뮤니티를 통해 연결될 확률을 계산할 수 있습니다.
Figure 18 : Relax the AGM, 각 노드의 연결 멤버십은 노드 u에서 커뮤니티 C로의 strength(\(F_{uC}\))를 포함합니다
따라서, 커뮤니티 C에 대한 노드 u와 v의 연결확률은 아래와 같이 표시되어 0이면 노드 u와 v는 커뮤니티 C를 경유하여 연결되지 않음을 그리고 1과 가까울 수록 C를 경유하여 연결을 나타내는 (0,1) 사이의 값을 의미합니다.
\[P_c(u,v)=1-exp(-F_{uC}\cdot F_{vC})\]위의 수식들을 모두 풀어쓰면,
\[\begin{align*} P(u,v)&=1-\Pi_{C\in \gamma}(1-P_C(u,v))&(1) \\ &=1-\Pi_{C\in \gamma}exp(-F_{uC}\cdot F_{vC})&(2) \\ &=1-exp(\Pi_{C\in \gamma}-F_{uC}\cdot F_{vC})&(3) \\ &=1-exp(-F_{u}^T\cdot F_{v})&(4) \\ \end{align*}\]그래프 생성 모델의 요소인 두 노드의 연결 확률 $P(u,v)$는 (1)과 같이 각 커뮤니티를 통해 연결될 확률을 (4)와 같이 멤버십의 강도를 사용하여 계산합니다.
2. BigCLAM model
Figure 19 : 그래프 생성 모델 F가 주어졌을때, 그래프 G의 발생 확률
Figure 19에서 확률은 많은 내적(\(F_{uC}\cdot F_{vC}\))을 포함하여 수치적으로 불안정해 아래와 같은 목적함수를 사용해 \(\mathcal{l} (F)\)를 최적화합니다.
\[log(P(G\|F))\equiv \mathcal{l} (F)\]위의 목적함수를 최적화하기 위해 아래와 같은 절차를 진행합니다.
각 노드의 멤버십 F(그래프 생성 모델)를 무작위로 설정
아래와 같은 업데이트를 수렴할때까지 반복합니다.
\[F_u^{(new)} = F_u^{(old)} + \mu \cdot \mathbb{l}(F_u^{(old)})\]Figure 20 : 경사하강법의 시간복잡도를 계산할때, 좌항은 u 차수에 선형적(빠름)이고 우항은 #nodes에 선형적(느림)이다. 따라서, 나이브 경사하강법은 느리지만 효율적으로 업데이트가 된다.
첫번째 합은 노드 u와 v가 연결될 확률을 정규화하여 이웃한 노드 v의 특징 벡터를 곱하여 최대화하려는 항입니다. 두번째 합은 이웃하지 않은 노드들의 특징 벡터를 합산하는 항으로 최소화하려는 목적을 가집니다.
이러한 절차는 노드 u와 v간의 연결 확률은 공유된 멤버십의 강도에 비례하며, 이를 통해 그래프가 주어졌을 때 해당 모델에 기반한 로그-가능도를 최대화하는 것이 목표로 BigCLAM의 파라미터 F(멤버십 강도)는 모델이 생성한 그래프와 실제 그래프 간의 유사성을 최대화하는 방식으로 추정이 진행됩니다. 이는 BigCLAM 모델의 핵심 아이디어 중 하나로, 각 노드의 멤버십 강도를 조절하여 그래프의 구조를 유연하게 표현할 수 있도록 합니다.