Statistical analysis of graphs with abrupt changes

Graphs are powerful mathematical tools to express relationships between anykind of items in very diverse disciplines. In this work, we worked on stochastic blockmodels and multiple change-point detection problem for graph time series, where numberof change points is unknown. Stochastic block models is a branch of clusteringalgorithms for relational data. We studied bayesian approaches as expectationmaximization(EM), variational expectation-maximization, Monte Carlo methods asGibbs sampling for analysis of stochastic block models. For time series analysis, wehave studied Hidden Markov Models, applied well-known forward-backward algorithmto multiple change point analysis on network series. We have proposed an approximateinference algorithm that combines Monte Carlo approaches and hidden Markovmodels (forward ltering-backward sampling). In our model, we calculate the forwardmessages completely, sample a change point from those, calculate the backward messagefor the sampled changed point, update with the forward message and sample achange point for the previous time step. It continues in this way to the rst time step,named backward-sampling. By this way, we have simplied the calculation cost. Inaddition, it is a motivation to use Monte Carlo methodologies in time series analysiswhere we can not take integrals easily in order to do exact inference. On experimentswe have done on syntheic data, we have seen that our proposed approximate inferencealgorithm gives results in accordance with exact inference methodology, in detectingmultiple change points and category assignments.