Â鶹ӰԺ

The study of time-varying networks is of fundamental importance for computer

network analytics. Dynamic networks provide models for social networks, and are

used to decode functional connectivity in neuroscience and in biology.

Several methods have been proposed to detect the effect of significant

structural changes (e.g., changes in topology, connectivity, or relative size of

the communities in a community graph) in a time series of graphs.

The main contribution of this work is a detailed analysis of the dynamic

stochastic blockmodel, a model for a random growing graph with community

structure. The goal of the work is to detect the time at which the graph

dynamics switches from a normal evolution -- where two balanced communities grow

at the same rate -- to an abnormal behavior -- where the two communities are

merging. Because the evolution of the graph is stochastic, one expects random

fluctuation of the graph geometry. The challenge is to detect an anomalous event

under normal random variation.

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 François Meyer.