Infoscience

Thesis

A statistical physics perspective of complex networks: from the architecture of the Internet and the brain to the spreading of an epidemic

A statistical physics perspective of complex networks: from the architecture of the Internet and the brain to the spreading of an epidemic Statistical physics has revealed itself as the ideal framework to describe large networks appearing in a variety of disciplines such as sociology, communication technology or neuroscience. Despite the diversity of these systems, they appear to exhibit a similar topological complexity such as the presence of small-world or scale-free patterns. The former property refers to a high global and local interconnectedness, whereas the latter means that the frequencies of the number of connections per node, i.e. the degrees, are distributed according to a decaying power law. This ubiquity at the topological level raises several questions. First of all, it should be verified whether the observed topology obtained through the measuring process corresponds to the real one. It is also important to understand the influence of topology on dynamic processes running on a network. Furthermore, we wish to explain how specific factors shape network topology. By implementing the measuring process as a treelike exploration, we demonstrated for scale-free network models that the exponent of the degree distribution of the explored network is smaller than the original one. This means that the low-degree nodes are underrepresented. Since such an exploration in principle mimics the discovery of the Internet map, the corresponding exponents should not be taken at face value. As mentioned above, topology plays a crucial role in different dynamic processes taking place on complex networks. An example of paramount importance is the spread of an epidemic. In such a context, it does not come as a surprise that a virus spreads more easily on a network in which global distances are small. This topological property is one of the conditions that allows one to ignore dynamical correlations and to describe the process in the framework of a mean-field approximation. This description, which we derived at different levels, uncovers the role of the degree. However, the influence of the local interconnectedness on the spreading behaviour remains elusive. By systematically exploiting spatial and temporal correlations that govern the spreading dynamics, we further elaborated two methods which quantitatively describe how local substructures influence the spreading behaviour. In the simplest model for a small-world network, a high global interconnectedness originates from the addition of long-range connections to a regular lattice. In a situation where a cost is associated with the lengths of the links, it is interesting to explore whether the emergence of small-world topology conflicts with a minimisation of the wiring costs. We found that, if the lengths of the additional links are distributed according to a decaying power law, small-world networks can be constructed in a very economical way. As further intriguing consequences, an increase of the exponent of the length distribution optimises the distribution of flows of traffic over the links while making the networks less vulnerable with respect to random failures of connections. Overall, this study has led to a series of results related to the topology of complex networks. More precisely, we have investigated how the topology is obtained, what its role in dynamic processes is and what factors shape it.

    Thèse École polytechnique fédérale de Lausanne EPFL, n° 3270 (2005)
    Section de physique
    Faculté des sciences de base
    Institut de théories des phénomènes physiques
    Jury: Guido Caldarelli, Wulfram Gerstner, Marco Tomassini, Minh Quang Tran

    Public defense: 2005-7-15

    Reference

    Record created on 2005-05-18, modified on 2016-08-08

Related material

Contacts

EPFL authors