CS224W - 04.Community Structure in Networks
- CS224W의 4주차 강의, Community Structure in Networks를 보고 정리한 글입니다.
1. Community Structure in Networks
2. Network Communities
3. Louvain Algorithm
4. Detecting Overlapping Communities: BigCLAM
Community Structure in Networks
Chapter03.
Role
에 대한 공부.
Chapter04:Community
에 대한 공부- 결국, 이번 챕터의 목적은 ‘서로 간에 밀접하게(Densely) 연결된 노드들의 집합을 찾는 것’
- 클러스터의 개념으로 이해해도 좋을 듯
Community에 대한 알고리즘적인 논의 이전에, Community에 대한 ‘시회과학적’인 논의로 먼저 시작.
- ‘Mark Granovetter’ 박사: 1960년대에 ‘사람들이 과연 어떻게 새로운 직장을 찾는가?’에 대해 연구
놀라운 그의 발견: ‘사람들은 그들의 (자주 만나는) ‘친한 친구’가 아니라 (드물게 만나는)
지인(Acquaintances)
에게 연락한다. 왜?- 이에 대한 그의 답 (이론)
- “Friendship을 두 가지 관점으로 바라볼 수 있다.”
Structural
perspective: 링크가 네트워크의 어떤 부분을 연결하는가?Interpersonal
perspective: 누군가로의 링크가 Strong한가 Weak한가?
#### Structural role: Triadic Closure
Triadic Closure
라는 개념
(= High clustering coefficient)
- 어떤 edge가 더 일어날 법한가? 답은 ‘a-b’
a-c는 네트워크 상에서 3 steps away, 하지만 a-b는 공통된 두 명의 친구를 갖고 있다.
공통된 친구를 갖고 있으면, 그들 또한 친구가 될 가능성이 더 높다.
- “Edge (Link)를 두 가지 관점에서 바라볼 수 있다.”
Structure
의 관점
- 구조적으로 단단히 결속된 Edge들 (Structurally embedded edges)들은 Socially strong
- 네트워크의 다른 부분들에 걸쳐있는 (spanning) Long-range Edges들은 Socially weak
Information
의 관점- Structurally embedded edges들은 정보 접근의 관점에서 몹시 redundant
- Long-range Edges들은 네트워크의 다른 부분들로부터 정보를 들을 수 있게 돼 새 직업을 얻는 데에 도움이 됨
- “Friendship을 두 가지 관점으로 바라볼 수 있다.”
- 이에 대한 그의 답 (이론)
이 이론은, 2007년에, Onnela에 의해 증명됨
- 사용한 데이터: EU 소속 국가 인구의 20%의 휴대폰 네트워크 데이터
Edge Weight는 통화횟수로 정의
결과: 통화횟수가(=Inter-personal strength of friendship) 많을수록, 정말 Neighbor Overlap 지수 또한 높아지더라.
-> 이는 Mark Granovetter 박사의 이론의 Triadic Closure을 증명한 것으로 보임.아래는 이해를 돕기 위한 이미지
- Edge Removal by Strength, Link Removal by Overlap 실험도 같은 결과를 말해줌
-> ‘정말로 Strong ties/edges를 가진 Communities라는 게 존재한다.’
- Edge Removal by Strength, Link Removal by Overlap 실험도 같은 결과를 말해줌
결국, '사람들이 새로운 직업을 찾을 때 평소에 자주 보는 친한 친구들이 아닌, 간간히 보는 지인들을 통해서 찾는 경향이 강한' 이유는, Mark Granovetter 박사의 이론에 따르면, 'Link' 혹은 'Edge'는 연결된 양상이 친분의 성격을 나타내어줄 수 있고 (Structural), 또 그 친분 간에는 경중을 따질 수 있는데(Interpersonal), 이들을 종합해 보았을 때, 가까운 친구들보다는 지인들이 사회적인 유대는 적을 수 있지만(socially weak), 오히려 더 유익한 정보를 많이 가져다 준다는 점에서 Acquaintance로 부터 새로운 직업을 찾는 경향이 많은 것. 그리고 이는 2007년에 실데이터를 사용하여 증명함.
Network Communities
- Granovetter 박사의 이론에 따르면 ‘네트워크는 단단하게 연결된 (Tightly connected) 노드들의 집합들’로 구성되어 있다.
- Network Communities에 대한 정의
- 내부적으로는 수많은 연결들로, 외부적으로는 적은 연결들로 구성된 노드들의 집합
- cf. Communities = clusers = groups = modules
그럼, 이 Communities를 어떻게 발견할 수 있을까?
답:
Modularity
라는 개념을 도입할 것이고, 우리는 Modularity를 Maximize하는 바로 그 Communities를 찾아내면 된다.
We can identify communities by mazimizing modularity.
Communities: 단단히 연결된 노드들의 집합 (sets of tightly connected nodes)
Modularity
Q
- 네트워크가 communities로 얼마나 잘 나누어져(partitioned) 있는가에 대한 측정
- Partitioned된 Disjoint communities에 대해 Modularity를 다음과 같이 계산
- 다음 식의 값을 크게 만드는 Communities 그룹을 찾는 게 목적이고, 이를 얻어내기 위해서는 Null Model이 필요한데, 앞서 3강에서 했던 ‘Configuration Model’의 사고 적용
- Configuration Model
- Community가 얼마나 잘 Partitioned 되어있는지를 평가하기 위해 필요한 ‘비교 기준’이 되는 모델
- Real graph G가 있으면, 이 그래프에서 Node의 개수(m)와 Edge의 개수(n)는 알 수 있음.
- 이를 갖고 Rewired network G’를 만든다!
- 특징
- 특징
- Modularity 계산의 정확한 식을 나타내면 다음과 같은 식이 도출
생각해보면, Configuration Model은, 실제 그래프의 Degree Distribution은 지키되, 아무렇게나 만들어낸 모델인데, Q(G,S) 값이 크다는 말은, 아무렇게나 만드는 모델보다, 이 현실 그래프 자체가 뭔가 유의미함을 담고 있다는 것이고, 따라서 Communities의 존재 또한 타당하다고 평가할 수 있을 것 같음.
- Modularity 값은 -1과 1사이의 값.
보통 0.3과 0.7 사이 정도면
Significant Community Structure
가 있음을 의미- Modularity를 아래와 같이 다른 form으로도 나타내어 볼 수 있음
Louvain Algorithm
- Community detection을 위한
Greedy Algorithm
시간복잡도 O(nlogn), 이 때 n은 노드의 개수
- 가중치 그래프도 지원하고, Hierarchical communities detection도 가능
- cf. Dendrogram을 통해 네트워크의 Hierarchical한 구조를 나타낼 수 있다.
- cf. Dendrogram을 통해 네트워크의 Hierarchical한 구조를 나타낼 수 있다.
- 네트워크에 널리 사용된다.
- 빠르고, 수렴도 빠르고, High
Modularity
output을 도출해주기 때문
- 빠르고, 수렴도 빠르고, High
- 요컨대, Louvain algorithm
greedily
maximizes modularity
Louvain Algorithm의 Process에 대한 설명
- 매 pass 마다 두 phases를 지난다.
- Phase1:
Partitioning
orOptimization
- Node-Communities 멤버들간의 오직 local change를 통해 Modularity를 optimize
- Phase2:
Aggregation
- 새 네트워크를 만들기 위해, Phase1을 통과한 결과들을 Super-nodes로 Aggregate
Phase1, 2를 Modularity의 증가가 없을 때까지 Iteratively Repeat
- Phase1:
각 Phase에 대해 조금 더 구체적으로 들어가보자.
Phase1 (Partitioning)
- 각 노드를 Distinct 한 Community 에 넣는다.
- 각 노드 i에 대해 Louvain 알고리즘은 두 가지 연산을 진행
- 연산1: 노드 i를 어떤 neighbor j의 community 속에 넣으면 발생하는 modularity 값의 변화량을 측정 (Modularity delta: ΔQ)
- 연산2: 노드 i를, 가장 큰 ΔQ를 발생시키는 community로 이동
ΔQ의 변화가 없을 때까지 Phase1 계속 실행
물론, 노드를 택하는 순서가 결과에 영향을 주기는 하지만, 그렇다고 이 순서가 결과에 큰 영향을 주는 것은 아니기 때문에 보통 이에 대해 큰 주의를 기울이진 않음.
여기서 말하는 ΔQ는 어떻게 계산하나?
- 뿐만 아니라, 현재 속한 Community가 D라면, ΔQ(D→i) 또한 쉽계 계산해낼 수 있음.
ΔQ식 더 자세히 보기
- 뿐만 아니라, 현재 속한 Community가 D라면, ΔQ(D→i) 또한 쉽계 계산해낼 수 있음.
Phase2 (Restructuring)
- Phase1에서 얻어진 communities를 super-nodes 로 압축!
- Super-node들 사이에 하나의 Edge라도 있으면 연결!
- 두 Super-node 간의 edge 가중치는 커뮤니티 간 모든 Edge 가중치들의 합
- 다시 Phase1으로 (한 개의 Community를 찾을 때까지 계속 반복하면 된다)
Pseudo-Code
요약
* Modularity - 그래프를 Community들로 나눌 때의 평가 기준이 됨 - Community들의 숫자를 결정 * Louvain Modularity Maximization - Greedy한 알고리즘 - 성능 좋고, 큰 사이즈의 네트워크에도 확장성도 좋다
Detecting Overlapping Communities: BigCLAM
- 앞에서의 Community들은 모두 Non-Overlapping 이었음.
Overlapping Community를 Detect할 수 있는 방법은 없을까?
- 역시 2가지 Step으로 구성
- Step1
- Node Community affiliation에 근거하여 graph generative model을 정의
- 여기서는 그 모델로
Community Affiliation Graph Model (AGM)
모델을 다룰 것
- Step2
- Graph G가 AGM을 통해 만들어졌다는 가정 하에, best AGM을 찾자!
(= Step1에서 AGM 모델을 정의한 이후, MLE를 찾겠다.)
- Graph G가 AGM을 통해 만들어졌다는 가정 하에, best AGM을 찾자!
- Step1
AGM
- Generative Model : Community affiliation으로부터 어떻게 네트워크가 generate되는가?
- Model Parameters: V, C, M, {p_c}
- V: Nodes
- C: Communities
- M: Memberships
- p_c: Community C의 노드들이 서로 연결되어 있을 Likelihood
- 이 때, 다수의(multiple) communities에 속해있는 노드들은 multiple coin flips!
- p(u,v): u,v가 서로 연결되어 있을 확률
- 공통된 그룹의 수가 많을수록 연결될 가능성이 커짐
- 이 때, 다수의(multiple) communities에 속해있는 노드들은 multiple coin flips!
- 예시
- AGM은 Overlapping 양상에 따라서 다양한 Community Structure를 표현할 수 있음
(Non-Overlapping, Overlapping, Nested 모두 표현 가능)
의문: Model로부터 Graph를 Generate하고 있는데, Graph가 있으면 Model을 얻을 수는 없을까?
- Maximum Likelihood Estimation 사용
- Given 그래프를 G라고 하면 다음식을 만족하는 F (model/parameter)를 찾으면 된다.
- “모델을 받아서, 이를 Graph Generation에 사용하고, 이 graph가 real graph와 가장 비슷하도록!”
- “Model Parameter가 주어졌을 때, 내 Graph Probability를 측정할 수 있다면, argmax를 찾아보자!”
- F,G가 주어졌으면, F가 G를 Generate할 Likelihood를 구해보자.
‘AGM’ 모델의 Relaxing 같은 교수님의 Relaxing AGM에 대한 설명
- 위의 모델은 0,1을 사용하여 노드들이 given community의 member인지아닌지를 따짐
- 하지만 그보다, 모든 node community membership의 strength를 따져보자는 접근 -> “Relax” the AGM!
-> 기존의 문제를, 모든 노드에 대해 Vector F를 찾는 문제로 바꾸어 놓음
BigCLAM Model
노드 u와 v가 연결되어 있을 확률은, shared memberships의 strength에 비례함
결국 BigCLAM 모델은 네트워크 G(V,E)가 주어졌을 때, 다음 l(F)를 Maximize하는 F를 찾는 것