Detailseite
Projekt
Rekonstruktion und Lernen in komplexen Netzwerken
Antragsteller
Professor Dr. Amin Coja-Oghlan
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung seit 2020
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 411362735
Zahlreiche bedeutende Ergebnisse behandeln die Vorwärtsevolution von Algorithmen und Prozessen auf Netzwerken, so dass Vorhersagen zur wahrscheinlichen Evolution des Prozesses möglich sind. Das erste Beispiel einer solchen Untersuchung betrifft das Perkolationsproblem auf vollständigen Graphen, welches im Jahr 1960 von Erdős und Rényi in einer Arbeit gelöst wurde, die als Ausgangspunkt der Theorie zufälliger Graphen gilt. Weitere Beispiele sind das Studium von `rumor spreading'-Prozessen oder epidemischen Ausbreitungen. Im Vergleich ist noch relativ wenig bekannt über die zugehörigen Rekonstruktionsprobleme. Dabei ist das Ziel, ausgehend von einer Momentaufnahme des Prozesses auf dessen Anfangsbedingungen rückzuschliessen, oder auch andere wichtige Parameter des Prozesses zu schätzen. Allerdings spielen diese Rekonstruktionsprobleme eine Schlüsselrolle an der Schnittstelle der Informatik mit anderen Disziplinen wie etwa der Epidemiologie. Ein besseres Verständnis von Rekonstruktionsproblemen kann ferner zur erfolgreichen Entwicklung neuer Lernverfahren mit Hilfe der probabilistischen Methode genutzt werden. Beispiele dafür sind neue Verfahren im `group testing' oder für das `pooled data'-Problem. Dieses Projekt zielt deshalb darauf ab, das rigorose Studium von Rekonstruktions- und Lernproblemen weiterzuentwickeln. Dabei geht es neben algorithmischen auch um informationstheoretische Gesichtspunkte. In der zweiten Förderphase widmen wir uns den folgenden vier Punkten: RLCN-2.1: Lernen und Rekonstruktion mittels der probabilistischen Methode Es geht darum, Rekonstruktions- und Lernprobleme mittels geeigneter probabilistischer Konstruktionen, insbesondere mit dichten graphischen Modellen, anzugehen, und algorithmische Techniken auf Grundlage des neuen `Approximate Message Passing'-Paradigmas zu entwickeln. RLCN-2.2: räumliches Mischen, spektrale Unabhängigkeit und Algorithmen für das zufällige Erzeugen Das Ziel ist, mittels neuerer Hilfsmittel wie beispielsweise Spektralmethoden Algorithmen für zufällige Erzeugungsprobleme auf zufälligen graphischen Modellen zu entwickeln. RLCN-2.3: Metastabilität von Dynamiken auf Netzwerken Hier geht es umgekehrt darum, Hindernisse für effizentes zufälliges Erzeugen zu identifizieren. Dazu zählen beispielsweise Verengungen oder Barrieren, in denen sich Dynamiken verfangen. RLCN-2.4: `Patient zero' und Kontaktrückverfolgung. Im `patient zero'-Problem geht es darum, den Ursprung eines epidemischen Ausbruchs auf Grundlage einer Momentaufnahme zu rekonstruieren. Eine wegweisende Frage, die in neueren empirischen Studien aufgeworfen wurde, zielt darauf ab, derartige Rekonstruktionsmethoden in der Kontaktrückverfolgung einzusetzen, um epidemische Ausbrüche einzudämmen.
DFG-Verfahren
Forschungsgruppen
