Some networks obtained from real world problems such as social networks, biological cells or earthquake recurrence networks, may consist of many thousands of vertices and exhibit a pronounced modular structure. To facilitate further analysis or derive a simple model of the whole system, it is often useful to identify subunits of these networks that are nearly disconnected from the remaining graph, called “clusters”. A well-known method to find clusters in undirected networks is based on random processes whose state space is the network's set of vertices, moving in each time step to a randomly chosen neighboring vertex. A close correspondence between network substructures and properties of such a random walk process has been exploited in numerical algorithms, which aim at decomposing the random walk's state space into disjoint “metastable” sets, describing nearly stable conditions of the system which are rarely changed. This dissertation contains an introduction to the theory of graphs and random walks, summarizes some popular cluster analysis methods and eventually presents and explores a new method which is based on random walks as well, but does not require the computationally costly approximation of eigenvectors. Instead, it uses “hitting times” that describe the expected number of time steps the random walk takes to enter a given target set. For the purpose of assessing runtime scaling, a family of sparse, directed, random networks spanning several orders of magnitude in vertex count is introduced. A series of tests verified that runtime of the presented algorithm scales linearly with the number of vertices in these network, in accordance with theoretical results. Therefore, the new approach is well suited for very large networks that are sufficiently sparse and shows a computational advantage over existing methods requiring eigenvector approximations. The presented method has one main caveat: The hitting times used in the detection of metastable sets are well-defined and finite only if each target set can be reached via a directed path from any vertex in the graph and the random walk is ergodic. This requires the graph to be strongly connected, which implies that it must be free of sinks and sources. Due to this restriction, many directed graphs are not eligible. The final discussion sketches an approach on how to overcome that limitation. Still, the set of strongly connected graphs is a significant extension of the set of undirected graphs, widening random walk based cluster analysis to an even broader field of application.
Ein häufig wiederkehrendes Problem bei der Arbeit mit großen Systemen unterschiedlicher Natur, etwa zellularen, elektrischen oder sozialen Netzwerken, ist die Erkennung funktionaler Untereinheiten, die eine hohe Eigenständigkeit vom Rest des Systems auszeichnet. Dazu bietet es sich an, das zu untersuchende System als Graphen zu modellieren und diesen mittels Clusteranalyse in Teile zu zerlegen, die zueinander wenige Verbindungen aufweisen, relativ zur Kantendichte innerhalb der Cluster. Ein bekannter Ansatz dazu basiert auf erinnerungslosen Zufallsprozessen, die sich mit jedem Zeitschritt von einer Ecke entlang einer anliegenden Kante zu einer zufällig gewählten benachbarten Ecke fortbewegen. Die Motivation hinter diesem Ansatz ist die Vorstellung, dass eine Zerlegung der Eckenmenge des Graphen in disjunkte, „metastabile” Mengen existiert, die nahezu stabile Zustände des Prozesses beschreiben, also nur sehr selten gewechselt werden. In dieser Dissertation wird die Theorie von Graphen und Zufallsprozessen eingeführt, einige bekannte Methoden der Clusteranalyse zusammen gefasst und schließlich eine neue Methode vorgeschlagen und analysiert, die ebenfalls auf Zufallsprozessen basiert, aber ohne die aufwändige Berechnung von Eigenvektoren auskommt. Stattdessen werden „Stoppzeiten” genutzt, die beschreiben, wie lange ein Zufallsprozess, der auf dem Netzwerk wandert, im Durchschnitt benötigt, um eine fest gewählte Zielmenge zu erreichen. Es wird aufgezeigt, dass diese neue Methode einen klaren Vorteil in der Skalierung des Rechenaufwandes zeigt, da die nötigen Rechenschritte zur Berechnung der Stoppzeiten im ungünstigsten Fall quadratisch mit der Zahl der Ecken ansteigt. Für dünn besetzte Graphen, in denen jede Ecke eine feste Zahl an Nachbarn nicht übersteigen darf, zeigen hier präsentierte numerische Experimente an großen Zufallsgraphen, dass die nötige Rechenzeit sogar näherungsweise linear mit der Eckenzahl der Graphen ansteigt. Im Gegensatz dazu skalieren klassische Zerlegungsalgorithmen, die eine Berechnung von Eigenvektoren erfordern, deutlich höher, nämlich mehr als quadratisch, mit der Eckenzahl. Die präsentierte neue Methode unterliegt jedoch einer Einschränkung: Die eingesetzten Stoppzeiten haben nur dann garantiert endliche Werte, wenn die gewählte Zielmenge sich von jeder Ecke des Graphen tatsächlich erreichen lässt und der Prozess in endlicher Zeit fast sicher jede Ecke wieder besucht. Das setzt voraus, dass der Graph stark zusammenhängend, insbesondere frei von Quellen und Senken sein muss. Dies schließt viele gerichtete Graphen aus, stellt aber immer noch eine echte Erweiterung gegenüber der Klasse der ungerichteten Graphen dar. Ansätze zur Überwindung dieser Einschränkung werden in der Auswertung skizziert.
