Recurrent segmentation meets block models in temporal networks
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 +
R^2H)$ 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.