728x90 반응형 community detection2 [Community Detection] Spectral Clustering Spectral Clustering: Graph Cut with EigenvectorsGraph Partitioning다음과 같은 그래프 $G = (V, E)$에 대하여 우리는 2개의 disjoint group $\{ 1,2,3 \}$와 $\{ 4,5,6 \}$로 partitioning할 수 있다. 그렇다면 어떤게 좋은(good) partition으로 정의할 수 있을까? 어떻게 효율적(efficiently)으로 partition을 구할 수 있을까?좋은 partition은 1) 같은 그룹끼리의 연결은 최대이며 2) 다른 그룹끼리의 연결은 최소화하는 것이다.위 그림을 예시로 들면, 그룹 A, B 내부 노드끼리의 connection은 3개이고, A와 B의 connection은 2개이다.Graph Cutspar.. 2023. 12. 6. [Community Detection] Girvan-Newman (GN) Algorithm Girvan-Newman: Divisive hierarchical clustering based on edge betweennessCommunity Detection우리는 그래프(네트워크)를 여러개의 모듈, 클러스터, 커뮤니티의 집합체로 생각한다.graph를 partitioning하여 micro-market을 찾을 수 있다. 소셜네트워크에서는 서로 겹치는(overlapping) social circle 혹은 circles of trust를 찾을 수 있다. 여기서는 undirected & unweighted network에서의 community detection에 알아보자. Edge betweenness해당 edge를 통과하는 최단거리의 개수 (Number of shortest paths passing t.. 2023. 11. 14. 이전 1 다음 728x90 반응형