Algoritmy vizualizace Power Graph

Algoritmy vizualizace výkonových grafů  jsou třídou algoritmů vizualizace grafů esteticky příjemným způsobem. Jejich cílem je uspořádat uzly grafu ve 2D nebo 3D prostoru tak, aby všechny hrany byly víceméně stejně dlouhé, a minimalizovat počet průsečíků hran přidělováním sil více hranám a uzlům na základě jejich vzájemné polohy a poté pomocí tyto síly buď simulují pohyb hran a uzlů, nebo minimalizují jejich energii [2] .

Zatímco vizualizace grafů může být obtížný úkol, silové algoritmy, které jsou fyzikálními modely, obvykle nevyžadují speciální znalosti v teorii grafů, jako je planarita grafů .

Síly

Algoritmy vizualizace silového grafu přiřazují síly na sadu hran a uzlů grafu . Je běžné používat přitažlivé síly podobné pružině založené na Hookeově zákoně k přiřazení sil dvojicím konců hrany grafu. Současně se k oddělení všech párů uzlů používají odpudivé síly, podobné odpuzování elektricky nabitých částic na základě Coulombova zákona . Abychom získali rovnovážný stav tohoto systému sil, hrany mají tendenci získávat jednotné délky (v důsledku působení pružin) a uzly, které nejsou spojeny hranou, mají tendenci být umístěny ve vzájemné vzdálenosti (kvůli působení odpudivých sil). Přitažlivé síly (žebra) a odpudivé síly (uzly) lze definovat pomocí funkcí, které nejsou založeny na fyzikálním chování pružin a částic. Například některé energetické systémy používají pružiny, jejichž síly se mění spíše logaritmicky než lineárně.

Alternativní model uvažuje síly podobné pružině pro každý pár uzlů , kde ideální délka každé pružiny je úměrná vzdálenosti v grafu mezi uzly i a j a nejsou použity žádné odpudivé síly. Minimalizace rozdílu (obvykle druhá mocnina rozdílu) mezi euklidovskou a ideální vzdáleností mezi uzly je ekvivalentní metrickému problému s více proměnnými .

Silový graf může využívat jiné síly než mechanické pružiny a síly odpuzování náboje. Sílu podobnou gravitaci lze použít k přitažení vrcholů k pevnému bodu v prostoru kreslení grafu. Toho lze využít ke zmenšení různých spojených složek rozpojeného grafu do jediného celku, jinak by se tyto části působením odpudivých sil od sebe rozlétly. Umožňuje také získat uzly s vylepšenou středovou polohou na obrázku [3] . To může také ovlivnit rozestupy mezi vrcholy ve stejné připojené komponentě. Analogy magnetických polí lze použít pro orientované grafy. Na hrany i uzly lze působit odpudivé síly, aby se předešlo překrývání nebo téměř překrývání ve finálním výkresu. Ve výkresech se zakřivenými hranami, jako jsou kruhové oblouky nebo splajny , mohou být síly také umístěny v řídicích bodech těchto křivek, například pro zlepšení úhlového rozlišení [4] .

Metody

Jakmile jsou síly v uzlech a hranách určeny, lze chování celého grafu pod těmito silami iterativně modelovat, jako by se jednalo o fyzikální systém. V takové situaci se síly působící na uzly snaží je přitáhnout k sobě nebo je od sebe odtlačit. Toto pokračuje, dokud se systém nedostane do stavu mechanické rovnováhy , tj. poloha uzlů se od iterace k iteraci nemění. Poloha uzlů v tomto rovnovážném stavu se použije pro vykreslení grafu.

Pro síly definované z pružin, jejichž ideální délka je úměrná vzdálenosti v grafu, poskytuje majorizace napětí velmi dobré chování (tj. monotónní konvergenci ) [5] a matematicky elegantní způsob , jak tento rozdíl minimalizovat , a tím i k dobrému umístění vrcholů grafu.

Můžete také použít mechanismy, které hledají energetické minimum přímočařeji než podle fyzikálního modelu. Takové mechanismy, které jsou příklady obecných globálních optimalizačních technik , zahrnují simulované žíhání a genetické algoritmy .

Výhody

