Scott Tiger Tech Blog

Blog technologiczny firmy Scott Tiger S.A.

Diagram Hiveplot

Autor: Eliza Szczechla o piątek 30. Sierpień 2013

k
Diagram Hiveplot to metoda wizualizacji sieci, w której graficzny rozkład elementów diagramu zależny jest wyłącznie od samej struktury sieci oraz istotnych dla odbiorcy informacji, związanych z prezentowanymi obiektami. Hiveplot stanowi alternatywę dla typowych sposobów reprezentacji złożonych sieci, do których wizualizacji stosuje się algorytmy rozkładu niezależne od domeny zastosowań.

Często wymienianą dziedziną zastosowań diagramu jest genomika, w której powszechnie stosowany jest diagram kołowy Circos. Hiveplot jest często przedstawiamy jako alternatywa dla diagramów Hairball.

Diagramy Hiveplot zostały przedstawione w pracy: Krzywinski M, Birol I, Jones S, Marra M (2011). Hive Plots — Rational Approach to Visualizing Networks. Briefings in Bioinformatics.

Źródło: hiveplot.com

Konstrukcja diagramu Hiveplot

  • Wierzchołki grafu rozmieszczone są na promieniście ułożonych osiach;
  • Wybór osi dla wierzchołka oraz jego promień (odległość od centrum diagramu), dokonywany jest na podstawie struktury grafu (np. liczby wierzchołków sąsiednich) lub cechy obiektu, który wierzchołek reprezentuje (np. poziom ekspresji genu);
  • Krawędzie grafu reprezentowane są przez łuki łączące wierzchołki;
  • Dodatkowe informacje mogą być reprezentowane przez: kolor i rodzaj symbolu dla wierzchołków oraz kolor i grubość krawędzi;
  • Długość osi może być określona z góry lub zależna od zbioru wierzchołków przydzielonych do osi;
  • Osie mogą być dodatkowo podzielone na segmenty, odzwierciedlające klasyfikację wierzchołków;

Źródło: mkweb.bcgsc.ca

Ograniczenia algorytmów rozkładu bazujących na estetyce

Wynik działania różnych algorytmów dla tej samej sieci; Źródło: mkweb.bcgsc.ca

Często stosowanym sposobem prezentacji sieci jest wykorzystanie uniwersalnych algorytmów rozmieszczających graf na płaszczyźnie (np. typu force-directed), dążących do jak największej przejrzystości rozkładu m.in. poprzez minimalizację liczby przecinających się krawędzi oraz wyrównanie ich średniej długości. Przy takim podejściu, położenie wierzchołka nie wynika jednoznacznie z cech obiektu, który on reprezentuje ani z jego umiejscowienia w sieci powiązań (np. liczby sąsiadów). Powoduje to, że otrzymany układ graficzny nie odzwierciedla bezpośrednio interesujących odbiorcę parametrów badanej sieci, utrudniając jednoznaczną interpretację i porównywanie otrzymanych w ten sposób grafów.
Co więcej, różne algorytmy generują znacznie różniące się rozkłady tej samej sieci. Taki sposób prezentacji sprawdza się dla prostych grafów, jednak wraz ze wzrostem złożoności danych ujawnia swoje ograniczenia:

  • Czytelność diagramu drastycznie spada ze wzrostem złożoności sieci;
  • Kolejne uruchomienia dla tych samych danych mogą dawać różne rezultaty, uniemożliwiając porównywanie diagramów i śledzenie zmian, ponieważ wiele algorytmów zawiera elementy losowe;
  • Układ grafu może nie odzwierciedlać informacji, które interesują odbiorcę, ponieważ jest niezależny od dziedziny zastosowań;
  • Nie jest możliwe miarodajne porównanie dwóch skomplikowanych sieci, ponieważ trudno ocenić w jakim stopniu różnice wynikają z samych danych, a w jakim zależą od algorytmu rozkładu;
  • Niewielkie zmiany w danych mogą mieć niewspółmiernie duży wpływ na układ graficzny diagramu;

Zalety algorytmu rozkładu zależnego od danych

W przypadku Hiveplot, wygląd diagramu jest ściśle podporządkowany parametrom wskazanym przez przyszłych odbiorców. Miejsce każdego wierzchołka na płaszczyźnie jest jednoznacznie wyznaczone przez przyjęte kryteria, związane z dziedziną zastosowań. Przykładowo, dla portalu społecznościowego, o przydziale wierzchołka do jednej z osi decydować może liczba znajomych użytkownika, a o odległości wierzchołka od centrum diagramu – jego staż na portalu, krawędzie reprezentowałyby komunikację między użytkownikami. Wizualna interpretacja oraz porównywanie takich diagramów są całkowicie jednoznaczne, wiemy np., że zagęszczenie krawędzi daleko od centrum oznacza dużą aktywność starszych stażem użytkowników, nie jest zaś wynikiem działania algorytmu typu force-directed. Główne zalety tego podejścia:

  • Diagram pozostaje czytelny także dla bardzo skomplikowanych sieci;
  • Możliwe jest miarodajne porównanie grafów reprezentujących dwie sieci lub tę samą sieć po wprowadzeniu zmian;
  • Interpretacja układu diagramu jest prosta i jednoznaczna, ponieważ jest on tworzony wyłącznie w oparciu o informacje istotne dla jego odbiorców;
  • Kolejne uruchomienia algorytmu dają identyczne rezultaty;

Zastosowanie

Przeznaczeniem diagramu Hiveplot jest obrazowanie złożonych sieci. Może być stosowany do wszelkich zestawów danych, które mogą być przedstawione w kategoriach relacji między parami elementów, zarówno skierowanych jak i nieskierowanych. Często cytowanym przykładem, zwłaszcza w kontekście porównania czytelności diagramów Hairball i Hiveplot, jest zestawienie sieci regulacji genowych bakterii E. coli oraz drzewa wywołań funkcji w jądrze systemu Linux.

Narzędzia

  • jhive – Java
  • HiveR – język R, dostępne diagramy 2D oraz 3D (przy wykorzystaniu pakietu rgl); Demo interaktywnej animacji 3D, dla losowych danych, można uzyskać w środowisku R przy pomocy poniższego kodu (po instalacji pakietów HiveR i rgl):
    require("HiveR")
    require("rgl")
    nx <- 6 #liczba osi
    demoData <- ranHiveData(nx = nx, type = "3D")
    plot3dHive(demoData)
  • implementacja przy użyciu d3.js – JavaScript
Share and Enjoy:
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • Śledzik
  • Blip
  • Blogger.com
  • Gadu-Gadu Live
  • LinkedIn
  • MySpace
  • Wykop

Zostaw komentarz

XHTML: Możesz użyć następujących tagów: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>