Community Detection

sheep·2021년 6월 27일

BigCLAM CS224W Community Detection GNN Spectral Clustering louvain

GNN

목록 보기

6/6

CS224W의 Community Structruture in Networks 강의와 Spectral Clutering 강의 부분을 정리한 글입니다.

아래 4가지 알고리즘에 대한 내용을 알아봄

Louvain 알고리즘
BigCLAM
Spectral Clustering
Motif-based Spectral Clustering

1. Community Structruture in Networks

Granovetter Theory

커뮤니티 탐지는 서로 밀집하게(densely)하게 연결된 노드를 구분하는 것이 목적

Q. 사람들은 개인적인 소개로 구직 정보를 얻을 때 어떻게 정보를 얻을까?

→ 친구보다는 지인을 통해 정보 얻음

친한 친구보다 지인을 통해 직장을 찾는 것은 friendships에 두 가지 측면이 있다는 것을 말함

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

Structural role : Triadic Closure(= High Clustering Coefficients)

a-c보다 a-b가 두 명의 공통 노드를 공유하기 때문에 더 연결될 가능성이 높은 edge 임

Granovetter의 설명(Granovetter Theory)

사회 구조의 edge가 연결되는 role은 구조적, 정보적 측면에서 정의
- Structural
  - 구조적으로 가까운 edge들은 사회적으로도 강하게 연결
  - 서로 다른 네트워크를 연결하는 장거리 edge들은 사회적으로도 약하다
- Information
  - 구조적으로 가까운 edge 들은 정보가 중복됨
  - 장거리 edge들이 다른 부분에서 새로운 정보를 얻게 해줌(지인)

2. Network Communities

Modularity

Granovetter Theory에 따르면 Network는 강하게 연결된 노드의 집합
Nework Communities
- 내부적으로 연결된 많은 노드들과 몇개의 외부적인 노드들로 이ㅣ루어진 집합
Modularity Q
- 노드간의 연결성 나타내는 Metric, 네트워크가 커뮤니티로 얼마나 잘 나뉘어졌는지 측정하는 척도
  
  $Q = \sum(\# of \quad degrees \quad within \quad groups) - (expected\quad \#edges\quad within\quad groups)$
- 위의 Expected term을 찾기 위해 Configure model(null model) 사용
- Modularity 의 특징은 [-1,1] 구간 값을 가짐
- 해석은 음수면 서로 상관 관계가 거의 없고, 0.3~0.7정도면 의미있는 커뮤니티 정보라 볼 수 있음

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

2m 은 normalize constant를 위한([-1,1] 구간으로 만들기 위한) 정규화 상수
$A_{ij}$ 는 연결되어 있으면 ? 1 아니면 0

Modularity 는 아래 식으로 다시 나타낼 수 있음(증명 생략)

$Q = {{1}\over{2m}} \sum_{ij}(A_{ij}- {{k_ik_j}\over{2m}}) \delta(C_i,C_j)$

$A_{ij}$ : 노드 i와 j 사이의 Edge weight
$2m$ : 그래프 안의 모든 edge weight의 합
$\delta(C_j,C_j)$ : 두 노드가 같은 커뮤니티면 1, 아니면 0

3. Louvain Algorithm

커뮤니티 탐지를 위한 greedy algorithm. 시간 복잡도 O(nlog(n))
weighted graph에 사용하며 hierarchical community를 찾을 수 있다함
Large graph 에서 성능이 잘 나온다함
두 phase로 이루어진 학습과정을 통해 greedy하게 modularity를 최대화 하는 알고리즘임

non-overlaps 알고리즘 설명

phase1

1) 각 노드가 single community라 생각

2) 노드 i를 어떤 이웃 j의 community에 넣으면 modularity값이 얼마나 증가하는 지 $\Delta Q$ 를 측정

3) 노드i를 가장 큰 $\Delta Q$ 를 발생시키는 community 로 이동 시킴

4) $\Delta Q$ 변화가 없을대까지 phase1를 반복

phase2

1) phase1의 결과 얻은 communities를 모아 single super node를 만듬

super-node 사이에 하나의 edge라도 있으면 연결
두 sper-node 사이에 edge 가중치는 커뮤니티 간 모든 edge 가중치의 합

2) 다시 phase1으로 돌아가 한 개의 community 를 찾을 때 까지 과정을 반복함

