On optimal tracking of structural changes in time-varying networks

Time-varying networks consist of a sequence of heterogeneous networks over time, and it is of great importance to detect the network structural changes. Most existing methods focus on detecting abrupt network mean changes, necessitating the assumption that the underlying network probabilities remain homogeneous between adjacent change points. This assumption can be overly strict in many real-life scenarios due to their versatile network dynamics and constantly changing network probabilities. In this paper, we propose a subspace tracking method to detect network structural changes in time-varying networks, whose network probabilities may undergo continuous changes but their network structures remain stable from one structural change point to the next. With the time-varying networks embedded in a latent embedding subspace, two new detection statistics are proposed to jointly detect the network structural changes, followed by a carefully refined detection procedure. Theoretically, we show that the proposed subspace tracking method is asymptotically consistent in terms of detecting the network structural changes, and also establish the impossibility region in a minimax sense. The advantage of the proposed method is also supported by extensive numerical experiments on both synthetic networks and a series of UK politician social networks.