Loading…
Thumbnail Image

Identification of nodes and Networks

robustness, immunization, and explosive synchronization

Liu, Yang

Complex systems in a broad range of scientific domains have been shown to be well-characterized by networks in an increasing number of studies. Problems such as cascading failures, spreading dynamics and the extraction of leading factors from raw data through the construction of networks can all be studied within the paradigm of network science. Such problems concerning networks are usually directly or indirectly associated with the identification of edges, nodes, and sometimes the entire network. Hence, it is mainly from the two levels of network structure: nodes and networks, that we aim to study the problem of network robustness (or immunization in the context of epidemics). On the local level of nodes, the goal of this thesis is to propose advanced approaches to fragment an existing network. Through such approaches we can achieve network fragmentation with an attack on fewer nodes than exiting methods, or alternatively, we can achieve a safer network which is more capable of containing epidemics while using the same resources (i.e., same amount of nodes). These approaches could also be applied to diverse problems such as to the distribution of a vaccine, to the decision over which group of individuals should be quarantined first, to the containment of misinformation in social networks, or to access the resilience of a network-based system under an intentional attack. To achieve that, this thesis integrates rules from explosive percolation, strategies from graph partition, and ideas from evolutionary computing. As a result, the developed approaches are much more effective at acquiring the key group of nodes responsible for the fragmentation when compared to the state-of-the-art methods. On the level of entire networks, we attempt to ascertain whether the order parameter -- here a measure of network robustness -- could be used to capture the network structure, and further study potential ways that could be used to enhance or weaken the robustness of a given network regarding such a parameter. In particular, we show that for the known phenomenon of explosive synchronization, the order parameter indeed plays an important role in capturing the network structure. In regard to the network robustness, however, only indirect strategies could be found. Hence, this thesis further discusses the predictability and controllability of the network robustness by the aid of machine learning methods on the dataset from the explosive synchronization. The main contributions of this thesis can therefore be summarized as follows: the methodology consisting of i) bounded and unbounded strategies and ii) evolutionary framework for the identification of influential nodes; and potential application include iii) effects of network robustness on explosive synchronization, iv) ways to enhance the robustness of a network, v) influences of acquaintances on the containment of epidemics, and vi) prediction of the hysteresis in explosive synchronization.
In zahlreichen Studien hat es sich erwiesen, dass komplexe Systeme durch Netzwerke charakterisiert werden können. Diverse Probleme wie Kaskadierungsfehler, Verbreitungsdynamik und Datenverarbeitung können durch Methoden der Netzwerkwissenschaft erforscht bzw. verbessert werden. Der wesentliche Aspekt von solchen netzwerkwissenschaftlichen Studien ist die Identifikation der Kanten, der Knoten oder des gesamten Netzwerks. Deshalb erforschen wir das Problem in dieser Arbeit von zwei Aspekten aus -- der eine ist die Identifikation der Knoten, der andere die Identifikation des Netzwerks. Das Ziel dieser Arbeit in Bezug auf den ersten Aspekt ist der Vorschlag fortgeschrittener Ansätze zur Fragmentierung eines bestehenden Netzwerks. In Vergleich zu anderen Methoden, geschieht dies mit weniger zu entfernenden Knoten. Als Resultat können wir ein sichereres Netzwerk erreichen, in dem z.B. Epidemien besser eingedämmt werden können, während dieselben Ressourcen (die gleiche Anzahl von Knoten) verwendet werden. Davon profitieren Anwendungen wie die Verteilung von Impfstoffen, die Entscheidung, welche Personengruppe unter Quarantäne gestellt werden soll, die Eindämmung von Fehlinformationen in sozialen Netzwerken oder das Erkennen der Ausfallsicherheit eines netzwerkbasierten Systems unter einem gezielten Angriff. Um dies zu erreichen, integriert diese Arbeit Regeln aus der explosiven Perkolation mit Strategien aus der Graphen-Partitionierung und Ideen aus evolutionären Algorithmen. Für über 20 empirische Netzwerke sind unsere entwickelten Ansätze im Vergleich zum Stand der Technik wesentlich effektiver bei der Erfassung der Schlüsselgruppe von Knoten, die für die Fragmentierung verantwortlich sind. In Bezug auf die Netzwerkidentifikation stellen wir uns die Frage, ob der sogenannte Ordnungsparameter -- hier ein Maß der Robustheit eines Netzwerks -- eine Netzwerkstruktur charakterisieren kann und untersuchen mögliche Wege die Robustheit eines bestimmten Netzwerks zu verbessern oder zu schwächen. Insbesondere haben wir beim Phänomen der explosiven Synchronisation festgestellt, dass der Ordnungsparameter in der Tat eine zentrale Rolle beim Charakterisieren der Netzwerkstruktur spielt. Für den Einfluss auf die Robustheit eines Netzwerks konnten jedoch nur indirekte Strategien gefunden werden. In dieser Arbeit wird daher die Vorhersagbarkeit und Steuerbarkeit der Netzwerkrobustheit mithilfe maschineller Lernwerkzeuge für den Datensatz aus der explosiven Synchronisation weiter erörtert. Die Hauptbeiträge und neue Methodik dieser Arbeit lassen sich daher wie folgt zusammenfassen: die Methodik bestehend aus i) begrenzten und unbegrenzten Strategien und ii) Ausarbeitung eines evolutionären Frameworks für die Untersuchung einflussreicher Knoten; und mögliche Anwendungen umfassen iii) Identifikation der Auswirkungen der Netzwerkrobustheit auf die explosive Synchronisation, iv) Entwicklung von Möglichkeiten zur Verbesserung der Robustheit eines Netzwerks, v) Einflüsse von Bekannten auf die Eindämmung von Epidemien und vi) Vorhersage der Hysterese bei der explosiven Synchronisation.