4. Dectecting Overlapping Communities : BigCLAM

실제 real world graph는 overlapping communities의 형태를 갖는 경우가 많다.
Overlapping의 경우 인전행렬 또한 겹치는 부분이 존재

overlaps 알고리즘 설명

STEP1.

Node community affilations에 근거해 graph를 위한 generative model 정의
Community Affiliation Graph Model(AGM)

STEP2.

Graph G가 AGM을 통해 만들어졌다는 가정을 가짐
generated 된 G을 가지도록 최적의 AGM을 찾음 → AGM이 G을 generative 하도록 모델 파라미터 학습
위의 과정을 통해 커뮤니티를 찾을 수 있으며 각 파라미터는 노드가 커뮤니티에 얼마나 속하는 지 알려줌

Generative process

model parameter : $(V,C,N,P_c)$
$P_c$ : community C의 노드가 각 노드와 연결될 확률
$P(u,v) = 1- \prod_{c\in M_u and M_v}(1-P_c)$

모델 파라미터(F)가 주어질 때, 그래프(G)가 생성될 확률을 구하고, 이 Likelihood을 최대화 하는 F를 찾음

$P(u,v)$ : 노드 u, v가 커뮤티티에 동시에 속할 확률
MLE를 통해 $P$ 를 최대화하는 F의 파라미터를 찾음

5. Spectral Clustering

Spectral Clustering의 개요

알고리즘은 3단계로 구성

1) Pre-processing

그래프를 표현하는 matrix 생성(Degree Matrix, Adejacency Matrix, Laplacian Matrix)

2) Decomposition(행렬 분해)

matrix의 eigen value와 eigen vector를 계산
행렬을 eigen value와 eigen vector 기반으로 저차원으로 mapping

3) Grouping

행렬 분해를 통해 얻은 새로운 representation(eigen vector)로 2개 이상 Cluster를 만들고, 각 data point들을 Cluster에 할당

Partitioning 에 대한 용어 및 개념 설명

Graph Partitioning

Q. 어떻게 그래프를 좋은 partition으로 나눌 것인가?

Q. 어떻게 효율적으로 partition을 정의할 것인가?

→ 그룹 내 노드간의 연결을 최대화 하면서 그룹 간 연결을 최소화 하는것이 좋은 Partitioning(일반 군집화 알고리즘의 클러스터링 평가와 일치하는 느낌)

Graph Cuts

cut : set of edges with one endpoint in each
$cut(A,B)=\sum_{i\in A, j \in B}W_{ij}$

minimum-cut
- 그룹들간의 연결 weight릃 최소화 함
- cluster 외부의 연결에만 집중하고, 내부의 연결성은 고려하지 않은 문제점이 있음 → Conductance를 고려하여 해결

Conductance
- 군집 내부의 연결성을 고려(군집 내 Density를 반영)
- 각 그룹간의 Density는 상대적이므로 Cut을 각 그룹의 Volume으로 나눠 구함
- 따라서 더 균형을 갖춘 Partitioning을 할 수 있음
- 그러나, 최적의 Conductance를 찾는 문제는 NP-Hard

따라서 Conductance를 구하는 과정에서 eigenvalue와 eigenvector를 이용하는 방법을 선택하는 것

Spectral Graph Partitioning

Q. A * X 의 의미?

A * X의 선형변환은 노드 i의 이웃인 j의 라벨들의 합
$y_i = \sum_{j=1}^{n}A_{ij}x_j = \sum_{(i,j) \in E}x_j$

Spectral Graph Theory는 Matrix Representing G의 Spectrum을 분석하는 방법

spectrum : 그래프의 eigenvector $x_i$ 는 eigen value $\lambda_i$ 의 크기 순으로 정렬한 것

예시) d-regular graph(모든 노드가 동일 degree를 가진 그래프)

Q. $Ax = \lambda x$ 에서 $\lambda$ 와 $x$ 는 무엇인가?

$x$ 를 (1, 1, ... , 1) 벡터라 하자.
그러면 $Ax = (d,d,...,d) = \lambda x$ 이 되고 $\lambda=d$ 가 됨
$d$ 는 $A$ 의 가장 큰 eigen value이며, $A$ 가 n by n 행렬일 때, n개의 eigen vecor, value가 나오게 됨