Faculté des sciences de base SB, Section de physique, Institut de théories des phénomènes physiques ITP

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

Petermann, Thomas ; De Los Rios, Paolo (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3270.

Ajouter à la liste personnelle
    Summary
    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.
    Zusammenfassung
    Komplexe Netzwerke mit den Augen des Statistischen Physikers betrachtet: Von der Architektur des Internets und des Gehirns zur Ausbreitung einer Epidemie Die statistische Physik erwies sich als idealer Rahmen zur Beschreibung grosser Netzwerke, wie sie in verschiedensten Disziplinen - so etwa in der Soziologie, der Kommunikationstechnologie oder den Neurowissenschaften - auftreten. Obwohl diese Systeme von der Natur her sehr verschiedenartig sind, besitzen sie eine ähnliche topologische Komplexität. Diese ist typischerweise charakterisiert durch die Präsenz von 'small-wor1d'-artigen oder skalenfreien Vernetzungsmustern. Während small-world für eine hohe globale und lokale Vernetzung steht, bedeutet Skalenfreiheit, dass die Verteilung der Grade - d.h. die Verteilung der Anzahl Verbindungen pro Knoten - einem abfallenden Potenzgesetz folgt. Diese Allgegenwärtigkeit auf topologischer Ebene wirft verschiedene Fragen auf. Zuallererst sollte sichergestellt werden, ob die durch den Messprozess erhaltene der tatsächlichen Topologie entspricht. Weiter ist es äusserst wichtig, die Rolle der Topologie in sich auf Netzwerken abspielenden dynamischen Prozessen zu verstehen. Zudem wollen wir begreifen, wie spezifische Faktoren die Topologie eines Netzwerkes bestimmen. Indem wir den oben erwähnten Messprozess als baumartige Erkundung implementierten, zeigten wir für skalenfreie Netzwerkmodelle, dass der Exponent der Gradverteilung des erkundeten Netzwerkes kleiner ist als derjenige des ursprünglichen Netzwerkes. Dies weist darauf hin, dass die Knoten mit kleinem Grad unterrepräsentiert sind. Da eine derartige Erkundung an sich der Ermittlung des Atlas des Internets gleichkommt, sollten die entsprechenden Exponenten mit Vorsicht interpretiert werden. Die Topologie spielt auch eine entscheidende Rolle in verschiedenen dynamischen Prozessen, die sich in einem Netzwerk abspielen können. Ein besonders relevantes Beispiel hierfür ist die Ausbreitung einer Epidemie. In einem derartigen Kontext erstaunt es wenig, dass sich ein Virus in einem Netzwerk mit kurzen globalen Distanzen leicht ausbreitet. Diese topologische Eigenschaft bedingt auch, dass dynamische Korrelationen schwach sind und der Prozess daher im Rahmen der mittleren Feldapproximation beschrieben werden kann. Diese Beschreibung, welche wir auf verschiedenen Ebenen herleiteten, liefert eine Interpretation der Rolle des Grades in der Ausbreitungsdynamik. Auf welche Art die lokale Vernetzung das dynamische Verhalten beinflusst, bleibt jedoch schwer fassbar. Mittels einer systematischen Untersuchung der zeitlichen und räumlichen Korrelationen, welche die Dynamik der Epidemie begleiten, entwickelten wir zwei Methoden, die quantitativ beschreiben wie lokale Vernetzungsstrukturen das Ausbreitungsverhalten bestimmen. Im einfachsten Modell für ein small-world Netzwerk wird die hohe globale Vernetzung durch hinzufügen langer Verbindungen auf ein regelmässiges Gitter erreicht. Falls nun aber die Länge einer Verbindung mit Kosten verknüpft ist, stellt sich die Frage, ob die small-world Eigenschaft auch dann resultiert, wenn zugleich die Vernetzungskosten minimiert werden sollen. Wir wiesen nach, dass small-world Netzwerke auf eine sehr sparsame Art erzeugt werden können, indem die Verbindungslängen gemäss einem abfallenden Potenzgesetz verteilt werden. Zudem fanden wir, dass eine Erhöhung des Exponenten der Längenverteilung die Netzwerke hinsichtlich zufälliger Ausfälle von Verbindungen weniger verwundbar macht und die Verteilung von Datenflüssen durch die Verbindungen optimiert. Insgesamt führte diese Studie zu einer Reihe von Erkenntnissen betreffend der Topologie von komplexen Netzwerken. So untersuchten wir, wie man die Topologie erhält, welche Rolle sie in dynamischen Prozessen spielt und durch welche Faktoren sie bestimmt wird.
    Résumé
    Une approche des réseaux complexes inspirée par la physique statistique: de l'architecture de l'Internet et du cerveau à la diffusion d'une épidémie La physique statistique s'est rélévée être un cadre idéal afin de décrire de grands réseaux qui apparaissent dans une multitude de disciplines telles que la sociologie, les technologies de communication et les neurosciences. Malgré la diversité de ces systèmes, ils sont presque identiques si l'on regarde à un niveau statistique la manière dont les noeuds sont connectés les uns avec les autres. Cette similitude topologique se manifeste par la propriété 'petit monde' et par l'invariance d'échelle. La première de ces propriétés signifie une haute interconnexion au niveau global et local, tandis que la seconde se réfère au nombre de connexions par noeud, c'est-à-dire au degré. L'invariance d'échelle implique que les degrés sont distribués selon une loi de puissance décroissante. Cette ubiquité topologique soulève plusieurs questions. Tout d'abord, il s'agit de vérifier si la topologie obtenue par un processus de mesure correspond à celle du réseau en question. Il est également important de comprendre l'influence de la topologie sur des processus dynamiques se déroulant sur un réseau. En outre, nous souhaitons connaître comment certains facteurs déterminent la topologie d'un réseau. En implémentant le processus de mesure mentionné ci-dessus comme une exploration arborescente, nous avons démontré pour des modèles de réseaux invariants d'échelle que l'exposant de la distribution des degrés du réseau exploré est plus petit que celui du réseau de départ. Cela veut dire que les noeuds de degré bas sont sous-représentés. Comme une telle exploration imite la découverte de l'atlas de l'Internet, les exposants correspondants doivent être interprétés avec prudence. La topologie joue également un rôle crucial dans plusieurs processus dynamiques pour lesquels le réseau représente la "trame". Un exemple d'une importance primordiale est la diffusion d'une épidémie. Dans un tel contexte, il est peu surprenant qu'un virus se propage plus facilement sur un réseau caractérisé par des distances globales courtes. Cette propriété topologique a également pour effet que les corrélations dynamiques sont faibles ce qui permet de décrire le processus dans le cadre de l'approximation du champ moyen. Cette description que nous avons dérivée sur plusieurs niveaux fournit une interprétation du rôle du degré dans la dynamique de diffusion. Pourtant, l'influence de l'interconnexion locale sur le comportement de diffusion reste largement incomprise. Par une investigation systématique des corrélations temporelles et spatiales qui accompagnent la dynamique de l'épidémie, nous avons développé deux méthodes qui décrivent d'une façon quantitative comment des structures d'interconnexion locales déterminent le comportement de diffusion. Dans le modèle le plus simple d'un réseau petit monde, la haute interconnexion globale est reproduite en ajoutant de longs liens sur un réseau régulier. Dans le cas où un coût est associé aux longueurs des connexions, il est intéressant d'examiner la condition pour qu'une topologie petit monde apparaisse si l'on désire minimiser le coût de câblage. Nous avons démontré que des réseaux petit monde peuvent être créés d'une facon très économique si les longueurs des connexions sont distribuées selon une loi de puissance décroissante. Comme autre conséquence intéressante, nous avons trouvé qu'une augmentation de l'exposant de la distribution des longueurs optimise la répartition des flux de données sur les connexions. En même temps, une telle augmentation rend les réseaux moins vulnérables par rapport à des défaillances aléatoires au niveau des connexions. Dans l'ensemble, cette étude a mené à une série de résultats concernant la topologie des réseaux complexes. Plus précisément, nous avons examiné comment la topologie est obtenue, quel rôle elle joue dans des processus dynamiques et quels facteurs la déterminent.