Informationsmaße zur Charakterisierung von Netzwerken

Für die Modellierung von komplexen realen Systemen sind netzwerk-basierte Ansätze zur Zeit allgegenwärtig. Da sich herausgestellt hat das komplexe Netzwerke oft charakteristische Strukturmuster aufweisen, sind nicht nur reine Zufallsgraphenmodelle für die Modellierung solcher Systeme von Bedeutung. Weiter folgt daraus das Methoden zur strukturellen Analyse von Netzwerken eine große Wichtigkeit besitzen. Der Schwerpunkt dieses Forschungsantrags liegt auf der Charakterisierung von Graphen. Allgemein wird darunter die Beschreibung der strukturellen Graphkomplexität auf Basis bestimmter Eigenschaften oder graphen-theoretischer Maße verstanden. Eine Möglichkeit zur Graph-Charakterisierung besteht in der Anwendung von Shannon-Informationsmaßen, wobei zunächst eine Wahrscheinlichkeitsverteilung basierend auf strukturellen Grapheigenschaften inferiert wird. Solche Informationsmaße für Netzwerke charakterisieren die Graphtopologie als strukturellen Informationsinhalt welche auch oft als Komplexitätsmaße für Graphen interpretiert werden. Jedoch wirkt sich die ungünstige Berechnungskomplexität einiger klassischer Informationsmaße oft negativ auf die Realisierung potentieller Anwendungen aus. Abgesehen von der Herausforderung effiziente Maße zu entwickeln, besteht ein großes Interesse mathematische Eigenschaften und Beziehungen solcher Komplexitätsmaße zu untersuchen. Bezüglich der bekannten Informationsmaße, die oft in der mathematischen Chemie zur Charakterisierung chemischer Strukturen eingesetzt werden, sind solche Eigenschaften noch fast gänzlich unbekannt. Das geplante Forschungsprojekt verfolgt zwei wesentliche Ziele: Zunächst sollen mathematische Eigenschaften von netzwerk-basierten Informationsmaßen untersucht werden. Die Resultate werden dann verwendet um bestehende Anwendungen zur Untersuchung von Beziehungen zwischen einer charakteristischen Eigenschaft einer Substanz mit seiner chemischen Struktur zu verbessern. Hierbei liegt das Hauptziel in der Anwendung neuer und bekannter Informationsmaße auf große Datenbanken um chemische Strukturen aussagekräftig zu charakterisieren.

Dieses Projekt behandelt die strukturelle Netzwerk-Charakterisierung mit informations-theoretischen Maßen. Quantitative Netzwerk-Charakterisierung kann generell als das Problem der Ableitung charakteristischer (struktureller) Eigenschaften verstanden werden. In unserem Fall verwendeten wir entropische Maße wie verschiedene Graph-Entropien. Unter Verwendung von informations-theoretischen Methoden erhält man eine Wahrscheinlichkeitsverteilung für die Struktur eines Netzwerks. Eine immer noch eine komplizierte Frage ist, welche Art von struktureller Komplexität ein gegebenes Maß erfasst. Dieses Projekt hatte zwei wesentliche Ziele: Erstens die Erforschung des mathematischen Apparates und zweitens, (idealerweise) diese Ergebnisse in der Chemieinformatik und für QSPR (Quantitative Struktur-Eigenschafts Beziehungen) anzuwenden.Der erste Teil befasste sich mit dem Beweisen neuer Beziehungen zwischen informations-theoretischen Maßen. Da sehr viele Maße entwickelt worden sind, ist diese Fragestellung nicht trivial. Es wurde auch ein Framework für probabilistische Ungleichungen (für Graphen) entwickelt, welches faszinierende Ergebnisse brachte. Zusätzlich wurden extremale Eigenschaften von informations-theoretischen Graph-Maßen untersucht was sehr schwierig war. Zusammengefasst haben wir neue Erkenntnisse für die Bestimmung der strukturellen Komplexität von Graphen erhalten. Das Problem ist für viele Anwendungsgebiete (z.B. Internet, Biologie, Chemie, etc.) relevant.Ein weiteres Problem in diesem Projekt betraf die Eindeutigkeit dieser informations-theoretischen Graph-Maße. Mit anderen Worten erforschten wir die Fähigkeit der Maße um Graphen strukturell zu unterscheiden. Das Ergebnis ist, dass die meisten bekannten Maße nicht eindeutig auf erschöpfend generierten Graphen sind. Einige waren jedoch hoch diskriminierend. Diese Erkenntnis kann verwendet werden um Graph-Isomorphie zu bestimmen oder eindeutige Fingerprints von Graphen zu erstellen. Zusammengefasst haben die Ergebnisse signifikant dazu beigetragen haben, eine Informationstheorie für Netzwerke zu entwickeln.Die erzielten Ergebnisse verwendeten wir um die Maße für die Anwendung in der Chemoinformatik und Chemometrik zu untersuchen. Wir fanden interessante und wichtige Eigenschaften von Deskriptoren, welche dazu verwendet werden können um effizientere Anwendungen in den genannten Gebieten zu designen. Eine wichtige Entdeckung ist, dass die meisten der verfügbaren molekularen Deskriptoren (insb. strukturelle Deskriptoren) strukturelle Information sehr ähnlich abbilden und damit überflüssig sein könnten. Dieses Ergebnis brachte die Frage auf, wie nützlich molekulare Deskriptoren sind.