  Predicting labels of nodes in a network, such as community memberships or
demographic variables, is an important problem with applications in social and
biological networks. A recently-discovered phase transition puts fundamental
limits on the accuracy of these predictions if we have access only to the
network topology. However, if we know the correct labels of some fraction
$\alpha$ of the nodes, we can do better. We study the phase diagram of this
"semisupervised" learning problem for networks generated by the stochastic
block model. We use the cavity method and the associated belief propagation
algorithm to study what accuracy can be achieved as a function of $\alpha$. For
$k = 2$ groups, we find that the detectability transition disappears for any
$\alpha > 0$, in agreement with previous work. For larger $k$ where a hard but
detectable regime exists, we find that the easy/hard transition (the point at
which efficient algorithms can do better than chance) becomes a line of
transitions where the accuracy jumps discontinuously at a critical value of
$\alpha$. This line ends in a critical point with a second-order transition,
beyond which the accuracy is a continuous function of $\alpha$. We demonstrate
qualitatively similar transitions in two real-world networks.
