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 Smart Glasses Guide: Neues Tool zur Auswahl von Datenbrillen und Anwendungen
15.10.2018 | Fraunhofer-Institut für Produktionstechnologie IPT

nachricht Einzigartige Infrastruktur für Deep Learning – DFKI erhält ersten NVIDIA DGX2 Supercomputer Europas
11.10.2018 | Deutsches Forschungszentrum für Künstliche Intelligenz GmbH, DFKI

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Größter Galaxien-Proto-Superhaufen entdeckt

Astronomen enttarnen mit dem ESO Very Large Telescope einen kosmischen Titanen, der im frühen Universum lauert

Ein Team von Astronomen unter der Leitung von Olga Cucciati vom Istituto Nazionale di Astrofisica (INAF) Bologna hat mit dem VIMOS-Instrument am Very Large...

Im Focus: Auf Wiedersehen, Silizium? Auf dem Weg zu neuen Materalien für die Elektronik

Wissenschaftler des Max-Planck-Instituts für Polymerforschung (MPI-P) in Mainz haben zusammen mit Wissenschaftlern aus Dresden, Leipzig, Sofia (Bulgarien) und Madrid (Spanien) ein neues, metall-organisches Material entwickelt, welches ähnliche Eigenschaften wie kristallines Silizium aufweist. Das mit einfachen Mitteln bei Raumtemperatur herstellbare Material könnte in Zukunft als Ersatz für konventionelle nicht-organische Materialien dienen, die in der Optoelektronik genutzt werden.

Bei der Herstellung von elektronischen Komponenten wie Solarzellen, LEDs oder Computerchips wird heutzutage vorrangig Silizium eingesetzt. Für diese...

Im Focus: Goodbye, silicon? On the way to new electronic materials with metal-organic networks

Scientists at the Max Planck Institute for Polymer Research (MPI-P) in Mainz (Germany) together with scientists from Dresden, Leipzig, Sofia (Bulgaria) and Madrid (Spain) have now developed and characterized a novel, metal-organic material which displays electrical properties mimicking those of highly crystalline silicon. The material which can easily be fabricated at room temperature could serve as a replacement for expensive conventional inorganic materials used in optoelectronics.

Silicon, a so called semiconductor, is currently widely employed for the development of components such as solar cells, LEDs or computer chips. High purity...

Im Focus: Blauer Phosphor – jetzt erstmals vermessen und kartiert

Die Existenz von „Blauem“ Phosphor war bis vor kurzem reine Theorie: Nun konnte ein HZB-Team erstmals Proben aus blauem Phosphor an BESSY II untersuchen und über ihre elektronische Bandstruktur bestätigen, dass es sich dabei tatsächlich um diese exotische Phosphor-Modifikation handelt. Blauer Phosphor ist ein interessanter Kandidat für neue optoelektronische Bauelemente.

Das Element Phosphor tritt in vielerlei Gestalt auf und wechselt mit jeder neuen Modifikation auch den Katalog seiner Eigenschaften. Bisher bekannt waren...

Im Focus: Chemiker der Universitäten Rostock und Yale zeigen erstmals Dreierkette aus gleichgeladenen Ionen

Die Forschungskooperation zwischen der Universität Yale und der Universität Rostock hat neue wissenschaftliche Ergebnisse hervorgebracht. In der renommierten Zeitschrift „Angewandte Chemie“ berichten die Wissenschaftler über eine Dreierkette aus Ionen gleicher Ladung, die durch sogenannte Wasserstoffbrücken zusammengehalten werden. Damit zeigen die Forscher zum ersten Mal eine Dreierkette aus gleichgeladenen Ionen, die sich im Grunde abstoßen.

Die erfolgreiche Zusammenarbeit zwischen den Professoren Mark Johnson, einem weltbekannten Cluster-Forscher, und Ralf Ludwig aus der Physikalischen Chemie der...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Rettungsdienst und Feuerwehr - Beschaffung von Rettungsdienstfahrzeugen, -Geräten und -Material

18.10.2018 | Veranstaltungen

11. Jenaer Lasertagung

16.10.2018 | Veranstaltungen

DFG unterstützt Kongresse und Tagungen - Dezember 2018

16.10.2018 | Veranstaltungen

VideoLinks
Wissenschaft & Forschung
Weitere VideoLinks im Überblick >>>
 
Aktuelle Beiträge

Nanodiamanten als Photokatalysatoren

18.10.2018 | Materialwissenschaften

Schichten aus Braunschweig auf dem Weg zum Merkur

18.10.2018 | Physik Astronomie

Rettungsdienst und Feuerwehr - Beschaffung von Rettungsdienstfahrzeugen, -Geräten und -Material

18.10.2018 | Veranstaltungsnachrichten

Weitere B2B-VideoLinks
IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics