Networks are commonly used to model complex real-world systems such as the cell or the brain. An important notion in analyzing networks is modularity. Usually, a network is considered modular if all its nodes can be partitioned into dense, connected subsets that are sparsely connected to one another. In this thesis, we extend the definition of modularity to cover networks that do contain dense modules that are sparsely connected to the rest of the network, but some nodes can belong to the region outside of modules, the so-called transition region. Accordingly, in contrast to full partitions, this work deals considers assignments: The association of every node to a module in the modular region or to the transition region. The first task to be tackled in this thesis is the construction of a formal definition of modularity. After surveying some of the prominent existing definitions in the literature, we found that they cannot be directly applied to networks that are not fully- partitionable. We then developed an approach based on time-continuous random walks for analyzing networks. Here we built on a rich literature on the topic of spectral clustering, equating network modules with metastable sets of a random walk. This allows us to define a network as modular if there is a choice of modules that produces a coarse-grained Markov process whose dynamics well-approximate those of the original random walk on the network. We first demonstrate that this score matches our intuition of modularity on synthetic networks, increasing with the density of the modules and in the case where the modular region is large. Perturbation analysis is then used to formally prove the correct behavior of the score on two specifically constructed classes of networks. Motivated both by the need to provide a good assignment as input to the modularity score and by the established usefulness of clustering methods, the second task to be tackled is that of finding good assignments. Continuing with the approach of Markov models, we first describe an algorithm based on a continuous random walk on the network. Next, modifications to several leading full-partition algorithms are described so that they output modules and transition regions rather than full partitions. The performance of all algorithms is then tested on a class of benchmark networks. Finally, we developed a combinatorial model of networks that are not fully partitionable as a union of split graphs, and posed the problem of finding modules and transition regions as a graph editing problem, proving its hardness and providing exact algorithms and heuristics. The discussion of each of the two tasks is completed by an example of a biological application. Identifying good assignments gives us a way to detect protein complexes in protein interaction networks, a well-studied topic. The flexibility of assigning proteins to modules or to the transition region helps identify more complicated structures as complexes. The modularity score is used to analyze the brain networks of autistic and typically-developed children, where the distribution of modularity scores is different between the two types. In future work it will be interesting to further investigate the modularity of biological networks and draw conclusions about their organization.
Netzwerke werden häufig benutzt, um komplexe reale Netzwerke wie die Zelle oder das Gehirn zu modellieren. Ein wichtiger Begriff zur Analyse von Netzwerken ist Modularität. Normalerweise wird ein Netzwerk als modular angesehen, wenn alle Knoten in dichte zusammenhängende Teilmengen partitioniert werden können, die untereinander nur schwach verbunden sind. In dieser Arbeit erweitern wir die Definition von Modularität, um auch Netzwerke zu erfassen, die dichte Module enthalten, die nur schwach mit dem Rest des Netzwerks verbunden sind, aber in denen einige Knoten zum Bereich außerhalb der Module gehören können, dem sogenannten Übergangsbereich. Dementsprechend betrachtet diese Arbeit im Gegensatz zu vollständigen Partitionen die sogenannten Zuordnungen: die Zuweisung von jedem Knoten zu einem Modul im Modulbereich oder zum Übergangsbereich. Die erste Aufgabe, die in dieser Arbeit in Angriff genommen wird, ist die Konstruktion einer formalen Definition von Modularität. Nachdem wir eine Bestandsaufnahme einiger bekannten existierenden Definitionen in der Literatur erstellt haben, fanden wir heraus, dass sie nicht direkt für Netzwerke angewendet werden können, die nicht vollständig partitionierbar sind. Wir entwickelten dann einen Ansatz, der auf zeitkontinuierlichen Random Walks zur Analyse von Netzwerken basiert. Dabei haben wir auf einer reichhaltigen Literatur zum Thema spektrales Clustering aufgesetzt, bei der Netzwerkmodule mit metastabilen Mengen des Random Walks gleichgesetzt werden. Dies erlaubt uns, ein Netzwerk als modular zu definieren, wenn es eine Auswahl von Modulen gibt, die einen grobkörnigen Markow-Prozess erzeugt, dessen Dynamik die des ursprünglichen Random Walks auf dem Netzwerk gut approximiert. Wir zeigen zuerst, dass dieser Score auf künstlichen Netzwerken mit unserer Intuition übereinstimmt und mit der Dichte der Module und der Größe des Modulbereichs zunimmt. Perturbationsanalyse wird dann benutzt, um das korrekte Verhalten des Scores auf zwei speziell konstruierten Klassen von Netzwerken formal zu beweisen. Motiviert sowohl durch die Notwendigkeit, eine gute Zuordnung als Eingabe für den Score zu finden, als auch durch die bekannte Nützlichkeit von Clustering- Methoden ist die zweite anzugehende Aufgabe die des Findens einer guten Zuordnung. Den Ansatz von Markow-Modellen fortsetzend, beschreiben wir einen Algorithmus, der auf einem zeitkontinuierlichen Random Walk auf dem Netzwerk beruht. Als nächstes werden Modifikationen für mehrere etablierte Algorithmen zum vollständigen Partitionieren beschrieben, die bewirken, dass sie Module und Übergangsbereich ausgeben anstelle von vollständigen Partitionen. Die Performance aller Algorithmen wird dann auf einer Klasse von Benchmark-Netzwerken getestet. Schließlich entwickeln wir ein kombinatorisches Modell von Netzwerken, die nicht vollständig partitionierbar sind, als Vereinigung von Split-Graphen, und formulieren das Problem, Module und den Übergangsbereich zu finden, als Grapheditierungsproblem; wir beweisen kombinatorische Schwierigkeit und zeigen exakte Algorithmen und Heuristiken. Die Diskussion jeder der beiden Aufgaben wird vervollständigt durch ein Beispiel einer biologischen Anwendung. Die Identifikation guter Zuordnungen gibt uns eine Möglichkeit, Proteinkomplexe in Proteininteraktionsnetzwerken zu finden, ein gut untersuchtes Thema. Die Flexibilität, ein Protein einem Modul oder dem Übergangsbereich zuzuordnen, hilft dabei, kompliziertere Strukturen als Komplexe zu erkennen. Der Modularitäts-Score wird benutzt, um die Gehirnnetzwerke von autistischen und typisch entwickelten Kindern zu analysieren, wo die Verteilung von Modularitäts-Scores zwischen den beiden Gruppen unterschiedlich ist, was uns Vermutungen über den Grund für diesen Unterschied anstellen lässt. In weiteren Arbeiten wird es interessant sein, die Modularität biologischer Netzwerke weiter zu erforschen und Schlussfolgerungen über ihre Organisation zu ziehen.