Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Schnelles Zeichnen von komplexen Beziehungen

24.09.2015

Ob im Liniennetzplan von Verkehrsunternehmen, bei der Routenplanung im Auto oder bei der Dynamik von Freundschaftsbeziehungen in sozialen Netzwerken: Detailreiche Informationen können vom Menschen am besten visuell erfasst werden. Doch damit entsprechende Graphen gut lesbar sind, müssen Computer ein gutes Layout – also eine optimale Positionierung aller Knotenpunkte und Verbindungen berechnen. Bei großem Detailreichtum ist dafür eine enorme Rechenleistung notwendig. Um diesen Zeichenprozess zu beschleunigen, haben Informatiker des Karlsruher Instituts für Technologie das Graphzeichnungstool „KaDraw“ entwickelt, welches ab sofort unter einer General Public License zum Download bereitsteht.

Die Qualitätskriterien für eine lesbare grafische Darstellung komplexer Beziehungen sind hoch. Beispielsweise müssen die Knotenpunkte weit genug auseinander liegen, um als solche erfasst werden zu können. Gleichzeitig muss das Graphzeichnungstool alle Kanten so anordnen, dass sie für den Betrachter erkennbar bleiben und nicht willkürlich übereinander liegen.


KaDraw zeichnet komplexe Graphen effizienter und optimiert deren Darstellung.

Grafik: Dr. Christian Schulz, KIT

Alle zu beachtenden Kriterien werden deshalb in einer Zielfunktion formuliert. Um diese zu optimieren und gleichzeitig die Effizienz bei der Berechnung zu steigern, hat das Team um Christian Schulz, Henning Meyerhenke und Martin Nöllenburg vom Institut für Theoretische Informatik am KIT das Graphzeichnungstool „KaDraw“ entwickelt.

Bei „KaDraw“ kommen zwei Methoden zum Einsatz. Zum einen bedient man sich der Parallelisierung durch Nutzung von Mehrkernprozessoren. So kann die Rechenleistung gesteigert werden, indem die Rechenlast auf mehrere Prozessorkerne verteilt wird. Zum anderen werden innovative Algorithmen verwendet. Diese Algorithmen erzeugen aus dem komplexen Eingabegraphen zunächst eine Hierarchie von immer kleiner werdenden Graphen.

Um eine gute Darstellung des Eingabegraphen zu erhalten, wird zunächst der kleinste Graph gezeichnet. Die Zeichnung wird danach stückweise auf die größeren Graphen übertragen und auf jedem größeren Level verbessert. „Mit dieser Methode können wir den Zeichenvorgang um ein Vielfaches beschleunigen. KaDraw kann Graphen etwa 30 Mal schneller zeichnen als vorherige Werkzeuge. Dabei bleibt die Qualität des Ergebnisses immer noch vergleichbar“, berichtet Christian Schulz.

Doch nicht nur statische Graphen können durch „KaDraw“ schneller gezeichnet werden. Auch dynamische Graphen, also Graphen, deren Beziehungen sich im Laufe der Zeit verändern, können mit dem Karlsruher System deutlich effizienter bearbeitet werden. Ein Beispiel für dynamische Graphen sind die Freundschaftsbeziehungen in sozialen Netzwerken. Diese unterliegen - etwa durch hinzukommende Freundschaften - einer stetigen Veränderung. „Bei dynamischen Graphen kann man eine bereits vorhandene Zeichnung in unser System eingeben und daraus ein neues Layout mit neuen Beziehungen zeichnen lassen“, erklärt Henning Meyerhenke.

Freie Software

Als Nächstes möchten die Wissenschaftler ein noch effizienteres Verfahren entwickeln. „Durch Verbesserung der algorithmischen Komplexität möchten wir die Effizienz des Verfahrens noch weiter steigern“, sagt Martin Nöllenburg. Doch bevor man sich den neuen Aufgaben widmet, wird „KaDraw“ der Öffentlichkeit zur Verfügung gestellt. Ab sofort steht das Graphenzeichnungstool unter einer General Public License (GPL) zur Verfügung. Zeitgleich präsentieren die Wissenschaftler ihr Tool auf der Fachtagung „Graph Drawing and Network Visualization“.

Link zum Download von KaDraw: http://algo2.iti.kit.edu/kadraw/

Weiterer Kontakt: Nils Ehrenberg, Pressereferent, Tel.: +49 721 608-48122, Fax: +49 721 608-43658, E-Mail: nils.ehrenberg@kit.edu

Das Karlsruher Institut für Technologie (KIT) vereint als selbstständige Körperschaft des öffentlichen Rechts die Aufgaben einer Universität des Landes Baden-Württemberg und eines nationalen Forschungszentrums in der Helmholtz-Gemeinschaft. Seine Kernaufgaben Forschung, Lehre und Innovation verbindet das KIT zu einer Mission. Mit rund 9 400 Mitarbeiterinnen und Mitarbeitern sowie 24 500 Studierenden ist das KIT eine der großen natur- und ingenieurwissenschaftlichen Forschungs- und Lehreinrichtungen Europas.

