Block-Structure Based Time-Series Models For Graph Sequences
This work addresses the problem of extending block models to graph sequences for researchers in network analysis, though it appears incremental as it builds on existing single-graph methods.
The authors tackled the challenge of modeling sequences of graphs by proposing two models that capture link and community persistence across time, with statistically and computationally efficient inference algorithms that leverage single-graph community detection methods, and validated them on synthetic and real data.
Although the computational and statistical trade-off for modeling single graphs, for instance, using block models is relatively well understood, extending such results to sequences of graphs has proven to be difficult. In this work, we take a step in this direction by proposing two models for graph sequences that capture: (a) link persistence between nodes across time, and (b) community persistence of each node across time. In the first model, we assume that the latent community of each node does not change over time, and in the second model we relax this assumption suitably. For both of these proposed models, we provide statistically and computationally efficient inference algorithms, whose unique feature is that they leverage community detection methods that work on single graphs. We also provide experimental results validating the suitability of our models and methods on synthetic and real instances.