Universität Tübingen | Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Forschung > Netzwerkanalyse | ||||||
|
Evolutionstheorien für natürliche und technische NetzwerkeIm Rahmen des DFG-Schwerpunktprogramm 1126: "Algorithmik großer und komplexer Netzwerke" haben wir uns mit den folgenden Projekten beschäftigt:Modelle für die Evolution von Netzwerken
Aufbau eines Archivierungssystems für große Graphen
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 DatenInnerhalb 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
Evolutionäre Netzwerkmodelle für P2P-overlay-NetzwerkeDie 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. |
||||||
Impressum
Datenschutzerklärung
![]() |