Detecting change points in the large-scale structure of evolving networks
This work addresses the challenge of identifying fundamental changes in large-scale patterns of interactions in dynamic networks, such as social networks, with potential applications in monitoring and analysis, though it appears incremental as it builds on existing probabilistic and Bayesian approaches.
The authors tackled the problem of detecting change points in evolving networks by formalizing it within an online probabilistic learning framework and introducing a method that combines a generalized hierarchical random graph model with a Bayesian hypothesis test. They showed that this method is more accurate than previous alternatives on synthetic data and identified change points aligning with known external shocks in real social networks.
Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external "shocks" to these networks.