Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E| \log^*|V|)$ Time
원문 초록
Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime $n^{1-o(1)} \leq K \leq o(n).$ A critical parameter is the effective signal-to-noise ratio $\lambda=K^2(p-q)^2/((n-K)q)$, with $\lambda=1$ corresponding to the Kesten-Stigum threshold. We show that a belief propagation algorithm achieves weak recovery if $\lambda>1/e$, beyond the Kesten-Stigum threshold by a factor of $1/e.$ The belief propagation algorithm only needs to run for $\log^\ast n+O(1) $ iterations, with the total time complexity $O(|E| \log^*n)$, where $\log^*n$ is the iterated logarithm of $n.$ Conversely, if $\lambda \leq 1/e$, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying power iteration to the non-backtracking matrix of the graph is shown to attain weak recovery if and only if $\lambda>1$. In addition, the belief propagation algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all $K \ge \frac{n}{\log n} \left( \rho_{\rm BP} +o(1) \right),$ where $\rho_{\rm BP}$ is a function of $p/q$.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Community and hyperedge inference in multiple hypergraphs
Communities in the Kuramoto Model: Dynamics and Detection via Path Signatures
VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates
A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks
베테-헤시안을 이용한 커뮤니티 검출
Community detection with the Bethe-Hessian
Saade, Krzakala, Zdeborov\'a (2014)가 도입한 베테-헤시안 행렬은 희소 네트워크에 스펙트럴 클러스터링 알고리즘을 적용하기 위해 고안된 에르미트 행렬이다. 비대칭이며 고차원인 비역추적 연산자를 사용하는 대신, 베테-헤시안 행렬에 기반한 스펙트럴 방법 역시 희소 확률적 블록 모형(SBM)에서 케스텐-스티검 검출 임계값에 도달할 것으로 추측된다. 우리는 유계 기대 차수와 증가하는 차수의 두 영역 모두에서 SBM의 베테-헤시안 스펙트럴 방법에 대한 최초의 엄밀한 분석을 제공한다. 구체적으로 다음을 보인다. (i) 기대 차수 $d\geq 2$일 때, 베테-헤시안 행렬의 음의 이상치 개수는 케스텐-스티검 임계값 이상에서 블록의 수를 일치적으로 추정할 수 있으며, 따라서 $d\geq 2$에 대한 Saade, Krzakala, Zdeborov\'a (2014)의 추측을 확인한다. (ii) 충분히 큰 $d$에 대해, 그 고유벡터를 이용하여 약한 복원을 달성할 수 있다. (iii) $d\to\infty$일 때, 음의 이상치 고유값 위치의 집중성을 수립하며, 베테-헤시안 행렬에 기반한 스펙트럴 방법을 통해 약한 일치성을 달성할 수 있다.
노드 유사도, 그래프 표현 학습, 계층적 군집화를 통한 복잡 네트워크의 커뮤니티 탐지
Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering
커뮤니티 탐지는 소셜, 인용, 생물학적 네트워크 등 다양한 실제 그래프를 분석하는 데 있어 중요한 과제이다. 본 논문은 이 과제를 다루기 위한 세 가지 새로운 일반 계층적 프레임워크를 제안한다. 제안한 접근법은 다양한 연결 기반 군집화 알고리즘, 정점 근접도 행렬, 그래프 표현 학습 모델을 지원한다. 우리는 확률적 블록 모델 그래프와 실제 데이터셋에서 364개의 모듈 조합을 비교한다. 최상의 파이프라인(Wasserman-Faust 및 상호 정보량 기반 PPMI 근접도, 그리고 딥러닝 기반 DNGR 표현)이 최첨단 Leiden 및 Louvain 알고리즘과 대등한 성능을 보임을 관찰한다. 동시에 후자와 달리 이 파이프라인들은 계층적 특성을 유지한다. 따라서 서로 호환되는 모든 가능한 개수의 중첩된 분할 계열을 출력한다. 이 특성은 올바른 분할 개수를 미리 알 수 없을 때 매우 중요하며, 분할 품질 측면에서 실질적으로 거의 비용 없이 얻어짐을 보인다. 작은 커뮤니티가 많이 모인 그래프에서는 우리의 파이프라인이 기준 솔루션보다 더 정확하다. 다만 우리 접근법의 단점은 시간 복잡도로, 개인용 컴퓨터에서는 프레임워크가 약 10000개 정점 규모의 네트워크로 제한된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.