22455 research outputs found
Sort by
Erkennung einer Adipositas-bedingten Obstruktion mit Ganzkörperplethysmographie und Spirometrie
Get PDFImproved voltage clamp fluorometry to investigate the molecular function of the P2X7 receptor C-terminus and characterization of novel P2X7 receptor ligands
Get PDFThe ATP-gated, purinergic P2X7 receptor (P2X7R) is a trimeric, non-selective cation channel with key functions in inflammation and immunity. It mediates a multitude of cellular events that are normally not associated with ion channel functions (e.g. modification of the plasma membrane, cytokine release, and cell death). Compared to the other homologous P2X receptor subunits (P2X1-P2X6), the P2X7 subunit contains an unusually long intracellular C-terminus, which is thought to be essential for most of these cellular responses [4.1]. However, the underlying molecular mechanisms and signaling pathways are incompletely understood. The role of the P2X7R in immune signaling and especially its involvement in diverse pathophysiological processes such as inflammation, epilepsy, Alzheimer’s disease, and cancer makes it an interesting drug target. To validate the P2X7R as a drug target, detailed understanding of its molecular and physiological functions, cell-type specific expression, and selective ligands are required. A major aim of this work was the investigation of the molecular consequences of P2X7R activation and the identification of potent antagonists. In addition, I investigated the localization of the P2X7R and thereby contributed to the characterization of a novel P2X7 mouse model. To investigate conformational changes in the molecular structure of the P2X7R that are associated with its activation, I applied voltage clamp fluorometry (VCF) ([4.2]). To this end, I refined a method for the incorporation of the environment-sensitive fluorescent unnatural amino acid (fUAA) ANAP into Xenopus laevis oocyte-expressed receptors. Furthermore, I constructed a VCF setup optimized for the detection of ANAP-specific fluorescence changes. VCF measurements from ANAP-containing P2X7R-expressing oocytes provided evidence that the ATP-induced conformational changes in extracellular and transmembrane domains are not translated to the intra-cellular C-terminus and that the P2X7-characteristic current facilitation is an intrinsic receptor property and likely associated with change in its gating ([3.1]). To determine and compare the potency of novel small-molecule P2X7R antagonists, I performed two-electrode voltage clamp (TEVC) analysis on P2X7R-expressing X. laevis oocytes ([3.2], [4.3]). These data revealed a compound with nanomolar potency, for which I further analyzed association and dissociation kinetics and confirmed its binding to the P2X7R allosteric binding pocket by site-directed mutagenesis. Finally, I contributed to the validation of a novel BAC transgenic reporter mouse model and the determination of the controversially discussed P2X7 expression pattern ([4.4] and [3.3]) by performing immunohistochemical tissue stainings to compare endogenous and transgenic P2X7R expression patterns. Together, these studies advanced our knowledge about molecular principles underlying P2X7 signal transduction, identified a new potent drug lead, and helped to provide a novel mouse model to investigate P2X7R localization and physiological functions. In an unrelated publication ([3.4]), I helped to characterize nicotinic acetylcholine receptor ligands by TEVC
Formal analysis of control systems via inductive approaches
Get PDFThis dissertation is concerned with the formal analysis of complex control systems via inductive approaches using barrier certificates. In general, safety-critical applications such as air traffic networks, autonomous vehicles, power grids, medical devices, and robotic equipment, are expected to satisfy complex logic specifications including but not limited to safety, reachability, and security. Due to several factors such as the continuous-state evolution of systems' trajectories, large systems' sizes, disturbances, etc., verification and synthesis of control systems against such high-level logic specifications is a challenging task.
An interesting yet simple way to tackle the verification and synthesis problem for logic specifications is to utilize inductive approaches based on barrier certificates. Barrier certificates take the form of inductive invariants and provide sufficient conditions for the satisfaction of safety or reachability specifications. Therefore, the verification and synthesis problem is reduced to the discovery of suitable barrier certificates. However, finding suitable barrier certificates can be a difficult problem due to several factors. First, the computation of barrier certificates is not scalable to large-scale systems. Second, the conditions imposed by barrier certificates are restrictive, making it difficult to search for one. Third, barrier certificate-based methods are limited to the analysis of safety or reachability specifications. As a result, they are not directly applicable to complicated logic tasks such as those expressed by omega-regular properties or (in)finite strings over automata, as well as security specifications such as those expressed by hyperproperties. In this regard, the dissertation focuses on alleviating the aforementioned issues and provides novel techniques to verify and synthesize controllers for (possibly large-scale and stochastic) control systems against the aforementioned specifications.
The first part of the thesis proposes a compositional framework for scalable construction of control barrier certificates for large-scale discrete-time stochastic control systems. In particular, we show that by considering the large-scale system as an interconnected one composed of several subsystems, one may construct control barrier certificates for the interconnected system by searching for so-called control sub-barrier certificates for subsystems and utilizing some compositionality conditions based on small-gain and dissipativity approaches. Correspondingly, one may also synthesize controllers that can be applied to the interconnected system in a decentralized manner, so that the large-scale system satisfies safety specifications over (in)finite time horizons with some probability lower bounds.
In the second part of the thesis, we propose a new notion of k-inductive barrier certificates for the verification of (stochastic) discrete-time dynamical systems against safety and reachability specifications. In particular, we illustrate that due to the restrictive nature of the traditional barrier certificate conditions, it is not always possible to find suitable barrier certificates even when the system is guaranteed to satisfy the desired specifications. Then, we extend the k-induction principle utilized in software verification to propose several notions of k-inductive barrier certificates that relax the traditional barrier certificate conditions. As a result, larger classes of functions may act as barrier certificates, making them easier to find. In the context of non-stochastic systems, we propose two notions of k-inductive barrier certificates and provide formal guarantees for safety specifications. In the case of stochastic systems, we propose one notion of k-inductive barrier certificates for safety and two notions for tackling reachability specifications. Then, we obtain probabilistic guarantees for the satisfaction of safety and reachability specifications over infinite time horizons, respectively.
The last part of the thesis is concerned with the analysis of (stochastic) control systems against complex logic specifications beyond safety and reachability. First, we consider the synthesis problem for (possibly large-scale) stochastic control systems against \emph{trace properties}, which describe specifications over individual traces of the system. Examples of such properties include omega-regular languages or (in)finite words over automata. We provide an automata-theoretic approach to decompose such complex specifications into sequential safety specifications. We then utilize the probability guarantees obtained for the safety specifications and combine them to obtain probability lower bounds for the satisfaction of original specifications. We provide such guarantees over both finite and infinite time horizons. Secondly, we consider the verification problem for non-stochastic systems against specifications that can be expressed over sets of traces, called hyperproperties. Hyperproperties can express many security and planning specifications that cannot be considered using omega-regular languages.
In this context, we provide an automata-theoretic approach to decompose hyperproperties into smaller verification conditions called conditional invariances. Then, we introduce a new notion of so-called augmented barrier certificates constructed on the augmented system (i.e., self-composition of the system) to provide guarantees for the satisfaction of the conditional invariances. These guarantees may then be combined to achieve the satisfaction of original hyperproperties.Diese Dissertation befasst sich mit der formalen Analyse komplexer Regelkreise, wobei induktive Ansätze unter Verwendung von Barrierezertifikaten zum Einsatz kommen. Im Allgemeinen wird von sicherheitskritischen Anwendungen wie Flugverkehrsnetzen, autonomen Fahrzeugen, Stromnetzen, medizinischen Geräten und Roboteranlagen erwartet, dass sie komplexe formale Spezifikationen erfüllen, um etwa die Betriebs- und Informationssicherheit zu gewährleisten oder anderweitige Ziele wie beispielsweise bestimmte Erreichbarkeitseigenschaften einzuhalten. Aufgrund verschiedener Faktoren wie der kontinuierlichen Zeitentwicklung der Systemtrajektorien, der Größe der Systeme, Störungen usw. ist die Verifizierung und Synthese von Steuersystemen anhand von solch allgemeinen logischen Spezifikationen eine anspruchsvolle Aufgabe.
Ein interessanter und dennoch einfacher Weg, das Verifikations- und Syntheseproblem für formale Spezifikationen anzugehen, ist die Verwendung von induktiven Ansäzen, die auf Barrierezertifikaten basieren. Diese haben die Form von induktiven Invarianten und liefern hinreichende Bedingungen für die Erfüllung von Sicherheits- oder Erreichbarkeitsanforderungen. Daher reduziert sich das Verifikations- und Syntheseproblem auf die Entdeckung geeigneter Barrierezertifikate. Die Suche nach geeigneten Barrierezertifikaten kann jedoch aufgrund mehrerer Faktoren ein schwieriges Problem darstellen. Erstens skaliert die Berechnung von Barrierezertifikaten nicht ohne weiteres auf große Systeme. Zweitens stellen die von Barrierezertifikaten auferlegten Bedingungen eine starke Einschränkung dar, was die Suche nach einem solchen Zertifikat erschwert. Drittens sind auf Barrierezertifikaten basierende Methoden auf die Analyse von Sicherheits- oder Erreichbarkeitsspezifikationen limitiert. Infolgedessen sind sie nicht direkt auf komplizierte logische Aufgaben anwendbar, wie z.B. solche, die durch omega-reguläre Eigenschaften oder (un)endliche Zeichenketten über Automaten ausgedrückt werden, oder auf bestimmte Sicherheitsspezifikationen, etwa wenn sie durch Hypereigenschaften ausgedrückt werden. In dieser Hinsicht konzentriert sich die Dissertation auf die Linderung der oben genannten Probleme und stellt neuartige Techniken zur Verifikation und Synthese von Reglern f\ür (möglicherweise große und stochastische) Regelkreise hinsichtlich der oben genannten Spezifikationen zur Verfügung.
IIm ersten Teil der Dissertation wird ein kompositorischer Rahmen für die skalierbare Konstruktion von Regelungsbarrierezertifikaten für große, zeitdiskrete und stochastische Regelkreise vorgeschlagen. Insbesondere zeigen wir, dass man durch die Zerlegung des Systems in mehrere, zusammenhängende Subsysteme Regelungsbarrierezertifikate für das Gesamtsystem konstruieren kann, indem man nach sogenannten Regelungsunterbarrierezertifikaten für die Subsysteme sucht. Hierzu lassen sich bestimmte Kompositionalitätsbedingungen auf der Basis von small-gain und dissipativity Ansätzen formulieren. Dementsprechend kann man auch Regler synthetisieren, die dezentral auf die zusammenhängenden Komponenten des Systems angewendet werden können, so dass das Gesamtsystem die Sicherheitsspezifikationen über (un)endliche Zeithorizonte mit einigen Wahrscheinlichkeitsuntergrenzen erfüllt.
Im zweiten Teil der Dissertation stellen wir das neuartige Konzept der k-induktiven Barrierezertifikate für die Verifikation von (stochastischen) zeitdiskreten dynamischen Systemen bezüglich Sicherheits- und Erreichbarkeitsspezifikationen vor. Insbesondere zeigen wir, dass es aufgrund der restriktiven Natur der traditionellen Barrierezertifikatsbedingungen nicht immer möglich ist, geeignete Barrierezertifikate zu finden, selbst wenn das System garantiert die gewünschten Spezifikationen erfüllt. Im Anschluss erweitern wir das k-Induktionsprinzip, das in der Softwareverifikation verwendet wird, indem wir mehrere Konzepte für k-induktive Barrierezertifikate vorschlagen, die die traditionellen Barrierezertifikatsbedingungen lockern. Infolgedessen können größere Klassen von Funktionen als Barrierezertifikate fungieren, wodurch sie leichter zu finden sind. Im Zusammenhang mit nicht-stochastischen Systemen führen wir zwei Ausprägungen von k-induktiven Barrierezertifikaten ein und geben formale Garantien für Sicherheitsspezifikationen. Für stochastische Systeme stellen wir ein Konzept für k-induktive Barrierezertifikate für Sicherheit und zwei Konzepte für die Behandlung von Erreichbarkeitsspezifikationen vor. Danach erarbeiten wir probabilistische Garantien für die Erfüllung von Sicherheits- und Erreichbarkeitsanforderungen über unendliche Zeithorizonte.
Der letzte Teil der Dissertation befasst sich mit der Analyse von (stochastischen) Regelkreisen bezüglich komplexer logischer Spezifikationen jenseits von Sicherheit und Erreichbarkeit. Zunächst betrachten wir das Syntheseproblem für (möglicherweise großräumige) stochastische Regelkreise im Hinblick auf Spureigenschaften, also Spezifikationen über einzelne Spuren des Systems. Beispiele für solche Eigenschaften sind omega-reguläre Sprachen oder (un)endliche Wörter über Automaten. Wir bieten einen automaten-theoretischen Ansatz, um solche komplexen Spezifikationen in sequenzielle Sicherheitsspezifikationen zu zerlegen. Wir verwenden sogleich die für die Sicherheitsspezifikationen erhaltenen Wahrscheinlichkeitsgarantien und kombinieren sie, um untere Wahrscheinlichkeitsschranken für die Erfüllung der ursprünglichen Spezifikationen zu erhalten. Wir geben derartige Garantien sowohl für endliche als auch für unendliche Zeithorizonte. Im Anschluss betrachten wir das Verifikationsproblem für nicht-stochastische Systeme bezüglich Spezifikationen, die über Mengen von Spuren, so genannte Hypereigenschaften, ausgedrückt werden können. Hypereigenschaften können viele Sicherheits- und Planungsspezifikationen ausdrücken, die mittels omega-regulären Sprachen nicht betrachtet werden können.
In diesem Zusammenhang stellen wir einen automaten-theoretischen Ansatz zur Verfügung, um Hypereigenschaften in kleinere Verifikationsbedingungen, sogenannte bedingten Invarianzen, zu zerlegen. Darauf aufbauend führen wir das Konzept des erweiterten Barrierezertifikats ein, welches auf dem (mittels Selbstkomposition) erweiterten System konstruiert wird, um Garantien für die Erfüllung der bedingten Invarianzen zu geben. Diese Garantien können dann wiederum kombiniert werden, um die Erfüllung der ursprünglichen Hypereigenschaften zu erreichen
Der Zusammenhang zwischen elektrophysiologischen Wirksamkeitsparametern, Begleitmedikation und Behandlungsergebnissen der Elektrokonvulsionstherapie bei Patienten mit Schizophrenie
Get PDFLearning from complex networks
Get PDFGraph Theory has proven to be a universal language for describing modern complex systems. The elegant theoretical framework of graphs drew the researchers' attention over decades. Therefore, graphs have emerged as a ubiquitous data structure in various applications where a relational characteristic is evident. Graph-driven applications are found, e.g., in social network analysis, telecommunication networks, logistic processes, recommendation systems, modeling kinetic interactions in protein networks, or the 'Internet of Things' (IoT) where modeling billions of interconnected web-enabled devices is of paramount importance.
This thesis dives deep into the challenges of modern graph applications. It proposes a robustified and accelerated spectral clustering model in homogeneous graphs and novel transformer-driven graph shell models for attributed graphs.
A new data structure is introduced for probabilistic graphs to compute the information flow efficiently. Moreover, a metaheuristic algorithm is designed to find a good solution to an optimization problem composed of an extended vehicle routing problem. The thesis closes with an analysis of trend flows in social media data.
Detecting communities within a graph is a fundamental data mining task of interest in virtually all areas and also serves as an unsupervised preprocessing step for many downstream tasks. One most the most well-established clustering methods is Spectral Clustering. However, standard spectral clustering is highly sensitive to noisy input data, and the eigendecomposition has a high, cubic runtime complexity O(n^3). Tackling one of these problems often exacerbates the other. This thesis presents a new model which accelerates the eigendecomposition step by replacing it with a Nyström approximation. Robustness is achieved by iteratively separating the data into a cleansed and noisy part of the data. In this process, representing the input data as a graph is vital to identify parts of the data being well connected by analyzing the vertices' distances in the eigenspace.
With the advances in deep learning architectures, we also observe a surge in research on graph representation learning.
The message-passing paradigm in Graph Neural Networks (GNNs) formalizes a predominant heuristic for multi-relational and attributed graph data to learn node representations. In downstream applications, we can use the representations to tackle theoretical problems known as node classification, graph classification/regression, and relation prediction. However, a common issue in GNNs is known as over-smoothing. By increasing the number of iterations within the message-passing, the nodes' representations of the input graph align and become indiscernible.
This thesis shows an efficient way of relaxing the GNN architecture by employing a routing heuristic in the general workflow. Specifically, an additional layer routes the nodes' representations to dedicated experts. Each expert calculates the representations according to their respective GNN workflow. The definitions of distinguishable GNNs result from k-localized views starting from a central node. This procedure is referred to as Graph Shell Attention (SEA), where experts process different subgraphs in a transformer-motivated fashion.
Reliable propagation of information through large communication networks, social networks, or sensor networks is relevant to applications concerning marketing, social analysis, or monitoring physical or environmental conditions. However, social ties of friendship may be obsolete, and communication links may fail, inducing the notion of uncertainty in such networks. This thesis addresses the problem of optimizing information propagation in uncertain networks given a constrained budget of edges.
A specialized data structure, called F-tree, addresses two NP-hard subproblems: the computation of the expected information flow and the optimal choice of edges. The F-tree identifies independent components of a probabilistic input graph for which the information flow can either be computed analytically and efficiently or for which traditional Monte-Carlo sampling can be applied independently of the remaining network.
The next part of the thesis covers a graph problem from the Operations Research point of view. A new variant of the well-known vehicle routing problem (VRP) is introduced, where customers are served within a specific time window (TW), as well as flexible delivery locations (FL) including capacity constraints. The latter implies that each customer is scheduled in one out of a set of capacitated delivery service locations. Practically, the VRPTW-FL problem is relevant for applications in parcel delivery, routing with limited parking space, or, for example, in the scope of hospital-wide scheduling of physical therapists. This thesis presents a metaheuristic built upon a hybrid Adaptive Large Neighborhood Search (ALNS). Moreover, a backtracking mechanism in the construction phase is introduced to alter unsatisfactory decisions at early stages. In the computational study, hospital data is used to evaluate the utility of flexible delivery locations and various cost functions.
In the last part of the thesis, social media trends are analyzed, which yields insights into user sentiment and newsworthy topics. Such trends consist of bursts of messages concerning a particular topic within a time frame, significantly deviating from the average appearance frequency of the same subject. This thesis presents a method to classify trend archetypes to predict future dissemination by investigating the dissemination of such trends in space and time.
Generally, with the ever-increasing scale and complexity of graph-structured datasets and artificial intelligence advances, AI-backed models will inevitably play an important role in analyzing, modeling, and enhancing knowledge extraction from graph data.Die Graphentheorie hat sich zur einer universellen Sprache entwickelt, mit Hilfe derer sich moderne und komplexe Systeme und Zusammenhänge beschreiben lassen. Diese theoretisch elegante und gut fundierte Rahmenstruktur attrahierte über Dekaden hinweg die Aufmerksamkeit von Wissenschaftlern/-innen. In der heutigen Informationstechnologie-Landschaft haben sich Graphen längst zu einer allgegenwärtigen Datenstruktur in Anwendungen etabliert, innerhalb derer charakteristische Zusammenhangskomponenten eine zentrale Rolle spielen. Anwendungen, die über Graphen unterstützt werden, finden sich u.a. in der Analyse von sozialen Netzwerken, Telekommunikationsnetwerken, logistische Prozessverwaltung, Analyse von Empfehlungsdiensten, in der Modellierung kinetischer Interaktionen von Proteinstrukturen, oder auch im "Internet der Dinge" (engl.: 'Internet Of Things' (IoT)), welches das Zusammenspiel von abermillionen web-unterstützte Endgeräte abbildet und eine prädominierende Rolle für große IT-Unternehmen spielt.
Diese Dissertation beleuchtet die Herausforderungen moderner Graphanwendungen. Im Bereich homogener Netzwerken wird ein beschleunigtes und robustes spektrales Clusteringverfahren, sowie ein Modell zur Untersuchung von Teilgraphen mittels Transformer-Architekturen für attribuierte Graphen vorgestellt. Auf wahrscheinlichkeitsbasierten homogenen Netzwerken wird eine neue Datenstruktur eingeführt, die es erlaubt einen effizienten Informationsfluss innerhalb eines Graphen zu berechnen. Darüber hinaus wird ein Optimierungsproblem in Transportnetzwerken beleuchtet, sowie eine Untersuchung von Trendflüssen in sozialen Medien diskutiert.
Die Untersuchung von Verbünden (engl.: 'Clusters') von Graphdaten stellt einen Eckpfeiler im Bereich der Datengewinnung dar. Die Erkenntnisse sind nahezu in allen praktischen Bereichen von Relevanz und dient im Bereich des unüberwachten Lernens als Vorverarbeitungsschritt für viele nachgeschaltete Aufgaben. Einer der weit verbreitetsten Methodiken zur Verbundanalyse ist das spektrale Clustering. Die Qualität des spektralen Clusterings leidet, wenn die Eingabedaten sehr verrauscht sind und darüber hinaus ist die Eigenwertzerlegung mit O(n^3) eine teure Operation und damit wesentlich für die hohe, kubische Laufzeitkomplexität verantwortlich. Die Optimierung von einem dieser Kriterien exazerbiert oftmals das verbleibende Kriterium. In dieser Dissertation wird ein neues Modell vorgestellt, innerhalb dessen die Eigenwertzerlegung über eine Nyström Annäherung beschleunigt wird. Die Robustheit wird über ein iteratives Verfahren erreicht, das die gesäuberten und die verrauschten Daten voneinander trennt. Die Darstellung der Eingabedaten über einen Graphen spielt hierbei die zentrale Rolle, die es erlaubt die dicht verbundenen Teile des Graphen zu identifizieren. Dies wird über eine Analyse der Distanzen im Eigenraum erreicht.
Parallel zu neueren Erkenntnissen im Bereich des Deep Learnings lässt sich auch ein Forschungsdrang im repräsentativen Lernen von Graphen erkennen. Graph Neural Networks (GNN) sind eine neue Unterform von künstlich neuronalen Netzen (engl.: 'Artificial Neural Networks') auf der Basis von Graphen. Das Paradigma des sogenannten 'message-passing' in neuronalen Netzen, die auf Graphdaten appliziert werden, hat sich hierbei zur prädominierenden Heuristik entwickelt, um Vektordarstellungen von Knoten aus (multi-)relationalen, attribuierten Graphdaten zu lernen. Am Ende der Prozesskette können wir somit theoretische Probleme angehen und lösen, die sich mit Fragestellungen über die Klassifikation von Knoten oder Graphen, über regressive Ausdrucksmöglichkeiten bis hin zur Vorhersage von relationaler Verbindungen beschäftigen.
Ein klassisches Problem innerhalb graphischer neuronaler Netze ist bekannt unter der Terminologie des 'over-smoothing' (dt.: 'Überglättens'). Es beschreibt, dass sich mit steigender Anzahl an Iterationen des wechselseitigen Informationsaustausches, die Knotenrepräsentationen im vektoriellen Raum angleichen und somit nicht mehr unterschieden werden können. In dieser Forschungsarbeit wird eine effiziente Methode vorgestellt, die die klassische GNN Architektur aufbricht und eine Vermittlerschicht in den herkömmlichen Verarbeitungsfluss einarbeitet. Konkret gesprochen werden hierbei Knotenrepräsentationen an ausgezeichnete Experten geschickt. Jeder Experte verarbeitet auf idiosynkratischer Basis die Knoteninformation. Ausgehend von einem Anfrageknoten liegt das Kriterium für die Unterscheidbarkeit von Experten in der restriktiven Verarbeitung lokaler Information. Diese neue Heuristik wird als 'Graph Shell Attention' (SEA) bezeichnet und beschreibt die Informationsverarbeitung unterschiedlicher Teilgraphen von Experten unter der Verwendung der Transformer-technologie.
Eine zuverlässige Weiterleitung von Informationen über größere Kommunikationsnetzwerken, sozialen Netzwerken oder Sensorennetzwerken spielen eine wichtige Rolle in Anwendungen der Marktanalyse, der Analyse eines sozialen Gefüges, oder der Überwachung der physischen und umweltorientierten Bedingungen. Innerhalb dieser Anwendungen können Fälle auftreten, wo Freundschaftsbeziehungen nicht mehr aktuell sind, wo die Kommunikation zweier Endpunkte zusammenbricht, welches mittels einer Unsicherheit des Informationsaustausches zweier Endpunkte ausgedrückt werden kann. Diese Arbeit untersucht die Optimierung des Informationsflusses in Netzwerken, deren Verbindungen unsicher sind, hinsichtlich der Bedingung, dass nur ein Bruchteil der möglichen Kanten für den Informationsaustausch benutzt werden dürfen. Eine eigens entwickelte Datenstruktur - der F-Baum - wird eingeführt, die 2 NP-harte Teilprobleme auf einmal adressiert: zum einen die Berechnung des erwartbaren Informationsflusses und zum anderen die Auswahl der optimalen Kanten. Der F-Baum unterscheidet hierbei unabhängige Zusammenhangskomponenten der wahrscheinlichkeitsbasierten Eingabedaten, deren Informationsfluss entweder analytisch korrekt und effizient berechnet werden können, oder lokal über traditionelle Monte-Carlo sampling approximiert werden können.
Der darauffolgende Abschnitt dieser Arbeit befasst sich mit einem Graphproblem aus Sicht der Optimierungsforschung angewandter Mathematik. Es wird eine neue Variante der Tourenplanung vorgestellt, welches neben kundenspezifischer Zeitfenster auch flexible Zustellstandorte beinhaltet. Darüber hinaus obliegt den Zielorten, an denen Kunden bedient werden können, weiteren Kapazitätslimitierungen. Aus praktischer Sicht ist das VRPTW-FL (engl.: "Vehicle Routing Problem with Time Windows and Flexible Locations") eine bedeutende Problemstellung für Paketdienstleister, Routenplanung mit eingeschränkten Stellplätzen oder auch für die praktische Planung der Arbeitsaufteilung von behandelnden Therapeuten/-innen und Ärzten/-innen in einem Krankenhaus. In dieser Arbeit wird für die Bewältigung dieser Problemstellung eine Metaheuristik vorgestellt, die einen hybriden Ansatz mit der sogenannten Adaptive Large Neighborhood Search (ALNS) impliziert. Darüber hinaus wird als Konstruktionsheuristik ein 'Backtracking'-Mechanismus (dt.: Rückverfolgung) angewandt, um initiale Startlösungen aus dem Lösungssuchraum auszuschließen, die weniger vielversprechend sind. In der Evaluierung dieses neuen Ansatz werden Krankenhausdaten untersucht, um auch die Nützlichkeit von flexiblen Zielorten unter verschiedenen Kostenfunktionen herauszuarbeiten.
Im letzten Kapitel dieser Dissertation werden Trends in sozialen Daten analysiert, die Auskunft über die Stimmung der Benutzer liefern, sowie Einblicke in tagesaktuelle Geschehnisse gewähren. Ein Kennzeichen solcher Trends liegt in dem Aufbraußen von inhaltsspezifischen Themen innerhalb eines Zeitfensters, die von der durchschnittlichen Erscheinungshäufigkeit desselben Themas signifikant abweichen. Die Untersuchung der Verbreitung solches Trends über die zeitliche und örtliche Dimension erlaubt es, Trends in Archetypen zu klassifizieren, um somit die Ausbreitung zukünftiger Trends hervorzusagen.
Mit der immerwährenden Skalierung von Graphdaten und deren Komplexität, und den Fortschritten innerhalb der künstlichen Intelligenz, wird das maschinelle Lernen unweigerlich weiterhin eine wesentliche Rolle spielen, um Graphdaten zu modellieren, analysieren und schlussendlich die Wissensextraktion aus derartigen Daten maßgeblich zu fördern.La théorie des graphes s'est révélée être une langue universel pour décrire les systèmes complexes modernes. L'élégant cadre théorique des graphes a attiré l'attention des chercheurs pendant des décennies. Par conséquent, les graphes sont devenus une structure de données omniprésente dans diverses applications où une caractéristique relationnelle est évidente. Les applications basées sur les graphes se retrouvent, par exemple, dans l'analyse des réseaux sociaux, les réseaux de télécommunication, les processus logistiques, les systèmes de recommandation, la modélisation des interactions cinétiques dans les réseaux de protéines, ou l'"Internet des objets" (IoT) où la modélisation de milliards de dispositifs interconnectés basés sur le web est d'une importance capitale.
Cette thèse se penche sur les défis posés par les applications modernes des graphes. Elle propose un modèle de regroupement spectral robuste et accéléré dans les graphes homogènes et de nouveaux modèles d'enveloppe de graphe pilotés par transformateur pour les graphes attribués.
Une nouvelle structure de données est introduite pour les graphes probabilistes afin de calculer efficacement le flux d'informations. De plus, un algorithme métaheuristique est conçu pour trouver une bonne solution à un problème d'optimisation composé d'un problème étendu de routage de véhicules. La thèse se termine par une analyse des flux de tendances dans les données des médias sociaux.
La détection de communautés au sein d'un graphe est une tâche fondamentale d'exploration de données qui présente un intérêt dans pratiquement tous les domaines et sert également d'étape de prétraitement non supervisé pour de nombreuses tâches en aval. L'une des méthodes de regroupement les mieux établies est le regroupement spectral. Cependant, le regroupement spectral standard est très sensible aux données d'entrée bruitées, et l'eigendecomposition a une complexité d'exécution cubique élevée O(n^3). S'attaquer à l'un de ces problèmes exacerbe souvent l'autre. Cette thèse présente un nouveau modèle qui accélère l'étape d'eigendecomposition en la remplaçant par une approximation de Nyström. La robustesse est obtenue en séparant itérativement les données en une partie nettoyée et une partie bruyante. Dans ce processus, la représentation des données d'entrée sous forme de graphe est essentielle pour identifier les parties des données qui sont bien connectées en analysant les distances des sommets dans l'espace propre.
Avec les progrès des architectures de Deep Learning, nous observons également une poussée de la recherche sur l'apprentissage de la représentation graphique.
Le paradigme du passage de messages dans les réseaux neuronaux graphiques (GNN) formalise une heuristique prédominante pour les données graphiques multi-relationnelles et attribuées afin d'apprendre les représentations des nœuds. Dans les applications en aval, nous pouvons utiliser les représentations pour résoudre des problèmes théoriques tels que la classification des nœuds, la classification/régression des graphes et la prédiction des relations. Cependant, un problème courant dans les GNN est connu sous le nom de lissage excessif. En augmentant le nombre d'itérations dans le passage de messages, les représentations des nœuds du graphe d'entrée s'alignent et deviennent indiscernables.
Cette thèse montre un moyen efficace d'assouplir l'architecture GNN en employant une heuristique de routage dans le flux de travail général. Plus précisément, une couche supplémentaire achemine les représentations des nœuds vers des experts spécialisés. Chaque expert calcule les représentations en fonction de son flux de travail GNN respectif. Les définitions de GNN distincts résultent de k vues localisées à partir d'un nœud central. Cette procédure est appelée Graph Shell Attention (SEA), dans laquelle les experts traitent différents sous-graphes à l'aide d'un transformateur.
La propagation fiable d'informations par le biais de grands réseaux de communication, de réseaux sociaux ou de réseaux de capteurs est importante pour les applications concernant le marketing, l'analyse sociale ou la surveillance des conditions physiques ou environnementales. Cependant, les liens sociaux d'amitié peuvent être obsolètes, et les liens de communication peuvent échouer, induisant la notion d'incertitude dans de tels réseaux. Cette thèse aborde le problème de l'optimisation de la propagation de l'information dans les réseaux incertains compte tenu d'un budget contraint d'arêtes.
Une structure de données spécialisée, appelée F-tree, traite deux sous-problèmes NP-hard: le calcul du flux d'information attendu et le choix optimal des arêtes. L'arbre F identifie les composants indépendants d'un graphe d'entrée probabiliste pour lesquels le flux d'informations peut être calculé analytiquement et efficacement ou pour lesquels l'échantillonnage Monte-Carlo traditionnel peut être appliqué indépendamment du reste du réseau.
La partie suivante de la thèse couvre un problème de graphe du point de vue de la recherche opérationnelle. Une nouvelle variante du célèbre problème d'acheminement par véhicule (VRP) est introduite, où les clients sont servis dans une fenêtre temporelle spécifique (TW), ainsi que des lieux de livraison flexibles (FL) incluant des contraintes de capacité. Ces dernières impliquent que chaque client est programmé dans l'un des emplacements de service de livraison à capacité. En pratique, le problème VRPTW-FL est pertinent pour des applications de livraison de colis, d'acheminement avec un espace de stationnement limité ou, par exemple, dans le cadre de la programmation de kinésithérapeutes à l'échelle d'un hôpital. Cette thèse présente une métaheuristique construite sur une recherche hybride de grands voisinages adaptatifs (ALNS). En outre, un mécanisme de retour en arrière dans la phase de construction est introduit pour modifier les décisions insatisfaisantes à des stades précoces. Dans l'étude computationnelle, des données hospitalières sont utilisées pour évaluer l'utilité de lieux de livraison flexibles et de diverses fonctions de coût.
Dans la dernière partie de la thèse, les tendances des médias sociaux sont analysées, ce qui donne un aperçu du sentiment des utilisateurs et des sujets d'actualité. Ces tendances consistent en des rafales de messages concernant un sujet particulier dans un laps de temps donné, s'écartant de manière significative de la fréquence moyenne d'apparition du même sujet. Cette thèse présente une méthode de classification des archétypes de tendances afin de prédire leur diffusion future en étudiant la diffusion de ces tendances dans l'espace et dans le temps.
D'une manière générale, avec l'augmentation constante de l'échelle et de la complexité des ensembles de données structurées en graphe et les progrès de l'intelligence artificielle, les modèles soutenus par l'IA joueront inévitablement un rôle important dans l'analyse, la modélisation et l'amélioration de l'extraction de connaissances à partir de données en graphe
Der Einfluss allostatischer Last auf die Regulation der innaten und adaptiven Immunantwort beim Menschen
Get PDF
Merging, fragmentation and collapse of interstellar filaments
Get PDFSterne haben die Menschen schon seit jeher fasziniert und Beobachtungen zeigten bereits vor Jahrzehnten, dass leichte Sterne filamentartigen Strukturen entspringen. Dennoch ist der Entstehungsprozess dieser Filamente sowie deren Entwicklung und Fragmentierung in einzelne Kerne bislang nicht hinreichend verstanden. Wie ich in der vorliegenden Arbeit, die neue Erkenntnisse zur Dynamik, Fragmentierung und zum Kollaps von Filamenten ermöglicht, zeige, spielt das Aufstellen, Verstehen und Vergleichen von Zeitskalen hierbei eine wesentliche Rolle.
Von zentraler Bedeutung hierbei ist die Zeitskala, auf der Filamente kollabieren, denn diese bestimmt ihre Lebensdauer und somit den zeitlichen Rahmen in dem physikalische Prozesse innerhalb des Filaments ablaufen können. Da es keine hydrostatische Lösung entlang der Hauptachse eines Filaments gibt, sind diese nicht stabil. Aus theoretischer Sicht müssen somit alle Filamente einem longitudinalen Kollaps unterliegen, wobei sich durch das Profil der Beschleunigung eine Verdichtung an jedem Ende des Filaments bildet. Dies ist der sogenannte „Edge Effect“. Die vorliegende Arbeit zeigt, dass der Filament-Kollaps in einem zweistufigen Prozess abläuft. Die erste Phase ist dominiert durch Eigengravitation, die zu einem beschleunigten Kollaps führt. In der zweiten Phase erfährt die Verdichtung am Ende des Filaments einen Staudruck durch das Material im Inneren des Filaments, was zu einer gleichförmigen Bewegung führt. Ausgehend von diesen Erkenntnissen lässt sich der Kollaps analytisch beschreiben und eine Kollapszeit berechnen, welche mit empirischen Betrachtungen übereinstimmt.
Unsere Studien zeigen, dass die Zeitskala, auf denen Filamente kollabieren, und somit auch der Edge Effect stark vom Dichtegradienten in der Endregion abhängt. Auch wenn er den Kollaps nicht aufhalten kann, so kann er diesen verlangsamen. Wird der Kollaps hinreichend verlangsamt, können Störungen schneller anwachsen, was zur Fragmentation entlang des Filaments führt. Das erklärt, weshalb der Edge Effect seltener beobachtet wird, als bisher theoretisch erwartet. Auf Basis unserer Ergebnisse ist zu erwarten, dass die meisten Filamente Dichtegradienten am Ende besitzen, die größer sind als der kritische Gradient, bei dem der Edge Effect und das Anwachsen der Störungen gleich schnell sind.
Eine Verlangsamung des Filament Kollaps ermöglicht den Ablauf von Prozessen, welche auf ähnlichen Zeitskalen stattfinden, wie zum Beispiel das Verschmelzen von Filamenten. Ich zeige in dieser Arbeit, dass es ohne die Verlangsamung des Kollapses bestimmte Rahmenbedingungen braucht, unter denen eine Verschmelzung überhaupt möglich ist. Die notwendigen Grenzwerte verschieben sich durch die Verlangsamung und machen eine Verschmelzung deutlich wahrscheinlicher. Durch die Verschmelzung unterliegen Filamente einer langanhaltenden Oszillation, die auch in der Geschwindigkeitsdispersion und der Säulendichte beobachtbar ist. In beispielhaften Filamenten der Orion-Region haben wir Hinweise auf ähnliche Strukturen gefunden.
Schlussendlich gebe ich noch einen Ausblick, wie maschinelles Lernen Simulationen von Filamenten beschleunigen kann. Wir haben ein Netzwerk entwickelt, das die Abschwächungskoeffizienten von interstellarer ultravioletter Strahlung bei bekannter Dichteverteilung bestimmt, was rechnerisch deutlich effizienter ist als herkömmliche Methoden. Große Strukturen werden gut reproduziert, jedoch ist die Reproduktion von kleinen und dichten Strukturen noch nicht hinreichend akkurat.Stars have always fascinated people and already decades ago observations showed that low-mass stars originate from filamentary structures. Nevertheless, the formation process of these filaments, as well as their evolution and fragmentation into individual cores, is not yet sufficiently understood. As I will show in this thesis, which provides new insights into the dynamics, fragmentation and collapse of filaments, determining, understanding and comparing timescales plays a crucial role, in this regard.
The timescale on which filaments collapse is of key importance because it determines their lifetime and therefore the timeframe in which physical processes can take place within the filament. Since there is no hydrostatic solution, filaments are not stable along their main axis. From a theoretical point of view, all filaments must therefore collapse in longitudinal direction with a compression forming at each end of the filament due to the profile of the acceleration. This is the so-called ‘edge effect’. The present thesis demonstrates that the filament collapse is a two-phase process. The first phase is dominated by the self-gravity of the filament, leading to an accelerated collapse. In the second phase, the condensations at the end of the filament experience the ram pressure of the material inside the filament, leading to a uniform movement. With these findings, the collapse can be described analytically and a collapse timescale can be determined which agrees well with empirical results.
Our studies show that the timescale on which filaments collapse, and therefore also the edge effect, strongly depends on the density gradient in the end region. Although a density gradient cannot stop the edge effect, it can slow it down. If the slow-down is sufficiently large, perturbations can grow faster than the edge, leading to fragmentation along the filament. This explains why the edge effect is observed less than theoretically expected. Our results suggest that most of the filaments are required to have density gradients shallower than the critical gradient, for which the edge effect and the perturbations grow on the same timescale.
The slow down of the filament collapse allows processes to occur that happen on similar timescales as, for example, filament mergers. In this work, I show that without slowing down the collapse, special initial conditions have to be met in order to make filament mergers possible. The necessary thresholds are shifted due to the slow-down, making a filament merger much more probable. The merger induces long-lived oscillations which can be observed in velocity dispersion and column density. We found evidence of similar signatures in exemplary filaments in the Orion region.
Finally, I will give an outlook on how machine learning can speed up simulations of filaments. We developed a network that predicts attenuation coefficients of interstellar ultraviolet radiation given a certain density distribution and which is computationally much more efficient than traditional methods. The overall structure is well reproduced, whereas the determination of small and dense features needs further improvement