Das KIT ist seit 2010 als familiengerechte Hochschule zertifiziert.

Diese Presseinformation ist im Internet abrufbar unter: www.kit.edu

Das Foto steht in druckfähiger Qualität auf www.kit.edu zum Download bereit und kann angefordert werden unter: presse@kit.edu oder +49 721 608-47414. Die Verwendung des Bildes ist ausschließlich in dem oben genannten Zusammenhang gestattet.

Weitere Informationen:

http://www.kit.edu/kit/pi_2015_109_schnelles-zeichnen-von-komplexen-beziehungen....

Monika Landgraf | Karlsruher Institut für Technologie

Weitere Nachrichten aus der Kategorie Informationstechnologie:

nachricht Schnelle Time-to-Market durch standardisierte Datacenter-Container
28.03.2017 | Rittal GmbH & Co. KG

nachricht Modellfabrik Industrie 4.0: Forschungs- und Trainingsplattform für Wissenschaft und Wirtschaft
28.03.2017 | Hochschule Konstanz

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Entwicklung miniaturisierter Lichtmikroskope - „ChipScope“ will ins Innere lebender Zellen blicken

Das Institut für Halbleitertechnik und das Institut für Physikalische und Theoretische Chemie, beide Mitglieder des Laboratory for Emerging Nanometrology (LENA), der Technischen Universität Braunschweig, sind Partner des kürzlich gestarteten EU-Forschungsprojektes ChipScope. Ziel ist es, ein neues, extrem kleines Lichtmikroskop zu entwickeln. Damit soll das Innere lebender Zellen in Echtzeit beobachtet werden können. Sieben Institute in fünf europäischen Ländern beteiligen sich über die nächsten vier Jahre an diesem technologisch anspruchsvollen Projekt.

Die zukünftigen Einsatzmöglichkeiten des neu zu entwickelnden und nur wenige Millimeter großen Mikroskops sind äußerst vielfältig. Die Projektpartner haben...

Im Focus: A Challenging European Research Project to Develop New Tiny Microscopes

The Institute of Semiconductor Technology and the Institute of Physical and Theoretical Chemistry, both members of the Laboratory for Emerging Nanometrology (LENA), at Technische Universität Braunschweig are partners in a new European research project entitled ChipScope, which aims to develop a completely new and extremely small optical microscope capable of observing the interior of living cells in real time. A consortium of 7 partners from 5 countries will tackle this issue with very ambitious objectives during a four-year research program.

To demonstrate the usefulness of this new scientific tool, at the end of the project the developed chip-sized microscope will be used to observe in real-time...

Im Focus: Das anwachsende Ende der Ordnung

Physiker aus Konstanz weisen sogenannte Mermin-Wagner-Fluktuationen experimentell nach

Ein Kristall besteht aus perfekt angeordneten Teilchen, aus einer lückenlos symmetrischen Atomstruktur – dies besagt die klassische Definition aus der Physik....

Im Focus: Wegweisende Erkenntnisse für die Biomedizin: NAD⁺ hilft bei Reparatur geschädigter Erbinformationen

Eine internationale Forschergruppe mit dem Bayreuther Biochemiker Prof. Dr. Clemens Steegborn präsentiert in 'Science' neue, für die Biomedizin wegweisende Forschungsergebnisse zur Rolle des Moleküls NAD⁺ bei der Korrektur von Schäden am Erbgut.

Die Zellen von Menschen und Tieren können Schäden an der DNA, dem Träger der Erbinformation, bis zu einem gewissen Umfang selbst reparieren. Diese Fähigkeit...

Im Focus: Designer-Proteine falten DNA

Florian Praetorius und Prof. Hendrik Dietz von der Technischen Universität München (TUM) haben eine neue Methode entwickelt, mit deren Hilfe sie definierte Hybrid-Strukturen aus DNA und Proteinen aufbauen können. Die Methode eröffnet Möglichkeiten für die zellbiologische Grundlagenforschung und für die Anwendung in Medizin und Biotechnologie.

Desoxyribonukleinsäure – besser bekannt unter der englischen Abkürzung DNA – ist die Trägerin unserer Erbinformation. Für Prof. Hendrik Dietz und Florian...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Industriearbeitskreis »Prozesskontrolle in der Lasermaterialbearbeitung ICPC« lädt nach Aachen ein

28.03.2017 | Veranstaltungen

Neue Methoden für zuverlässige Mikroelektronik: Internationale Experten treffen sich in Halle

28.03.2017 | Veranstaltungen

Wie Menschen wachsen

27.03.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

Von Agenten, Algorithmen und unbeliebten Wochentagen

28.03.2017 | Unternehmensmeldung

Hannover Messe: Elektrische Maschinen in neuen Dimensionen

28.03.2017 | HANNOVER MESSE

Dimethylfumarat – eine neue Behandlungsoption für Lymphome

28.03.2017 | Medizin Gesundheit