Detecting Topological Changes in Dynamic Community Networks
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. This
model is formed by adding new vertices, and randomly attaching them to the existing nodes. 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 to the theoretical analysis of the statistical test, we conduct several experiments on
synthetic and real dynamic networks, and we demonstrate that our test can detect changes in graph
topology.
This work is in collaboration with Peter Wills.