Community Detection in Degree-Corrected Block Models

2016/07/24 by Gao, Chao, Ma, Zongming, Zhang, Anderson Y. +1 · 5 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1607.06993

Abstract

Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCBMs). We first derive asymptotic minimax risks of the problem for a misclassification proportion loss under appropriate conditions. The minimax risks are shown to depend on degree-correction parameters, community sizes, and average within and between community connectivities in an intuitive and interpretable way. In addition, we propose a polynomial time algorithm to adaptively perform consistent and even asymptotically optimal community detection in DCBMs.

Cited by

• Optimal Graph Clustering without Edge Density Signals
• Information Loss and Disparate Effects in Network Embeddings
• Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning
• Biological Processing Units: Leveraging an Insect Connectome to Pioneer Biofidelic Neural Architectures
• Strongly Consistent Community Detection in Popularity Adjusted Block Models

Related

• Minimax Rates of Community Detection in Stochastic Block Models
• Community Detection in the Stochastic Block Model by Mixed Integer Programming
• A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms