Maße basierend auf Graphautomorphismen

Die quantitative Netzwerkanalyse (oder Quantitative Graphentheorie) ist ein neuer Zweig der klassischen Graphentheorie. Anstatt Graphen nur auf Basis struktureller Eigenschaften zu beschreiben, zielt die quantitative Analyse auf die Quantifizierung struktureller Information ab. Die Methoden zur quantitativen Graphanalyse können in zwei Kategorien eingeteilt werden: Methoden zum Graphvergleich (Ähnlichkeit/Distanz) oder quantitative Maße zur numerischen Charakterisierung von Graphen. Letztere Klasse von Maßen ist bereits intensiv in Disziplinen wie z.B. Chemieinformatik, Chemometrik, Bioinformatik, Systembiologie usw. angewendet worden. Solche Maße sind bereits intensiv erforscht worden. Zum Beispiel basieren solche Maße oft auf der Shannon-entropie, auf Distanzen in Graphen, Knotengrade usw. Jedoch sind Maße basierend auf Graphautomorphismen noch nicht intensiv untersucht worden. Ein wesentlicher Grund könnte die oft ungünstige Zeitkomplexität der zu Grunde liegenden Algorithmen sein. In diesem Projekt definieren und untersuchen wir neue quantitative Maße basierend auf der Automorphismengruppe von (chemischen) Graphen. Um diese Maße numerisch zu berechnen benutzen wir die effiziente Software SubMat. Weiter beweisen wir Schranken um die Größe von Orbits und letztlich der Automorphismengruppe effizient abzuschätzen. Dieses Projekt verfolgt zwei wesentliche Ziele: Erstens erforschen wir mathematische Eigenschaften von automorphismus-basierten Graphmaßen. Zweitens werden wir die mathematischen Resultate anwenden, um deren Benutzung und Wirkung innerhalb der Chemieinformatik anzustreben. Speziell wenden wir die erwähnten Graphmaße an, um markierte chemische Graphen zu untersuchen. Wir stellen nochmals klar, dass in diesem Projekt das Clustering von molekularen Strukturen auf Basis von automorphismus-basierten Graphmaßen eines der anwendungsorientierten Teilprobleme des zweiten Teil des Projekts ist. Idealerweise erhalten wir neue Anwendungen in der Chemieinformatik aber das grundlegende Ziel ist ein besseres Verständnis der neuen Maße im Sinne der Grundlagenforschung.

Die Quantitative Graphentheorie ist ein neuer Zweig der klassischen Graphentheorie. Anstatt Graphen nur auf Basis struktureller Eigenschaften zu beschreiben, zielt die quantitative Analyse auf die Quantifizierung struktureller Information ab. Die Methoden zur quantitativen Graphanalyse können in zwei Kategorien eingeteilt werden: Methoden zum Graphvergleich (Ähnlichkeit/Distanz) oder quantitative Maße zur numerischen Charakterisierung von Graphen. Letztere Klasse von Maßen ist bereits intensiv in Disziplinen wie z.B. Chemieinformatik, Chemometrik, Bioinformatik, Systembiologie usw. angewendet worden. Diese Maße sind bereits allgemein und im Rahmen des Projekts intensiv erforscht worden. Zum Beispiel basieren solche Maße oft auf der Shannon-entropie, auf Distanzen in Graphen, Knotengrade usw. Jedoch sind Maße basierend auf Graphautomorphismen noch nicht intensiv untersucht worden. Ein wesentlicher Grund könnte die oft ungünstige Zeitkomplexität der zu Grunde liegenden Algorithmen sein. In diesem Projekt untersuchten wir neue quantitative Maße basierend auf der Automorphismengruppe von Graphen. Die Resultate sind zum einen analytischer Natur und zum einem haben wir auch computationale Resulte erzielt. Dieses Projekt verfolgte zwei wesentliche Ziele: Erstens erforschrten wir mathematische Eigenschaften von automorphismus-basierten Graphmaßen. Zweitens erzielten wir mathematische Resultate, um deren Benutzung und Wirkung innerhalb der Chemieinformatik anzustreben. Die Forschung in diesem Projekt konnte genutzt werden, um neue Anwendungen in der Chemieinformatik und ein besseres Verständnis von symmetie-basierten Maße im Sinne der Grundlagenforschung zu erlangen.