Structures of Complex Networks and of their Dynamics
Christophe Crespelle - Habilitation à Diriger des Recherhes (HDR)

I defended my habilitation thesis (HDR), entitled "Structures of Complex Networks and of their Dynamics" on September 26th 2017 in Lyon. HDR is the French diploma giving right to advise PhD students and to apply for full professorship. The manuscript is a synthetic document describing my research activity after my PhD thesis, in 2007.


It contains four chapters, an introduction and a conclusion which discusses two research directions in which I particularly believe for the domain of complex networks.

The first chapter deals with the measurement of the degree distribution of the Internet topology. Our approach is based on a new principle called property oriented measurement, which provides more faithful information by focusing only on one target property, without collecting a map of the network. Two methods are presented, one for measuring the degree distribution of the logical topology and one for measuring the degree distribution of the physical topology.

Chapter 2 presents three works on the dynamics of complex networks. The first one is a case study on the dynamic network of contacts within a hospital and the other two are methodological developments dedicated to dynamic networks in general. One is about characterising the structure of changes of the topology of a dynamic network, the other one addresses the problem of finding appropriate time scales in order to aggregate a dynamic network into a series of graphs.

Chapter 3 deals with complex network modelling. The aim is to design random generation processes that output synthetic networks having properties as close as possible from those observed for real-world networks. We describe two different approaches toward this goal. One is based on the entanglement structure of maximal cliques, while the other one is based on the approximation of complex networks by strongly structured graphs.

Finally, the last chapter considers the problem of designing very compact encodings of graphs that do not penalise the queries made during algorithmic treatments, such as listing the neighbours of one given vertex. We investigate the efficiency of two related encodings, named contiguity and linearity, which use linear orderings of the vertices of the graph.

Main page