[CS224W] 4. Community Structure in Networks

(다른 할 일이 많아서 그래프 스터디 정리해놓는 것이 조금 미뤄졌습니다.. ㅎㅎ)
4강은 김태욱님께서 리뷰해주셨습니다. 4강은 네트워크에서 커뮤니티는 어떻게 찾을까?(Community Detection) 에 초점을 맞춘 강의입니다. 3강이 새로운 개념을 마구잡이로 주입하는 내용인 것에 반해, 조금은 더 흥미롭게 술술 읽히는 강의였습니다. 

목차

1. Community Structure in Networks
2. Network Communities
3. Louvain Algorithm
4. Detecting Overlapping Communities : BigCLAM

 

1. Community Structure in Networks

이번 챕터는 서로간에 밀접하게(densely)하게 연결된 노드들을 구분하는 것이 목적입니다. 

먼저 네트워크에서 정보가 흐르는 것에 대해서 알아보겠습니다. 

Q. 사람을은 사람 소개로 정보를 얻을 때 어떻게 정보를 얻을까? (People find the information through personal contacts?)

-> A. 아주 친한 사람(친구)보다는 지인을 통해 정보를 얻음 (Contacs were often acquaintances rather than close friends)

Granovetter's Answer

아주 친한 친구보다는 지인을 통해 직장을 찾는 것은 friendships에 두가지 측면이 있다는 것으로 설명됩니다.

• Structural : 링크가 어떤 부분을 연결하는가?
• Interpersonal : 어떤 링크가 더 강하고 약한가?

Structural role : Triadic Closure 

Triadic closure = High clustering coefficient 입니다.

a-c 보다 a-b가 더 연결될 가능성이 높은 edge입니다. 두 명의 공통된 노드를 가지고 있기 때문입니다. 

 

 

 

Granovetter's Explanation

따라서 Granovetter는 사회구조의 edge가 연결되는 role을 구조적, 정보적 측면에서 정의했습니다.

• Structural
  • 구조적으로 가까운(결속된) edge 들은 사회적으로도 강하게 연결됨
  • 서로 다른 네트워크를 연결하는 장거리 edge들은 사회적으로도 약하다.
• Information
  • 구조적으로 가까운(결속된) edge 들은 정보가 중복된다.
  • 장거리 edge들이 다른 부분에서 새로운 정보를 얻도록 해준다. (지인)

 

Granovetter's theory가 나오고 증명이 되지 않았는데, 50년 후에 real data를 통해 증명되었습니다. 

Edge Strengh in Real Data

EU 소속 국가 인구의 20% 의 휴대폰 네트워크 데이터입니다. edge weight는 통화횟수로 정의했습니다.

결국 O_ij는 교집합/합집합이며, 네트워크에서 얼마나 많은 지인(nodes)를 공유(overlap)하고 있는가에 대한 정보를 나타내는 수치입니다. 지인을 많이 공유할 수록 1에 가까워집니다.

 

 

2. Network Comminities

Granovetter's theory 에 따르면 network는 강하게 연결된 노드들의 집합입니다. 

