지역 고차원 그래프 클러스터링

지역 그래프 클러스터링 방법은 그래프의 작은 지역을 탐색하여 노드 클러스터를 찾는 것을 목표로 합니다. 이러한 방법은 주어진 시드 노드 주변에서의 대상 클러스터링을 가능하게 하며, 입력 그래프의 크기에 의존하지 않기 때문에 전통적인 전역 그래프 클러스터링 방법보다 빠릅니다. 그러나 현재의 지역 그래프 분할 방법은 네트워크에 중요한 고차원 구조를 반영하도록 설계되지 않았으며, 방향성 네트워크를 효과적으로 처리할 수 없습니다. 여기에서는 작은 서브그래프가 포착한 고차원 네트워크 정보를 포함하여 이러한 문제를 해결하는 새로운 유형의 지역 그래프 클러스터링 방법을 소개합니다. 우리는 최소 모티프 전도도를 가진 시드 노드를 포함하는 클러스터를 찾는 모티프 기반 근사 개인화 페이지랭크(MAPPR) 알고리즘을 개발했습니다. 이는 네트워크 모티프의 전도도 메트릭의 일반화입니다. 우리는 기존 이론을 일반화하여 빠른 실행 시간(그래프 크기와 무관함)을 증명하고 클러스터 품질에 대한 이론적 보장을 얻습니다(모티프 전도도 측면에서). 우리는 작은 모티프 전도도를 가진 집합을 찾기 위한 노드 이웃 이론도 개발하였고, MAPPR 알고리즘의 입력으로 사용할 좋은 시드 노드를 찾는 경우에 이러한 결과를 적용합니다. 합성 및 실제 네트워크에서의 커뮤니티 탐지 작업에 대한 실험적 검증은 우리의 새로운 프레임워크 MAPPR가 현재의 엣지 기반 개인화 페이지랭크 방법론보다 우수함을 보여줍니다.