Evolutionstheorien für natürliche und technische Netzwerke

Modelle für die Evolution von Netzwerken

1. Metabolisches Netzwerk von E. coli

• Evolution von metabolischen Netzwerken. Für die Evolution von Protein-Protein-Interaktionsnetzwerken gibt es mehrere Modelle, die vor allen Dingen darauf beruhen, dass Knoten mitsamt ihren Kanten verdoppelt werden. Auch wenn die Evolution dieser Netzwerke auf denselben Grundprinzipien (DNA-Mutation) beruht wie die Evolution von metabolischen Netzwerken, ist dieses Modell aus biologischen Gründen nicht auf die Evolution von letzteren übertragbar. Wir haben eine neues Evolutionsmodell entwickelt, dass auf biologischen Modellen der molekularbiologischen Evolutionstheorie beruht und die wesentlichen Charakteristika des metabolischen Netzwerkes von E. coli erzeugen kann.
• Evolution von sozialen Netzwerken (Stichwort: Small Worlds). Hier haben wir, aufbauend auf dem grundlegenden Artikel von Watts und Strogatz (Nature 393,pp. 440-442, 1998), ein generalisiertes, dynamisches Small-World-Modell entwickelt, dass auf einem dynamischen Prozess des Umziehens von einzelnen Knoten gegründet ist. Das Modell lässt sich bezüglich seiner steady state -Eigenschaften im Gegensatz zu anderen Small-World-Modellen recht leicht analysieren und könnte ein gutes Modell abgeben für die Bildung von Email-Netzwerken und dazu benutzt werden, die Verbreitung von Viren in solchen Netzwerken zu analysieren.
• Evolution von dezentralisierten, egoistischen und einmaligen Netzwerken. Für dieses spezielle Szenario haben wir ein formales Modell aufgebaut, das zu der großen Gruppe der evolutionären Algorithmen gehört. Da das formale Modell, das hier benutzt wurde, die Analyse von Laufzeiten erlaubt, ergibt sich für dieses Thema eine Kooperation mit der Arbeitsgruppe um Ingo Wegener. In den folgenden zwei Jahren wollen wir innerhalb des formalen Modells möglichst viele, effiziente Adapationsregeln entwickeln, und deren Anwendung und Analyse in dynamischen Szenarien erarbeiten.

Aufbau eines Archivierungssystems für große Graphen

2. Screenshot eines Interfaces, mit dem Graphen aus dem Archivierungssystem heruntergeladen werden können. Die Graphen werden mit einer Reihe von verschiedenen Metadaten abgespeichert, bspw. ob sie skalenfrei oder zusammenhängend sind, und umgekehrt kann in dem System auch nach allen Graphen mit diesen Eigenschaften gesucht werden.

Viele Arbeitsgruppen des Schwerpunktprogrammes haben Graphen und Graphengeneratoren erstellt, die auch für andere Teilnehmer des Schwerpunktprogrammes interessant sind und es bei gemeinsamer Nutzung ermöglichen, dass verschiedene Arbeitsgruppen auf derselben Graphenfamilie ihre Ergebnisse untereinander austauschen können. Beispiele dafür sind Verkehrsdaten (Wagner et al.), soziale und politische Netzwerke (Brandes et al.) und Amazon-Graphen (Kaufmann et al.). Um diesen Austausch zu erleichtern, wurde in unserem Arbeitsbereich von Sascha Meinert im Rahmen seiner Diplomarbeit ein System zur Archivierung und zum Austausch von großen Graphen entworfen. Dieses System wird in Kürze zur Benutzung freigegeben werden (Voraussichtliches Freigabedatum Ende Februar 2005). Für die Bedarfsanalyse, die dem Entwurf der Datenbank voranging, wurde ein Treffen mit den Arbeitsgruppen von Dorothea Wagner und Ulrik Brandes organisiert (Projekt im Rahmen des Schwerpunktprogrammes: Analyse und Visualisierung Sozialer Netzwerke).

Analyse von großen Netzwerken aus biologischen und chemischen Daten

Innerhalb unseres eigenen Institute haben sich noch zwei weitere Kooperationen ergeben, innerhalb derer wir Algorithmen für die effiziente Erkennung von Subgraphen entwickeln konnten. In einem ersten Projekt mit der Arbeitsgruppe um Kay Nieselt geht es um die Bestimmung von Cliquen in Netzwerken, die aus DNA-Sequenzvergleichen stammen. Wir konnten nachweisen, dass diese spezielle Art von Netzwerk eine Form des Intervallgraphen aus Intervallen unterschiedlicher Länge darstellt, und damit die Menge aller Cliquen in polynomieller Zeit berechenbar ist.

In einer zweiten Kooperation (mit der Arbeitsgruppe um Oliver Kohlbacher) geht es darum, Netzwerke aus chemischen Substanzen, die durch unterschiedliche Ähnlichkeitsmaße in ihrer Verwandtschaft zueinander charakterisiert werden, in geeigneter Weise und effizient zu clustern. Erste Versuche waren hier sehr ermutigend. Eine ähnliche Clusteranalyse haben wir auch für Netzwerke durchgeführt, die aus öffentlich zugänglichen Daten von Amazon.de erzeugt wurden.

Randerkennung in Unit-Disk-Graphen

3. Unit-Disk-Graph. Die Färbung gibt an, mit welcher Wahrscheinlichkeit ein Knoten am Rand liegt.

Evolutionäre Netzwerkmodelle für P2P-overlay-Netzwerke

Die oben genannten evolutionären Modelle können dafür genutzt werden, um für dezentralisierte Netzwerke, wie die meisten P2P-Netzwerke, overlay-Netzwerke zu konstruieren, die besondere Eigenschaften ausweisen. Eine Kooperation mit der Arbeitsgruppe um Klaus Wehrle hat bisher dazu geführt, dass wir für ein von Dr. Wehrle editiertes Buch die Verwendung von klassischen Netzwerkmodellen (Small-Worlds, Skalenfreie Netzwerke, Zufallsgraphen) für P2P-Netzwerke zusammengefasst haben. Weitere Forschungen werden hier zeigen, inwieweit neue Protokolle zu dynamisch und dezentral erzeugten Netzwerktopologien führen können, die für diese Netzwerke am besten geeignet sind.