  We introduce the Markov Stochastic Block Model (MSBM): a growth model for
community based networks where node attributes are assigned through a Markovian
dynamic. We rely on HMMs' literature to design prediction methods that are
robust to local clustering errors. We focus specifically on the link prediction
and collaborative filtering problems and we introduce a new model selection
procedure to infer the number of hidden clusters in the network. Our approaches
for reliable prediction in MSBMs are not algorithm-dependent in the sense that
they can be applied using your favourite clustering tool. In this paper, we use
a recent SDP method to infer the hidden communities and we provide theoretical
guarantees. In particular, we identify the relevant signal-to-noise ratio (SNR)
in our framework and we prove that the misclassification error decays
exponentially fast with respect to this SNR.
