Die vorliegende Dissertation widmet sich der theoretischen Untersuchung zweier neuer Algorithmen für Clustering und Community Detection: AWC (Adaptive Weights Clustering) und AWCD (Adaptive Weights Community Detection). Ein zentraler Aspekt sind dabei die Raten der Konsistenz. Bei der Betrachtung von AWC steht die Tiefe Lücke zwischen den Clustern, also die relative Differenz der jeweiligen Dichten, im Vordergrund. Bis auf logarithmische Faktoren ist die erreichte Konsistenzrate optimal. Dies erweitert die niedrigdimensionalen Ergebnisse von Efimov, Adamyan and Spokoiny (2019) auf das Mannigfaltigkeitenmodell und berücksichtigt darüber hinaus viel allgemeinere Bedingungen an die zugrunde liegende Dichte und die Form der Cluster. Insbesondere wird der Fall betrachtet, bei dem zwei Punkte des gleichen Clusters nahe an dessen Rand liegen. Zudem werden Ergebnisse für endliche Stichproben und die optimale Wahl des zentralen Parameters λ diskutiert. Bei der Untersuchung von AWCD steht die Asymptotik der Differenz θ − ρ zwischen den beiden Bernoulli Parametern eines symmetrischen stochastischen Blockmodells im Mittelpunkt. Es stellt sich heraus, dass das Gebiet der starken Konsistenz bei weitem nicht optimal ist. Es werden jedoch zwei Modifikationen des Algorithmus vorgeschlagen: Zum einen kann der Bias der beteiligten Schätzer minimiert werden. Zum anderen schlagen wir vor, die Größe der initialen Schätzung der Struktur der Gruppen zu erhöhen, indem auch längere Pfade mit berücksichtigt werden. Mithilfe dieser Modifikationen erreicht der Algorithmus eine nahezu optimale Konsistenzrate. Teilweise können diese Ergebnisse auch auf allgemeinere stochastische Blockmodelle erweitert werden. Für beide Probleme illustrieren und validieren wir außerdem die theoretischen Resultate durch umfangreiche Experimente. Abschließend lässt sich sagen, dass die vorliegende Arbeit die Lücke zwischen theoretischen und praktischen Ergebnissen für die Algorithmen AWC und AWCD schließt. Insbesondere sind beide Algorithmen nach einigen Modifikationen auf relevanten Modellen konsistent mit einer nahezu optimalen Rate. / This thesis presents a theoretical study of two novel algorithms for clustering and community detection: AWC (Adaptive Weights Clustering) and AWCD (Adaptive Weights Community Detection). Most importantly, we discuss rates of consistency. For AWC, we focus on the asymptotics of the depth ε of the gap between clusters, i.e. the relative difference between the density level of the clusters and the density level of the area between them. We show that AWC is consistent with a nearly optimal rate. This extends the low-dimensional results of Efimov, Adamyan and Spokoiny (2019) to the manifold model while also considering much more general assumptions on the underlying density and the shape of clusters. In particular, we also consider the case of two points in the same cluster that are relatively close to the boundary. Moreover, we provide finite sample guarantees as well as the optimal tuning parameter λ. For AWCD, we consider the asymptotics of the difference θ − ρ between the two Bernoulli parameters of a symmetric stochastic block model. As it turns out, the resulting regime of strong consistency is far from optimal. However, we propose two major modifications to the algorithm: Firstly, we discuss an approach to minimize the bias of the involved estimates. Secondly, we suggest increasing the starting neighborhood guess of the algorithm by taking into account paths of minimal path length k. Using these modifications, we are able to show that AWCD achieves a nearly optimal rate of strong consistency. We partially extend these results to more general stochastic block models. For both problems, we illustrate and validate the theoretical study through a wide range of numerical experiments. To summarize, this thesis closes the gap between the practical and theoretical studies for AWC and AWCD. In particular, after some modifications, both algorithms exhibit a nearly optimal performance on relevant models.

