Phase Transitions in Spectral Community Detection of Large Noisy Networks
In this paper, we study the sensitivity of the spectral clustering based community detection algorithm subject to a Erdos-Renyi type random noise model. We prove phase transitions in community detectability as a function of the external edge connection probability and the noisy edge presence probability under a general network model where two arbitrarily connected communities are interconnected by random external edges. Specifically, the community detection performance transitions from almost perfect detectability to low detectability as the inter-community edge connection probability exceeds some critical value. We derive upper and lower bounds on the critical value and show that the bounds are identical when the two communities have the same size. The phase transition results are validated using network simulations. Using the derived expressions for the phase transition threshold we propose a method for estimating this threshold from observed data.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Phase Transitions in the Output Distribution of Large Language Models
In a physical system, changing parameters such as temperature can induce a phase transition: an abrupt change from one state of matter to another. Analogous phenomena have recently been observed in large language models.…
Community Detection and Stochastic Block Models
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fer…
ClusteringCommunity DetectionStochastic Block ModelContinuous Phase Modulation of Phase Coded Transmit Waveforms using Multi-Tone Sinusoidal Frequency Modulation
Phase Coded (PC) waveforms possess desirable Auto-Correlation Function (ACF) properties for use in radar and sonar systems. However, their spectra possess high spectral leakage due to the abrupt phase transitions between…
Phase Transitions in Community Detection: A Solvable Toy Model
Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of $q=2$ groups. However,…
Community DetectionUnsupervised machine learning of quantum phase transitions using diffusion maps
Experimental quantum simulators have become large and complex enough that discovering new physics from the huge amount of measurement data can be quite challenging, especially when little theoretical understanding of the…
BIG-bench Machine LearningClusteringDimensionality Reduction