Title: A Geometric Approach for Real-time Monitoring of Dynamic Large Scale Graphs: AS-level graphs illustrated,
Abstract: The monitoring of large dynamic networks is a major chal- lenge for a wide
range of application. The complexity stems from properties of the underlying
graphs, in which slight local changes can lead to sizable variations of global
prop- erties, e.g., under certain conditions, a single link cut that may be
overlooked during monitoring can result in splitting the graph into two
disconnected components. Moreover, it is often difficult to determine whether a
change will propagate globally or remain local. Traditional graph theory
measure such as the centrality or the assortativity of the graph are not
satisfying to characterize global properties of the graph. In this paper, we
tackle the problem of real-time monitoring of dynamic large scale graphs by
developing a geometric approach that leverages notions of geometric curvature
and recent development in graph embeddings using Ollivier-Ricci curvature [47].
We illustrate the use of our method by consid- ering the practical case of
monitoring dynamic variations of global Internet using topology changes
information provided by combining several BGP feeds. In particular, we use our
method to detect major events and changes via the geometry of the embedding of
the graph.