Eine der stärksten Erweiterungen der klassischen Theorie formaler Sprachen und Automaten ist die Einbeziehung von Gewichten oder Vielfachheiten aus einem Halbring. Diese Dissertation untersucht gewichtete Automaten über Strukturen mit Nebenläufigkeit. Wir erweitern die Arbeit von Lodaya und Weil und erhalten so ein Modell gewichteter verzweigender Automaten, in dem die Berechnung des Gewichts einer parallelen Komposition anders als die einer sequentiellen Komposition gehandhabt wird. Die von Lodaya und Weil eingeführten Automaten modellieren Nebenläufigkeit durch Verzweigen. Ein verzweigender Automat ist ein endlicher Automat mit drei verschiedenen Typen von Transitionen. Sequentielle Transitionen überführen durch Ausführen eines Ereignisses einen Zustand in einen anderen. Dagegen sind Gabel- und Binde-Transitionen für das Verzweigen verantwortlich. Läufe dieser Automaten werden beschrieben durch sequentiell-parallele posets, kurz sp-posets. Alle Transitionen des Automaten werden in unserem Modell mit Gewichten versehen. Neben dem Nichtdeterminismus und der sequentiellen Komposition wollen wir nun auch die parallele Komposition quantitativ behandeln. Dafür benötigen wir eine Gewichtsstruktur mit einer Addition, einer sequentiellen und einer parallelen Multiplikation. Solch eine Struktur, genannt Bihalbring, besteht damit de facto aus zwei Halbringen mit derselben additiven Struktur. Weiterhin muss die parallele Multiplikation kommutativ sein. Das Verhalten eines gewichteten verzweigenden Automaten ist dann eine Funktion, die jeder sp-poset ein Element eines Bihalbrings zuordnet. Das Hauptresultat charakterisiert das Verhalten dieser Automaten im Sinne von Kleenes und Schützenbergers Sätzen über das Zusammenfallen der Klassen der erkennbaren und der rationalen Sprachen bzw. formalen Potenzreihen. Darüber hinaus untersuchen wir den Abschluss dieser Verhalten unter allen rationalen Operationen und unter dem Hadamard-Produkt. Letztlich diskutieren wir Zusammenhänge zwischen Reihen und Sprachen im Rahmen verzweigender Automaten. / One of the most powerful extensions of classical formal language and automata theory is the consideration of weights or multiplicities from a semiring. This thesis investigates weighted automata over structures incorporating concurrency. Extending work by Lodaya and Weil, we propose a model of weighted branching automata in which the calculation of the weight of a parallel composition is handled differently from the calculation of the weight of a sequential composition. The automata as proposed by Lodaya and Weil model concurrency by branching. A branching automaton is a finite-state device with three different types of transitions. Sequential transitions transform a state into another one by executing an action. In contrast, fork and join transitions are responsible for branching. Executions of such systems can be described by sequential-parallel posets, or sp-posets for short. In the model considered here all kinds of transitions are equipped with weights. Beside non-determinism and sequential composition we would like to deal with the parallel composition in a quantitative way. Therefore, we are in need of a weight structure equipped with addition, a sequential, and, moreover, a parallel multiplication. Such a structure, called a bisemiring, is actually composed of two semirings with the same additive structure. Moreover, the parallel multiplication has to be commutative. Now, the behavior of a weighted branching automaton is a function that associates with every sp-poset an element from the bisemiring. The main result characterizes the behavior of these automata in the spirit of Kleene's and Schützenberger's theorems about the coincidence of recognizable and rational languages, and formal power series, respectively. Moreover, we investigate the closure of behaviors under all rational operations and under Hadamard-product. Finally, we discuss connections between series and languages within our setting.

Eine der stärksten Erweiterungen der klassischen Theorie formaler Sprachen und Automaten ist die Einbeziehung von Gewichten oder Vielfachheiten aus einem Halbring. Diese Dissertation untersucht gewichtete Automaten über Strukturen mit Nebenläufigkeit. Wir erweitern die Arbeit von Lodaya und Weil und erhalten so ein Modell gewichteter verzweigender Automaten, in dem die Berechnung des Gewichts einer parallelen Komposition anders als die einer sequentiellen Komposition gehandhabt wird. Die von Lodaya und Weil eingeführten Automaten modellieren Nebenläufigkeit durch Verzweigen. Ein verzweigender Automat ist ein endlicher Automat mit drei verschiedenen Typen von Transitionen. Sequentielle Transitionen überführen durch Ausführen eines Ereignisses einen Zustand in einen anderen. Dagegen sind Gabel- und Binde-Transitionen für das Verzweigen verantwortlich. Läufe dieser Automaten werden beschrieben durch sequentiell-parallele posets, kurz sp-posets. Alle Transitionen des Automaten werden in unserem Modell mit Gewichten versehen. Neben dem Nichtdeterminismus und der sequentiellen Komposition wollen wir nun auch die parallele Komposition quantitativ behandeln. Dafür benötigen wir eine Gewichtsstruktur mit einer Addition, einer sequentiellen und einer parallelen Multiplikation. Solch eine Struktur, genannt Bihalbring, besteht damit de facto aus zwei Halbringen mit derselben additiven Struktur. Weiterhin muss die parallele Multiplikation kommutativ sein. Das Verhalten eines gewichteten verzweigenden Automaten ist dann eine Funktion, die jeder sp-poset ein Element eines Bihalbrings zuordnet. Das Hauptresultat charakterisiert das Verhalten dieser Automaten im Sinne von Kleenes und Schützenbergers Sätzen über das Zusammenfallen der Klassen der erkennbaren und der rationalen Sprachen bzw. formalen Potenzreihen. Darüber hinaus untersuchen wir den Abschluss dieser Verhalten unter allen rationalen Operationen und unter dem Hadamard-Produkt. Letztlich diskutieren wir Zusammenhänge zwischen Reihen und Sprachen im Rahmen verzweigender Automaten. / One of the most powerful extensions of classical formal language and automata theory is the consideration of weights or multiplicities from a semiring. This thesis investigates weighted automata over structures incorporating concurrency. Extending work by Lodaya and Weil, we propose a model of weighted branching automata in which the calculation of the weight of a parallel composition is handled differently from the calculation of the weight of a sequential composition. The automata as proposed by Lodaya and Weil model concurrency by branching. A branching automaton is a finite-state device with three different types of transitions. Sequential transitions transform a state into another one by executing an action. In contrast, fork and join transitions are responsible for branching. Executions of such systems can be described by sequential-parallel posets, or sp-posets for short. In the model considered here all kinds of transitions are equipped with weights. Beside non-determinism and sequential composition we would like to deal with the parallel composition in a quantitative way. Therefore, we are in need of a weight structure equipped with addition, a sequential, and, moreover, a parallel multiplication. Such a structure, called a bisemiring, is actually composed of two semirings with the same additive structure. Moreover, the parallel multiplication has to be commutative. Now, the behavior of a weighted branching automaton is a function that associates with every sp-poset an element from the bisemiring. The main result characterizes the behavior of these automata in the spirit of Kleene's and Schützenberger's theorems about the coincidence of recognizable and rational languages, and formal power series, respectively. Moreover, we investigate the closure of behaviors under all rational operations and under Hadamard-product. Finally, we discuss connections between series and languages within our setting.

No description available.