Dynamics of Graph Topologies – DynGraph

This project's goal is to define relevant methods and tools for studying graphs' dynamics. We base our work on specific real cases of dynamic graphs, such as the internet infrastructure, links between blogs, or networks of proximity between individuals. Indeed, applying the notions we introduce to specific cases allows to test their relevance. Conversely, studying specific cases naturally raises new questions, which can then be formalised into generic notions. Our objective is therefore to design generic methods, i.e. methods which can be used for the study of any graph's dynamics. These methods are developed along four directions: description and handling of dynamic graphs; anomalous event detection; dynamics of the graphs' community structure, and design of dynamic models sharing the properties observed in practice. Finally, our goal is also to obtain results on the dynamics of specific cases of prime interest.

We have obtained important results along four directions: new notions for the characterisation of a graph's dynamics; new methods for anomaly detection; new methods for cutting up a graph into communities, i.e. groups of densely linked nodes, and to track these communities through time; and new models allowing simulations. Finally, we understand better the dynamics of some crucial societal objects. The project also contributed to the setting up of two new academic/industrial partnerships.

Several promising outcome arise from this project. First, we have achieved a better understanding of the studied objects, which led the the introduction of the notion of link flow, an extremely promising concept. We have submitted a proposal to the last ANR call. Even though it was not selected during the first phase, we are confident that, once it has matured, this approach will yield outstanding results. Second, some of the notions we have introduced are relevant for distributed computing, in particular the community core notion. Computing these notions in an efficient way on computing clusters will allow us to deal with graphs which are one order of magnitude larger than what we can currently address. This is one important prospect and it is a feature of the Request project, funded by the future investments program, which we are a partner of and which has just started. Finally, the project led to the introduction of extremely promising notions for the study of dynamic communities, which could not be finalised during the project's duration. This question is one of the main axis of the ANR CONTINT project CODDDE, led by Jean-Loup Guillaume (member of the current project), starting in 2014.

The project results have led on the one hand to software implementations of the new methods designed, and on the other hand to publications in the traditional academic diffusion media: international journals (4 publications including Complex Systems) and international conferences (12 publications including MobiCom). We have taken care to target the different relevant scientfic communities in order to maximise the project's impact.

Dynamic graphs appear in many contexts: computer networks in which nodes and links may experience failures, social networks in which links between individuals appear and disappear with time, web graphs with pages and links being created or deleted, etc. Up to very recently, these objects have mainly been studied as static graphs, i.e. snapshots at a given time. A large number of results from the last 10 years have introduced a set of tools for the analysis and description of static graphs. However, taking into account the dynamics of these graphs is fundamental for their understanding, and the corresponding applications. There is therefore a high need for the development of tools and methods for the analysis of the dynamics of graphs, both at the fundamental level and for the applications, in computer science, biology, sociology, economy, etc.

This project has two distinct goals: on the one hand, we wish to design the necessary tools for the study of dynamic graphs by introducing relevant notions to describe and understand their structure.
To achieve this, we will begin by studying the time-evolution of properties describing static graphs, which will allow some firt interesting results. This is however not satisfying, because studying the evolution of static properties does not allow to take fully into account the graph's dynamics. For instance, this approach does not allow to study basic notions such as node or link appearance or disappearance rate, or the duration for which they are present in the graph. We will therefore also introduce notions that intrinsically take the dynamics of the studied graphs into account.
We will also study questions of particular importance in this context: event detection and dynamic community detection. Finally, we also wish to address the question of dynamic graph modelling, i.e. the generation of artificial dynamic graphs sharing the same properties as real dynamic graphs.

The second goal of this project is to use dynamic graphs coming from real applications for the validation of our works. This will ensure the relevance of our fundamental works, and at the same time it will produce results on these specific cases, with a strong impact in the corresponding domains.
We already have acess to large datasets coming from three different dynamic graphs: the communications between computers on the Internet observed at the IP level; measurements of the evolution of the local Internet topology around a given computer; and exchanges on peer-to-peer systems for file sharing. We may include additional cases in the course of the project, if relevant.

The team involved in this project is composed of the permanent members of the Complex Networks team in LIP6. The principal investigator of the project and the other team members are certain that the study of the dynamics of graphs is a fundamental emerging theme in the general field of complex network study, and they wish to spend an important part of their time on the development on this theme.