Reliable Time Prediction in the Markov Stochastic Block Model
This work addresses network analysis challenges for researchers and practitioners in fields like social networks or recommendation systems, but it is incremental as it builds on existing stochastic block models and HMM literature.
The paper tackles the problem of link prediction and collaborative filtering in community-based networks by introducing the Markov Stochastic Block Model (MSBM), which incorporates Markovian dynamics for node attributes, and proposes robust prediction methods with theoretical guarantees, including an exponential decay of misclassification error with respect to signal-to-noise ratio.
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.