Evolutionstheorien für natürliche und technische Netzwerke

Im Rahmen des DFG-Schwerpunktprogramm 1126: "Algorithmik großer und komplexer Netzwerke" haben wir uns mit den folgenden Projekten beschäftigt:

Im Rahmen des DFG-Schwerpunktes 1126 "Algorithmik großer und komplexer Netzwerke" beschäftigen wir uns mit der Frage, wie sich dynamische Netzwerke entwickeln. Dazu haben wir verschiedene Evolutionsmodelle entwickelt, die die Evolution von Netzwerken beschreiben. Die Modelle sind so entworfen, dass sie zu einem steady state führen, der bezüglich seiner Eigenschaften analysiert werden kann. Wir haben für die folgenden Szenarien Netzwerkmodelle entwickelt, die die Evolution der angegebenen Netzwerke formal und analysierbar beschreiben:

• 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.

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).

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.

Im Rahmen der bisher vorgestellten Projekte haben wir uns intensiv mit Zentralitätsmaßen beschäftigt, die die Knoten eines Netzwerkes danach klassifizieren, wie zentral sie für das Netzwerk sind. Umgekehrt ist es für manche Applikationen auch interessant herauszufinden, welche Knoten eher peripher sind. In einer Zusammenarbeit mit Sandor Fekete, Alexander Kröller und Dennis Pfisterer (Projekt im Rahmen des Schwerpunktprogrammes: Algorithmen und Protokolle für dezentrale Vernetzung und Betrieb großer Ad-hoc-Netzwerke ohne den Gebrauch von Lokalisierungshardware ) haben wir darum ein Maß entwickelt, dass die Knoten am Rande eines Netzwerkes identifiziert.

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.