Methods for analyzing complex networks using random walker approaches

Abstract

Real-world systems are often modeled as networks. Many algorithms for analyzing such complex networks are oriented towards finding modules that are densely inter-connected substructures having sparse connections to the rest of the network, and finding hub nodes that are key connectors of modules. In many cases these modules and hubs correspond to relevant structures in the original system. For example in biological systems, modules often correspond to functional units and hubs to essential parts of this system. In this thesis we developed a new mathematical framework that can be effectively applied for analyzing complex networks. This framework is based on defining a new type of random walk processes on networks and using spectral methods for finding modules and hubs. When considering random walk processes on networks, modules represent metastable sets of this process. There are two crucial differences in the approach presented in this thesis compared to standard random-walk- based methods for module finding. Firstly, we have defined a new time- continuous random walk process characterized by waiting times in each node which results in increased metastability of the process in densely connected areas of the network-modules. In this way we have overcome the problem of most standard random walk processes for which also nonmodular structures (for example long chains) represent metastable sets. The second difference results from the fact that most of the state-of-the-art approaches for module finding focus on finding a full partition of a network. The method introduced in this thesis finds a fuzzy decomposition of a network into modules, where nodes can be assigned to more than one module with a certain probability. In order to find such modules we used Markov State Models (MSM) as low-dimensional models for metastable Markov processes. We generalized the standard MSM approach that is based on full partitioning of the state space and developed a fuzzy MSM, where nodes that are assigned to some module with probability almost 1 correspond to dominant metastable regions. For determining the optimal modules, we used the approximation quality measure of the resulting MSM, based on the error between the original and reproduced dominant eigenvalues. This thesis provides a new methodological approach for finding network hubs. We defined hubs as nodes that are important for the communication between network modules, that is determined by the associated random walk process. For measuring the amount of communication flow between modules in the network, we presented a method that is based on the framework of Transition Path Theory (TPT). Finally, we proposed a generalization of our methods for analyzing undirected networks to the case of directed networks. The main difficulty is that random walk processes on directed networks are non-reversible. To this end, we adapted our methods to analyzing non-reversible processes by introducing two transfer operators whose spectral properties provide information that is needed for finding metastable sets of this process. In this way, we have provided a spectral approach for finding metastable sets of non-reversible processes. However, it is not yet clear how metastable sets are related to modules in directed networks. This will be the topic of future research.

Technische oder natürliche Systeme werden oft als Netzwerke modelliert. Viele der vorhandenen Methoden zur Analyse solcher komplexer Netzwerke wurden dazu entwickelt, sogenannte Module und Hubs zu finden. Ein Modul ist eine Menge von Knoten, zwischen denen die Vernetzung untereinander stärker ist als zum Rest des Netzwerkes. Wichtige Knoten, die zur Verbindung von Modulen essentiell sind, werden als Hubs bezeichnet. Module und Hubs in einem Netzwerk entsprechen oft wichtigen Strukturen in dem durch dieses Netzwerk modellierten System. In biologischen Systemen entsprechen Module beispielsweise organisatorischen Einheiten und Hubs wichtigen Botenstoffen. In dieser Arbeit haben wir ein neues mathematisches Framework zur Analyse von komplexen Netzwerken entwickelt. Es basiert auf der spektralen Analyse neuartiger Random-Walk Prozesse auf Netzwerken. Bei der Netzwerkanalyse mittels Random- Walk Prozessen entsprechen Module im Allgemeinen den metastabilen Mengen des Prozesses. Im Vergleich zu Standardmethoden zur Modulidentifikation unterscheidet sich unser neuer Ansatz durch zwei wichtige Merkmale: Erstens benutzen wir einen neuen zeitkontinuierlichen Random-Walk Prozess, der durch Wartezeiten in jedem Knoten charakterisiert ist. Dies führt zu einer erhöhten Metastabilität des Prozesses in den dicht vernetzten Bereichen der Netzwerkmodule und einer reduzierten Metastabilität in nicht-modularen Strukturen wie z.B. langen “Ketten”, die von den Standardmethoden wegen der hohen Metastabilität als Module erkannt werden. Der zweite grundlegende Unterschied unseres Ansatzes besteht darin, ein Netzwerk nicht vollständig in Module zu unterteilen und jeden Knoten zu genau einem Modul zuzuordnen (sog. full-partitioning), sondern einen Knoten einem oder mehreren Modulen mit einer bestimmten Wahrscheinlichkeit zuzuordnen (fuzzy-decomposition). Zur Identifikation dieser Module benutzen wir Markov-State-Models (MSM) als niedrig-dimensionale Repräsentation von metastabilen Markov Prozessen. Da das Standard-MSM Framework auf einer vollständigen Partition des Zustandsraumes basiert, haben wir dieses in der vorliegenden Arbeit verallgemeinert und eine fuzzy-MSM Variante entwickelt. In dieser Variante entsprechen Knoten, die einem Modul mit einer Wahrscheinlichkeit nahe Eins zugeordnet sind, den dominanten metastabilen Bereichen. Um die optimalen Module zu bestimmen, benutzen wir die Approximationsgüte des resultierenden MSM, welche auf dem Fehler zwischen den originalen und reproduzierten dominanten Eigenwerten basiert. Neben dem Finden von Modulen wird in dieser Dissertation auch eine neue Methode zur Identifikation von sog. Hubs vorgestellt. Wir definieren Hubs als Knoten, die für die Kommunikation zwischen Modulen wichtig sind. Um den Kommunikationsfluss zwischen Modulen zu bestimmen, beschreiben wir eine neue Methode, die auf dem Transition Path Theory Framework basiert. Im letzten Teil der Arbeit verallgemeinern wir die vorgestellten Konzepte, die bisher nur für ungerichtete Netzwerke entwickelt wurden, auf die Klassen der gerichteten Netzwerke. Das Hauptproblem hierbei ist, dass Random-Walk Prozesse auf gerichteten Netzwerken nicht reversibel sind. Um nicht-reversible Prozesse analysieren zu können, führen wir zwei Transferoperatoren ein, deren spektrale Eigenschaften die benötigten Informationen zur Identifikation von metastabilen Mengen liefern. Dadurch haben wir einen neuen, spektralen Ansatz zur Identifikation von metastabilen Mengen in nicht-reversiblen Prozessen entwickelt. Die Verbindung von diesen metastabilen Mengen zu Modulen in gerichteten Netzwerken ist noch nicht abschließend geklärt und wird Gegenstand weiterer Forschung sein.