Clustering

이 글은 구글이 2017년 KDD에서 발표한 논문 Ego-Splitting Framework: from Non-Overlapping to Overlapping Clusters를 정리한 글입니다. 왜 비중첩 클러스터링만으로는 부족한가 현실의 네트워크에는 보통 중간 크기(대략 100명 안팎)의 커뮤니티가 다수 존재하고, 하나의 노드가 여러 커뮤니티에 동시에 걸쳐 있는 경우가 흔합니다. 그런데 기존의 비중첩(non-overlapping) 클러스터링 알고리즘들은 각 노드를 정확히 하나의 커뮤니티에만 배정하기 때문에, 이런 실제 네트워크 구조를 제대로 포착하지 못합니다. 물론 중첩(overlapping) 클러스터링을 시도하는 알고리즘들도 이미 여럿 있었지만, 대체로 지나치게 복잡하거나 유연성이 떨어졌고, 이론적인 보장도 부족했습니다. ...