Následující vlastnosti jsou nejdůležitějšími výhodami silových algoritmů:

Dobrá kvalita výsledků Alespoň u středně velkých grafů (do 50-500 vrcholů) mají získané výsledky obvykle velmi dobré vzory grafů pro následující kritéria: stejnoměrnost délek hran, rovnoměrné rozložení vrcholů a symetrie. Poslední kritérium je nejdůležitější a obtížně dosažitelné v jiných typech algoritmů. Flexibilita Silové algoritmy lze snadno přizpůsobit a rozšířit o další estetická kritéria. Díky tomu jsou algoritmy obecnějšími třídami algoritmů pro vizualizaci grafů. Příklady existujících rozšíření jsou algoritmy řízeného grafu, 3D grafová vizualizace [6] , shluková grafová vizualizace, omezená grafová vizualizace a dynamická grafová vizualizace. Intuitivnost Vzhledem k tomu, že algoritmy jsou založeny na fyzických analogech známých objektů, jako jsou pružiny, je chování algoritmů relativně snadno předvídatelné a pochopitelné. To se v jiných typech algoritmů pro vizualizaci grafů nenachází. Jednoduchost Typické silové algoritmy jsou jednoduché a lze je implementovat v několika řádcích kódu. Jiné třídy vykreslovacích algoritmů, jako jsou algoritmy založené na ortogonálních umístěních, obvykle vyžadují mnohem více práce. interaktivita Další výhodou této třídy algoritmů je aspekt interaktivity. Nakreslením přechodných fází grafu může uživatel sledovat, jak se graf mění, a sledovat vývoj od chaotického nepořádku k dobře vypadající konfiguraci. V některých interaktivních nástrojích pro kreslení grafů může uživatel vypustit jeden nebo více uzlů z rovnovážného stavu a sledovat, jak uzly migrují do nového rovnovážného stavu. To dává algoritmům výhodu pro dynamické a online grafové vizualizační systémy. Přísná teoretická podpora Zatímco jednoduché silové algoritmy se často objevují v literatuře i v praxi (protože jsou relativně jednoduché a srozumitelné), počet rozumnějších přístupů začíná přibývat. Statistikové řeší podobné problémy v multidimenzionálním škálování ( MDS ) již od  30. let 20. století a fyzici mají také dlouhou historii práce se souvisejícími problémy modelování pohybu n těles , takže existují poměrně vyspělé přístupy. Například přístup majorizace napětí k metrickému MDS může být aplikován na grafovou vizualizaci, v tomto případě lze dokázat monotónní konvergenci [5] . Monotónní konvergence, vlastnost, že algoritmus sníží stres nebo náklady na umístění vrcholů v každé iteraci, je důležitá, protože zajišťuje, že umístění nakonec dosáhne lokálního minima a algoritmus se zastaví. Tlumení oscilací způsobí zastavení algoritmu, ale nezaručuje, že bude dosaženo skutečného lokálního minima.

Nevýhody

Hlavní nevýhody silových algoritmů:

Skvělá pracovní doba U typických silových algoritmů se obecně předpokládá , že mají doby běhu ekvivalentní O(n 3 ), kde n je počet uzlů ve vstupním grafu. Počet iterací se totiž odhaduje na O(n) a při každé iteraci je nutné se podívat na všechny dvojice uzlů a vypočítat vzájemné odpudivé síly. To je podobné problému N-těla ve fyzice. Protože však odpudivé síly mají lokální povahu, lze graf rozdělit tak, aby byly brány v úvahu pouze sousední vrcholy. Mezi hlavní techniky používané algoritmy k určení umístění uzlů ve velkých grafech patří vysokorozměrné vkládání [7] , vrstvené reprezentace a další techniky související s modelováním problému n-těl . Například metoda FADE [8] založená na simulaci Barnes-Hut může zlepšit dobu běhu na n*log(n) na iteraci. Hrubým odhadem lze během několika sekund očekávat nakreslení maximálně 1000 uzlů standardní technikou n 2 na iteraci a 100 000 uzlů technikou n*log(n) na iteraci [8] . Silové algoritmy v kombinaci s vrstveným přístupem mohou kreslit grafy s miliony uzlů [9] . Špatná místní minima Je snadné vidět, že silový algoritmus dává graf s minimální energií, konkrétně to může být pouze lokální minimum . Zjištěné lokální minimum může být v mnoha případech výrazně horší než globální minimum, což vede k nekvalitnímu zastoupení. U mnoha algoritmů, zejména těch, které umožňují pouze gradientní sestupný pohyb , může být konečný výsledek silně ovlivněn počáteční polohou, která je ve většině případů generována náhodně. Problém špatného lokálního minima se stává obzvláště důležitým s rostoucím počtem vrcholů grafu. Kombinace různých algoritmů pomáhá tento problém vyřešit [10] . Například lze použít algoritmus Kamada-Kawai [11] pro rychlé vygenerování přijatelného počátečního umístění a poté algoritmus Fruchterman-Reinhold [12] pro zlepšení pozice sousedních uzlů. Další technikou pro získání globálního minima je použití víceúrovňového přístupu [13] .

