Information-theoretic Limits for Community Detection in Network Models
This work addresses fundamental theoretical limits for community detection in networks, which is crucial for researchers in network science and machine learning, though it appears incremental as it extends known analyses to additional models.
The paper analyzes information-theoretic limits for recovering node labels in various network models, including Stochastic Block Model, Exponential Random Graph Model, Latent Space Model, Directed Preferential Attachment Model, and Directed Small-world Model, deriving non-recoverability conditions based on model-specific parameters such as edge probabilities, latent space dimensions, and homophily ratios.
We analyze the information-theoretic limits for the recovery of node labels in several network models. This includes the Stochastic Block Model, the Exponential Random Graph Model, the Latent Space Model, the Directed Preferential Attachment Model, and the Directed Small-world Model. For the Stochastic Block Model, the non-recoverability condition depends on the probabilities of having edges inside a community, and between different communities. For the Latent Space Model, the non-recoverability condition depends on the dimension of the latent space, and how far and spread are the communities in the latent space. For the Directed Preferential Attachment Model and the Directed Small-world Model, the non-recoverability condition depends on the ratio between homophily and neighborhood size. We also consider dynamic versions of the Stochastic Block Model and the Latent Space Model.