Hyse: A spring embedder approach for layout of hybrid graphs
Hyse: Hibrit çizge yerleşimi için yay bazlı yaklaşım
- Tez No: 842059
- Danışmanlar: PROF. DR. UĞUR DOĞRUSÖZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 93
Özet
Son zamanlarda verilerin büyümesi katlanarak arttı ve ilişkisel verilerin görsel analizini giderek karmaşık hale getirdi. Bu tür verileri görsel olarak çekici bir şekilde sunmak, analiz sürecini basitleştirmeye yardımcı olabilir. Merkezi yönlendirilmiş veya hiyerarşik bir parça ve birbirine bağlı yönlendirilmemiş bileşenlerden oluşan hibrit çizgeler, karmaşıklığını yönetirken değişen soyutlama düzeylerine sahip ilişkisel verileri temsil etmek için pratik bir yapı sunar. Verilerdeki ilişkileri anlamak, içgörüleri keşfetmek ve önemli kalıpları elde etmek için bu tür çizgelere yönelik iyi optimize edilmiş bir çizge düzenine ihtiyaç vardır. Buna yanıt olarak, hibrit çizgeler için özel olarak tasarlanmış yeni bir çizge düzeni algoritması olan HySE'yi (Hybrid Spring Embedder) sunuyoruz. HySE, hem yönlendirilmiş hem de yönlendirilmemiş arasındaki uyumu korurken, yalnızca çizgenin yönlendirilmemiş kısmında değil, aynı zamanda hiyerarşide de optimize edilmiş kuvvet yönlendirmeli düzenin estetiğini ve kalitesini elde etmek için popüler yay yerleştirmeyi temel alan bütünsel bir yaklaşımdan yararlanır. Yerleştirme algoritması, yönlendirilmiş çizge elemanlarının sıralama bilgilerinin, popüler yaklaşımlardan biriyle önceden hesaplandığını varsayar. Daha sonra uygun başlangıç konumlarını bulur ve yönlendirilmemiş parçaları yerleşime entegre etmek için kuvvet yönlendirmeli yerleşim tekniğini kullanır, kenarları modellemek için yay kuvvetlerini ve düğümler için itici elektrik kuvvetlerini uygular. Yinelemeli bir yöntem olan HySE, enerjinin en aza indirildiği bir denge durumuna yakınsar, bu da karmaşık hibrit çizgeler için görsel olarak hoş ve yorumlanabilir düzenler sağlar. İyi tasarlanmış bir süreçle rastgele oluşturulan bileşik hibrit çizgeler üzerinde gerçekleştirilen deneyler, HySE'nin kalite açısından en son teknoloji algoritmalar kadar iyi performans gösterdiğini doğrulamaktadır. Aynı zamanda küçük ve orta boyutlu çizgelerde de bilinen algoritmaların hızını yakalar.
Özet (Çeviri)
In recent times, the growth of data has been exponential, making the visual analysis of relational data progressively complex. Presenting such data in a visually appealing manner can help simplify the analysis process. Hybrid graphs, comprising a central directed or hierarchical part and interconnected undirected components, offer a practical structure for representing relational data with varying levels of abstraction while managing its complexity. To comprehend the relationships in data, discover insights, and get important patterns, a well-optimized graph layout for such graphs is needed. In response, we present HySE (Hybrid Spring Embedder), a novel graph layout algorithm tailored for hybrid graphs. HySE makes use of a holistic approach based on the popular spring embedder to achieve the aesthetics and quality of an optimized force-directed layout, not only on the undirected part of the graph but also on the hierarchy while maintaining the cohesion between both directed and undirected elements of the graph. The layout algorithm assumes the rank information of directed graph elements is already calculated with one of the popular approaches. Then, it finds appropriate initial positions and uses a force-directed layout technique to integrate the undirected parts into the layout, applying spring forces to model the edges, and repulsive electric forces for the nodes. Iteratively, HySE converges to an equilibrium state with minimized energy, resulting in visually pleasing and interpretable layouts for intricate hybrid graphs. Experiments performed on graphs, generated randomly through a well-designed process, validate that HySE performs as well as the state-of-the-art algorithms in terms of quality. It also matches the speed of well-established algorithms as well in small-to-medium-sized graphs.