Dynamic sparse graphs with overlapping communities

Dynamic community detection in networks addresses the challenge of tracking how groups of interconnected nodes evolve, merge, and dissolve within time-evolving networks. Here, we propose a novel statistical framework for sparse networks with power-law degree distribution and dynamic overlapping community structure. Using a Bayesian Nonparametric framework, we build on the idea to represent the graph as an exchangeable point process on the plane. We base the model construction on vectors of completely random measures and a latent Markov process for the time-evolving node affiliations. This construction provides a flexible and interpretable approach to model dynamic communities, naturally generalizing existing overlapping block models to the sparse and scale-free regimes. We provide the asymptotic properties of the model concerning sparsity and power-law behavior and propose inference through an approximate procedure which we validate empirically. We show how the model can uncover interpretable community trajectories in a real-world network.