Source detection in graphs

Abstract

Die Quellensuche in Graphen ist die Suche nach dem Ursprungs eines Ausbreitungsphänomens in einem Netzwerk. Die Quelle ist ein Knoten des Graphen, der vor der Suche unbekannt ist. Die Quelle könnte zum Beispiel der Ursprung einer Kontamination in einem Wasserverteilungssystem oder einem Logistiksystem für Lebensmittel sein. Ebenso kann der Ursprung einer Krankheit in einem Beförderungsnetz (Flug-, Straßen- oder Bahnverkehr, usw.) von Interesse sein. Aufgrund der Relevanz der Anwendungen wurden diese Themen von vielen Forschern aus praktischer Sicht betrachtet. Es fehlt bisher eine abstrahierende und generische mathematische Betrachtung. Die vorliegende Arbeit ist ein erster Schritt in diese Richtung. Dafür wird eine allgemeine und einfache Modellvorstellung basierend auf endlichen Graphen und einer konstanten Ausbreitungsgeschwindigkeit des Ausbreitungsphänomens angenommen. Aufbauend auf dieser Modellierung wird die Problemstellung abstrakt eingeführt. Ins- besondere wird zwischen der online und der offline Quellensuche unterschieden. Die online Quellensuche findet gleichzeitig mit dem Ausbreitungsphänomen statt und es ist möglich während der Suche weitere Daten zu sammeln. Die offline Quellensuche findet dagegen zeitlich nach dem Ausbreitungsphänomen statt und alle Daten sind zu Beginn der Suche vorhanden. Eine weitere wichtige Unterscheidung liegt in der deterministischen und der stochasti- schen Quellensuche. Die deterministische Quellensuche baut auf exakten Daten auf, während die stochastische Quellensuche zufällige Fehler in den Daten zulässt und behandelt. Der deterministische Fall ist deutlich einfacher als der stochastische und es kann daher vor der Quellensuche angeben werden, welche Daten benötigt werden, um beliebige Quellen zu finden. Hierbei spielen besonders das Konzept der metrischen Dimension eines Graphen und hier vorgestellte Erweiterungen eine Rolle. Im stochastischen Fall werden mindestens die Daten des deterministischen Falls benötigt und zusätzliche Daten, um die zufälligen Fehler durch mitteln zu verringern, sodass noch eine hinreichend gute Schätzung der Quelle erreicht wird. Hier ist es a priori nicht möglich anzugeben, welche Daten benötigt werden. Genauso kann die Quelle nicht mehr exakt gefunden sondern nur noch geschätzt werden. Für diese Aufgabe wird die lineare Regression verwendet. Über die Fehleranalyse dieser Schätzer werden Heuristiken eingeführt, die angeben, welche Daten gesammelt werden sollten. Zur Lösung des stochastischen online Quellenfindungsproblems wird ein iterativer Algorithmus vorgeschlagen. Dieser besteht aus dem linearen Regressionsschätzer und der Heuristik zur Datensammlung. In jeder Iteration wird hierbei auf Grundlage der bisherigen Daten eine Schätzung der Quelle vorgenommen. Abhängig von der Qualität dieser Schätzung werden entweder weitere Daten gesammelt und eine nächste Iteration angestoßen oder die Schätzung wird akzeptiert und der Algorithmus beendet. Da die Sammlung der Daten nur heuristisch erfolgt, können keine theoretischen Garantien bezüglich der Konvergenz eines Algorithmus basierend auf dem Schätzer und der Heuristik gegeben werden. Um die Konvergenz zu erzwingen wird eine Einschränkung für die Daten, die die Heuristik aussuchen darf, eingeführt und im Algorithmus genutzt. Die praktische Leistungsfähigkeit dieses Algorithmus wird anhand von numerischen Simulationen gezeigt. Zum einen wird der Algorithmus genutzt um in einer Simulation die Quelle von Herzrhythmusstörungen zu finden und zum anderen um auf allgemeinen Testgraphen die Quelle eines simulierten Ausbreitungsphänomens zu finden. Eine neue mathematische Theorie für die Quellensuche in Graphen wird in dieser Arbeit eingeführt. Innerhalb der Theorie wird ein Algorithmus entwickelt, der das stochastische online Quellenfindungsproblem löst. Die Konvergenz des Algorithmus wird diskutiert und seine Robustheit in numerischen Simulationen gezeigt.

Source detection in graphs refers to the search for the origin of a spreading signal in a network. The source is an unknown node in the graph, which could be the origin of contamination in a water supply network, food logistics network, or the location of a disease outbreak in a transportation network (air, road, or rail transport). While many researchers have focused on practical applications of this problem, an abstract and generic mathematical examination is lacking. This work provides a general and simple modeling of the problem based on finite graphs and constant speed of the spreading signal. The problem is defined based on this modeling, with a distinction made between offline and online source detection. Offline source detection takes place after the signal has propagated through the network and all data is available, while online source detection is conducted during the spread of the signal, and new data may be collected during the search. Another important distinction is between stochastic and deterministic source detection, where the latter is simpler and allows for determining the necessary data, to find any source, before the search. In the stochastic case, in contrast to the deterministic case, it is not possible to determine the necessary data, to find any source, a priori. In general additional data is required to reduce random errors by averaging, and the source can only be estimated, not found exactly. Linear regression is used for this task, and the error analysis of this estimator leads to heuristics for collecting necessary data. An iterative algorithm is proposed for stochastic online source detection problem, consisting of the linear regression estimator and a data collection heuristic. However, as the data is collected heuristically, there are no theoretical guarantees regarding the convergence of the algorithm. To address this, a feasibility constraint on the data is introduced to enforce convergence. The algorithm’s practical performance is demonstrated through numerical simulations on simulated cardiac tachycardia and general test graphs. Overall, this thesis presents a novel mathematical framework for general source detection in graphs, with a new solution algorithm for the stochastic online problem. The algorithm’s convergence is discussed, and its robustness is shown in numerical simulations.