Title: Detecting Topological Changes in Dynamic Community Networks,
Abstract: The study of time-varying (dynamic) networks (graphs) is of fundamental
importance for computer network analytics. Several methods have been proposed
to detect the effect of significant structural changes in a time series of
graphs. The main contribution of this work is a detailed analysis of a dynamic
community graph model. This model is formed by adding new vertices, and
randomly attaching them to the existing nodes. It is a dynamic extension of the
well-known stochastic blockmodel. The goal of the work is to detect the time at
which the graph dynamics switches from a normal evolution -- where balanced
communities grow at the same rate -- to an abnormal behavior -- where
communities start merging. In order to circumvent the problem of decomposing
each graph into communities, we use a metric to quantify changes in the graph
topology as a function of time. The detection of anomalies becomes one of
testing the hypothesis that the graph is undergoing a significant structural
change. In addition the the theoretical analysis of the test statistic, we
perform Monte Carlo simulations of our dynamic graph model to demonstrate that
our test can detect changes in graph topology.