# Recurrent segmentation meets block models in temporal networks

arXiv: https://arxiv.org/abs/2205.09862 · HTML: https://mlsanity.com/paper/2205.09862/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 19 May 2022.

## Builds on (most cited first, 8 of 8)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [Statistical clustering of temporal networks through a dynamic stochastic block model](https://mlsanity.com/paper/1506.07464/) (2015)
- [Dynamic stochastic blockmodels for time-evolving social networks](https://mlsanity.com/paper/1403.0921/) (2014)
- [A semiparametric extension of the stochastic block model for longitudinal networks](https://mlsanity.com/paper/1512.07075/) (2015)
- [Mining Periodic Patterns with a MDL Criterion](https://mlsanity.com/paper/1807.01706/) (2018)
- [Finding events in temporal networks: Segmentation meets densest-subgraph discovery](https://mlsanity.com/paper/1808.09317/) (2018)
- [Strongly polynomial efficient approximation scheme for segmentation](https://mlsanity.com/paper/1805.11170/) (2018)

## Abstract (arXiv)

A popular approach to model interactions is to represent them as a network with nodes being the agents and the interactions being the edges. Interactions are often timestamped, which leads to having timestamped edges. Many real-world temporal networks have a recurrent or possibly cyclic behaviour. For example, social network activity may be heightened during certain hours of day. In this paper, our main interest is to model recurrent activity in such temporal networks. As a starting point we use stochastic block model, a popular choice for modelling static networks, where nodes are split into R groups. We extend this model to temporal networks by modelling the edges with a Poisson process. We make the parameters of the process dependent on time by segmenting the time line into K segments. To enforce the recurring activity we require that only H < K different set of parameters can be used, that is, several, not necessarily consecutive, segments must share their parameters. We prove that the searching for optimal blocks and segmentation is an NP-hard problem. Consequently, we split the problem into 3 subproblems where we optimize blocks, model parameters, and segmentation in turn while keeping the remaining structures fixed. We propose an iterative algorithm that requires O(KHm + Rn + R2H) time per iteration, where n and m are the number of nodes and edges in the network. We demonstrate experimentally that the number of required iterations is typically low, the algorithm is able to discover the ground truth from synthetic datasets, and show that certain real-world networks exhibit recurrent behaviour as the likelihood does not deteriorate when H is lowered.