1. Community Detection in Networks
1. 1. Granovetter’s Research
•
강의 전반과 강하게 연결되는 내용은 아니지만, close-friend 보다 지인의 중요성 설명
•
강한 친밀도의 친구끼리는 이미 많은 정보가 공유되고 있음
•
Redundant information
1. 2. Triadic Closure
•
B와 C도 연결될 가능성이 높음: Triadic closure
1. 3. Edge Overlap
•
Community 척도를 판단하는 근거로 앞으로 모든 알고리즘은 edge overlap의 파생형에 해당
•
Overlap이 많으면 보통 edge strength도 증가
•
Overlap이라는 index에 대한 정당성 제공
•
Edge strength를 기준으로 할때, edge overlap을 기준으로 할때 둘다 low를 먼저 자를 때 graph가 더 빠르게 파편화 됨
2. Network Communities
2. 1. Social Network Data
•
마치 mincut과 같은 두 community의 분할
2. 2. Modularity Q
•
Overlap을 활용한 보다 체계화된 지표 Q
•
각 node의 degree는 유지한 상황에서 무작위로 edge가 연결되었을 때의 상호 연결성과 현재의 연결성 비교
3. Louvain Algorithm
3. 1. Scheme of Louvain Algorithm
•
주위에서 Q 늘릴 수 있는 greedy한 community search
•
해당 community에 aggregate
3. 2. First Phase of Louvain Algorithm
•
node i에 대해서 주위 community에 하나씩 넣어보면서 제일 좋은 community 고르기
•
node i가 고립된 node일 때는 상관 없지만, 그게 아니면 D에서 i가 빠져나가는 것과 새로 C로 편입되는 과정을 더해야 함
•
Modularity Q를 식 정리로 간단하게 구할 수 있음
•
Community 내부 edge수와 총 edge수를 비교하여 얻음
•
위 식을 node i가 있을 때와 없을 때에 대해서 계산하면 됨
3. 3. Second Phase of Louvain Algorithm
•
Phase 1의 같은 community를 하나의 super node로 보고 반복
4. Detecting Overlapping Communities: AGM & NOCD
4. 1. Overlapping Communities
•
여러 community에 중복해서 들어간 경우를 구현하고자 함
•
Community 소속 정보로 graph 만들고, 그 그래프가 잘 되었는지 확인
4. 2. AGM: Generative Process
•
Community affiliation을 기반을 그래프 생성
•
각 community에 속한 node는 연결될 확률을 갖고, 따라서 여러 community에 함께 속한 node들은 서로 연결됨
•
Community가 주어지면 node 사이의 연결 확률을 만들 수 있는 model이 필요함
•
Strength를 의미하는 F를 활용하여 정의할 수 있음
•
여러개의 community에 속해 있어도, dot product로 비교적 쉽게 계산 가능하고, SGD로 update 가능
•
올바른 그래프를 생성할 수 있도록 loss를 update