Historie

Metody vizualizace silového grafu se vracejí k Tuttově práci [14] ve které ukázal, že polyedrické grafy lze kreslit na rovině s konvexními plochami fixováním vrcholů vnější plochy rovinného grafu v konvexní poloze a umístěním pružiny. jako přitažlivé síly na každé hraně a umožňují systému dostat se do rovnovážného stavu [15] . Vzhledem k jednoduché povaze sil se v tomto případě systém nemůže zaseknout v lokálním minimu, ale konverguje k jediné globální optimální konfiguraci. S ohledem na tento článek se vložení rovinných grafů s konvexními plochami někdy nazývá vložení Tutt .

Kombinaci přitažlivých sil sousedních vrcholů grafu a odpudivých sil pro všechny vrcholy poprvé použil Eads [16] [17] . Další průkopnickou práci o tomto typu umístění síly publikovali Fruchterman a Reingold [18] . Myšlenka použití pouze pružinových sil mezi všemi páry vrcholů s ideální délkou pružiny rovnající se vzdálenosti grafu má na svědomí Kamada a Kawai [19] [11] .

Viz také

  • Cytoscape , program pro vizualizaci biologické sítě. Základní balíček obsahuje silové umístění jako jednu z vestavěných metod.
  • Gephi , interaktivní vizualizační a průzkumná platforma pro všechny druhy sítí a komplexních systémů, dynamické a hierarchické grafy.
  • Graphviz , softwarový nástroj, který implementuje víceúrovňový algoritmus umístění síly (mimo jiné) schopný zpracovat velmi velké grafy.
  • Tulip , softwarový nástroj, který implementuje většinu algoritmů pro umístění síly (GEM, LGL, GRIP, FM³).
  • Prefuse

Poznámky

  1. ↑ Grandjean, 2015 , str. 109–128.
  2. ↑ Koburov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Černobelskij, Cunningham, Goodrich, Kobourov, Trott, 2011 , str. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , str. 163-180.
  6. ↑ Vose, Aaron 3D prohlížeč fylogenetických stromů . Staženo: 3. června 2012.  (nepřístupný odkaz)
  7. ↑ Harel, Kořen, 2002 , str. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , str. 197-210.
  9. ↑ Galerie velkých grafů . Získáno 22. října 2017. Archivováno z originálu 25. května 2021.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , str. 77–86; Rýže. na straně 212.
  11. ↑ 1 2 Kamada, Kawai, 1989 , str. 7-15.
  12. ↑ Fruchterman a Reingold 1991 , str. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Archivováno 12. srpna 2021 na Wayback Machine Víceúrovňový algoritmus pro vykreslování grafů zaměřených na sílu
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , str. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , s. 149–160.
  18. ↑ Fruchterman a Reingold 1991 , str. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Literatura

Čtení pro další čtení

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Kreslení grafů: Algoritmy pro vizualizaci grafů. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Kreslení grafů: metody a modely / Michael Kaufmann, Dorothea Wagner. - Springer, 2001. - (Poznámky k přednáškám z informatiky 2025). - ISBN 978-3-540-42062-0 . - doi : 10.1007/3-540-44969-8 .

Odkaz