Research themes

Networks play a central role in a wide variety of contexts and situations ranging from computer science to social science, including statistical physics, biology and many others. Most networks studied in practice, often referred as complex networks, share several properties and yield similar questions about their topology and its influence on the behavior of these networks. For instance, the network of Internet routers and physical links between them plays a key role in the design of efficient routing protocols. My research themes are centered on the study of these complex networks with a computer scientist approach, centered on the graph theory and the networking point of view. Among the variety of questions arising while studying complex networks, my personal interests include metrology, analysis, modeling and algorithmic on complex network.

Network metrology is centered on the acquisition of data and their interpretation. Acquiring data is sometimes easy, but more often is a challenging task. For instance the Internet graph is obtained through various measurements procedures (traceroute, BGP tables, etc) which are currently not clearly understood and rely on some unknown behaviors. While the classical approach consists in collecting as much data as possible, the obtained graphs are known to be partial and biased. This incite us to understand how the bias appears and how it can be removed or controlled.

Network analysis consists in the study of complex networks in order to obtain their main characteristics and extract some complex information about them. A large number of studies have been conduced is the past few years, which have introduced or measured many properties of complex networks. Some of these properties are simple statistical ones, such as the density, the diameter, the degree distribution, the clustering coefficient or some correlations between these parameters, etc. However, this approach is nowadays mostly static, and networks are considered as undirected and unlabelled, while most real complex networks are not only evolving during time, but nodes are of different kinds, links may be associated to a flow in the case of Internet for instance, etc. Both dynamic and valuated approach should bring a better understanding of many phenomena.

Network and phenomena modeling has carried out an intense activity since 1998, beginning with the leading approach of a few scientist. Two levels of modeling can be defined when considering complex networks. The first one has been widely studied and concern the networks themselves: different models try either to produce networks having some wanted properties or to mimic an evolution process which would eventually produce a graph similar to the observed one. Another level of modeling concerns the phenomena which take place on complex networks. The spreading or halting of viruses on social networks or mechanisms of routing on the Internet are some of them. Understanding these phenomena would make it possible to modify the network in order to prevent them.

Dedicated algorithms: complex networks are generally quite large (from a few thousand to a few billion nodes), which is not usual in graph theory. One cannot use exponential algorithms, and even quadratic ones are generally intractable if we do not assume specific properties. The largest ones, for instance the web graph, cannot even be stored in main memory on a classical workstation. However, all these networks have very specific properties which allow us to use parallel computation, dynamic algorithms or approximation methods. One may also design dedicated algorithms which would be efficient on this kind of networks even if they are not on random or other classes of networks. Pioneer work might be done in this branch of algorithmic.