프룬드 피벗: 동적, 병렬 및 로컬 컴퓨테이션 모델을 위한 상관 클러스터링 알고리즘

양수 및 음수 엣지 레이블이 있는 그래프가 주어졌을 때, 상관 클러스터링 문제는 노드를 클러스터링하여 클러스터 간의 양수 엣지와 클러스터 내의 음수 엣지의 총수를 최소화하는 것을 목표로 합니다. 이 문제는 데이터 마이닝에서 많은 응용 프로그램이 있으며, 특히 비지도 학습에 적합합니다. 현대 애플리케이션에서 대규모 그래프 및 끊임없이 변화하는 데이터의 일반성을 영감을 받아, 우리는 동적, 병렬(MPC) 및 로컬 컴퓨테이션(LCA) 환경에서 상관 클러스터링에 대해 연구합니다. 우리는 이러한 모든 환경에서 최첨단 런타임 복잡성을 개선하는 접근 방식을 설계했습니다. 특히, 우리는 그래프 크기와 무관하게 예상되는 감가상각 상수 시간에 실행되는 첫 번째 완전 동적 알고리즘을 제공합니다. 또한, 우리의 알고리즘은 유명한 피벗 알고리즘의 근사 보장을 본질적으로 일치시킵니다.