  In this paper, we consider networks consisting of a finite number of
non-overlapping communities. To extract these communities, the interaction
between pairs of nodes may be sampled from a large available data set, which
allows a given node pair to be sampled several times. When a node pair is
sampled, the observed outcome is a binary random variable, equal to 1 if nodes
interact and to 0 otherwise. The outcome is more likely to be positive if nodes
belong to the same communities. For a given budget of node pair samples or
observations, we wish to jointly design a sampling strategy (the sequence of
sampled node pairs) and a clustering algorithm that recover the hidden
communities with the highest possible accuracy. We consider both non-adaptive
and adaptive sampling strategies, and for both classes of strategies, we derive
fundamental performance limits satisfied by any sampling and clustering
algorithm. In particular, we provide necessary conditions for the existence of
algorithms recovering the communities accurately as the network size grows
large. We also devise simple algorithms that accurately reconstruct the
communities when this is at all possible, hence proving that the proposed
necessary conditions for accurate community detection are also sufficient. The
classical problem of community detection in the stochastic block model can be
seen as a particular instance of the problems consider here. But our framework
covers more general scenarios where the sequence of sampled node pairs can be
designed in an adaptive manner. The paper provides new results for the
stochastic block model, and extends the analysis to the case of adaptive
sampling.
