  Recently network analysis has gained more and more attentions in statistics,
as well as in computer science, probability, and applied mathematics. Community
detection for the stochastic block model (SBM) is probably the most studied
topic in network analysis. Many methodologies have been proposed. Some
beautiful and significant phase transition results are obtained in various
settings. In this paper, we provide a general minimax theory for community
detection. It gives minimax rates of the mis-match ratio for a wide rage of
settings including homogeneous and inhomogeneous SBMs, dense and sparse
networks, finite and growing number of communities. The minimax rates are
exponential, different from polynomial rates we often see in statistical
literature. An immediate consequence of the result is to establish threshold
phenomenon for strong consistency (exact recovery) as well as weak consistency
(partial recovery). We obtain the upper bound by a range of penalized
likelihood-type approaches. The lower bound is achieved by a novel reduction
from a global mis-match ratio to a local clustering problem for one node
through an exchangeability property.