• Network Comminities : 내부적으로 연결된 많은 노드들과 몇몇의 외부적인 노드들로 이루어진 집합입니다.
• Modularity Q : 노드간의 연결성을 정의하는 metric, 네트워크가 커뮤니티로 얼마나 잘 나뉘어져 있는지
• Q = (# of deges withing group s) - (expected # edges within group s) 
  • expected # edges within group s <- 을 찾기 위해 configure moel(null model) 사용

 

위의 내용과 같이 null model을 만든 후에 Modularity를 구해줍니다. Modularity는 [-1,1] 사이의 값이며, 음수인 경우는 서로간에 거의 상관이 없는, 연결되어 있지 않은 comminity를 정의한 것이고 보통 0.3~0.7 정도가 의미있는 communinity structure라고 합니다. 

 

modularity를 최대화 시켜서 communities를 정의할 수 있고, Equivalently modularity 는 0또는 1의 델타를 써서 다음과 같이 나타냅니다.

 

 

3. Louvain Algorithm

• Louvain Algorithm 은 Community detenction을 위한 Greedy algorithm으로 시간복잡도 O(nlogn)을 가집니다. 
• weighted graph에 사용되고 hierarchical communities 또한 찾을 수 있습니다.
• 빠르고, 빠른 수렴이 가능하며 High modularity output을 도출해주기 때문에 널리 사용됩니다.
• 큰 스케일의 large network에서 성능이 좋습니다.
• 두 가지 단계를 통해서 greedily 하게 modularity를 최대화 시키는 것이 핵심입니다. 

(각 단계에 대한 설명은 태욱님의 설명에서 발췌해왔습니다.)

Modularity Gain

다음 그림으로 이해하는 것이 더 쉽습니다.

(오) 계산 설명

 

 

4. Detecting Overlapping Communities : BigCLAM

 

실제 real world는 overlapping comminities의 형태를 띄는 경우가 많습니다. overlapping의 경우 인접행렬(Adjacency matrix) 또한 겹치는 부분이 존재하게 됩니다. Overlapping Community를 Detect할 수 있는 방법을 보겠습니다.

• Step1
  • Node community affiliations에 근거하여 graph를 위한 generative model을 정의합니다.
  • Community Affiliation Graph Model (AGM)
• Step2
  • Graph G 가 AGM을 통해 만들어졌다는 가정 하에 진행
  • generated된 G를 가지도록 best AGM을 찾음 (AGM이 G를 generative하도록 파라미터를 학습시킴, MLE)
  • 이 방법을 통해 communities를 발견할 수 있음 (파라미터는 node가 community에 얼마나 속하는지 알려줌)

Community Affiliation Graph Model (AGM)

왼쪽 그림은 Community Affiliation을 보여줍니다. (커뮤니티끼리 제휴되어 있는 모습) A, B가 communities이고 밑의 점들이 네트워크의 노드들로 커뮤니티와 연결되어 있는 모습을 나타냈습니다. 이를 모델로 표현하면 오른쪽의 Network 형태가 됩니다. (P_A는 커뮤니티 A가 가지고 있는 확률입니다.)

따라서 Generative Process는 다음과 같이 이뤄집니다.

• model parameters : (V, C, M, {p_c}) 주어짐
• community c의 노드가 각 노드들과 연결될 확률 p_c
• 여러 커뮤니티에 연결된 노드들은 여러번의 사건을 가짐

 

AGM이 모델로 Network를 생성하는 과정은 위와 같습니다. 이제는 Graph(네트워크) 가 주어졌을 때, Model(F) 를 찾아보도록 하겠습니다.

 

Graph Fitting / Graph Likeligood P(G|F)

• Maximum Likelihood Estimation 사용
• 파라미터(F)주어질 때, 그래프(G)의 확률
• F가 주어질 때 G가 나올 확률(Graph Probability)를 구하고, 이 확률을 최대화 시키는 F를 찾으면 됩니다. (argmax)

-> (1) F가 주어졌을 때 G가 나올 확률을 구하고, (2) 이 확률을 최대화 시키는 F를 찾아보겠습니다. 

 

왼쪽 그림과 같이 P(G|F)를 구하고 오른쪽 그림과 같이 F를 정의해서 찾습니다. 오른쪽 그림은 이전에는 특정 커뮤니티와의 연결여부만을 0,1로 나타냈던 것과 다르게 모든 node community들과의 strength를 따졌습니다. 

 

BigCLAM Model

위의 과정들을 정리한 것이 BigCLAM Model 입니다. 이에 대한 것을 정리해보면 다음과 같습니다.

(1) F가 주어졌을 때 G가 나올 확률을 구하고, (2) 이 확률을 최대화 시키는 F를 찾는다  -> 이 자체가 BigCLAM Model의 핵심입니다. 

 

• P(u,v) 는 노드 u 와 v 가 각각의 커뮤니티에 동시에 속할 확률입니다. 이는 shared membership에 비례합니다.
• -> 본직적으로 공통된 것이 서로 많으면 강하게 결속되어 있는 것이기 때문에, 값이 크다면 연결성이 큰 것입니다.
• 안정화를 위해 log 를 덧씌운 log-likelihood 를 사용해서  l(F)를 정의했고, 최적화(optimization)은 gradient ascent를 통해서하는데 시간이 오래걸립니다.

 

 

Reference

Stanford CS224W 2019
스터디 4강 리뷰 자료 velog.io/@tobigs-gnn1213/4.-Community-Structure-in-Networks

4. Community Structure in Networks