Simplifying Complex Networks

Networks, or graphs, provide a remarkable framework to represent a wide class of complex systems. Examples of such systems include protein interaction maps, neuronal connections in the brain, the Internet, electrical grids, or social interactions underlying the spreading of an epidemic. For most of these systems, the complexity arises because of their large size and intricate internal organization. A promising approach to simplify such systems is therefore to reduce the complexity of the corresponding networks. Throughout this Thesis, we investigated several methods to reduce the complexity of networks. In particular, we introduced a novel strategy, called Spectral Coarse Graining by analogy with the coarse graining in Statistical Physics. We describe how this new method allows us to unravel the backbone structure of a network and results in a significantly smaller, but truly representative version of the initial network. To illustrate the power of the method, we applied it to several real networks, with particular emphasis on networks describing the molecular dynamics of small proteins.