Inference in the Stochastic Block Model with a Markovian assignment of the communities

Large random graphs have been very popular in the last decade since they are powerful tools to model complex phenomena like interactions on social networks or the spread of a disease. In practical cases, detecting communities of well connected nodes in a graph is a major issue, motivating the study of the Stochastic Block Model (SBM). In this model, each node belongs to a particular community and edges are sampled independently according to a probability depending of the communities of the nodes. Aiming at progressively bridging the gap between models and reality, time evolving random graphs have been recently introduced. In [20], a Stochastic Block Temporal Model is considered where the temporal evolution is modeled through a discrete hidden Markov chain on the nodes membership and where the connection probabilities also evolve through time.