정보 기반 복제 상관관계를 통한 메가스케일 네트워크의 다중 해상도 커뮤니티 탐지

우리는 Potts 모델 커뮤니티 탐지 알고리즘을 사용하여 그래프의 계층적 또는 다중 해상도 구조를 정확하고 정량적으로 평가합니다. 우리의 다중 해상도 알고리즘은 동일한 그래프의 여러 복제("복제본") 간의 상관관계를 다양한 해상도에서 계산합니다. 강한 상관관계를 가진 복제본에 의해 중요한 다중 해상도 구조가 식별됩니다. 평균 정규화된 상호 정보, 정보의 변동 및 기타 측정치는 원리적으로 "최상의" 해상도에 대한 정량적 추정을 제공하고 그래프의 구조의 상대적 강도를 나타냅니다. 이 방법은 정보 비교를 기반으로 하기 때문에, 원칙적으로 다중 해상도를 탐색할 수 있는 커뮤니티 탐지 모델과 함께 사용할 수 있습니다. 우리의 접근법은 다른 최적화 문제로 확장될 수 있습니다. 지역 측정으로서, 우리의 Potts 모델은 다른 인기 있는 모델에 영향을 미치는 "해상도 한계"를 피합니다. 이 모델을 사용하여, 우리의 커뮤니티 탐지 알고리즘은 현재 사용 가능한 방법 중에서 가장 높은 정확도를 자랑합니다. 이를 통해 우리는 40 x10;6개의 노드와 1 x10;9개 이상의 엣지를 가진 그래프를 검사할 수 있습니다. 우리는 또한 알고리즘의 다중 해상도 변형이 단일 프로세서에서 최소 200,000개의 노드와 10 x 10;6개의 엣지를 놀라울 정도로 높은 정확도로 해결할 수 있음을 보고합니다. 전형적인 경우에 대해, 우리는 커뮤니티 탐지에 대해 초선형 스케일링 O (L1.3)와 다중 해상도 알고리즘에 대해 O (L1.3 log N)을 발견하는데, 여기서 L은 엣지의 수이고 N은 시스템의 노드 수입니다.