Power Graph vizualizációs algoritmusok

A teljesítménygráf- vizualizációs algoritmusok a gráfvizualizációs algoritmusok  egy osztályát alkotják , esztétikus módon. Céljuk, hogy a gráf csomópontjait 2D-s vagy 3D-s térben úgy rendezzék el, hogy minden él többé-kevésbé azonos hosszúságú legyen, és minimalizálják az élmetszéspontok számát úgy, hogy több élhez és csomóponthoz a relatív helyzetük alapján erőt rendelnek, majd a ezek az erők vagy az élek és csomópontok mozgásának szimulálására, vagy azok energiájának minimalizálására [2] .

Míg a gráfok megjelenítése nehéz feladat lehet, a kényszeralgoritmusok, mint fizikai modellek, általában nem igényelnek speciális gráfelméleti ismereteket, mint például a gráfsíkság .

Erők

Az erő gráf vizualizációs algoritmusai erőket rendelnek hozzá a gráf éleinek és csomópontjainak halmazához . Elterjedt a rugószerű vonzási erők használata a Hooke-törvény alapján, hogy erőket rendeljünk a gráf éleinek párjaihoz. Ugyanakkor az elektromosan töltött részecskék Coulomb-törvénye alapján történő taszításához hasonló taszító erőket használnak az összes csomópontpár szétválasztására. Ennek az erőrendszernek az egyensúlyi állapotának eléréséhez az élek hajlamosak egyenletes hosszúságot kapni (a rugók hatására), és azok a csomópontok, amelyeket él nem köt össze, általában egymástól távol helyezkednek el (a taszító erők hatása). A vonzó erők (bordák) és a taszító erők (csomók) olyan függvények segítségével határozhatók meg, amelyek nem a rugók és részecskék fizikai viselkedésén alapulnak. Például egyes energiarendszerek rugókat használnak, amelyek erői logaritmikusan változnak, nem pedig lineárisan.

Egy alternatív modell rugószerű erőket vesz figyelembe minden egyes csomópontpárra, ahol az egyes rugók ideális hossza arányos a gráfban az i és j csomópontok közötti távolsággal , és nem használnak taszító erőket. Az euklideszi és a csomópontok közötti ideális távolság közötti különbség (általában a különbség négyzete) minimalizálása egyenértékű a többváltozós skálázási metrika problémájával .

Az erőgrafikon a mechanikus rugóktól és a töltés taszító erőktől eltérő erőket is felhasználhat. A gravitációhoz hasonló erővel a csúcsokat egy fix pont felé húzhatjuk a gráfrajzi térben. Ezzel egy szétválasztott gráf különböző összefüggő komponenseit egyetlen egésszé lehet redukálni , különben ezek a részek a taszító erők hatására szétrepülnének egymástól. Azt is lehetővé teszi, hogy a [3] ábrán javított központi pozíciójú csomópontokat kapjon . Ez ugyanabban a csatlakoztatott komponensben a csúcsok közötti távolságot is befolyásolhatja. A mágneses mezők analógjai használhatók irányított gráfokhoz. A taszító erőket mind az élekre, mind a csomópontokra lehet helyezni, hogy elkerüljük az átfedést vagy a közeli átfedést a végső rajzon. Az ívelt élekkel rendelkező rajzokon, mint például körívek vagy spline -ok, ezeknek a görbéknek a szabályozási pontjain erők is elhelyezhetők, például a szögfelbontás javítása érdekében [4] .

Módszerek

Miután meghatároztuk a csomópontokon és az éleken lévő erőket, a teljes gráf viselkedése ezen erők hatására iteratív módon modellezhető, mintha az egy fizikai rendszer lenne. Ilyen helyzetben a csomópontokra ható erők megpróbálják közelebb húzni vagy eltolni őket egymástól. Ez addig folytatódik, amíg a rendszer el nem éri a mechanikai egyensúlyi állapotot , azaz a csomópontok helyzete nem változik iterációról iterációra. A csomópontok pozíciója ebben az egyensúlyi állapotban a gráf rajzának generálására szolgál.

Az olyan rugókból meghatározott erők esetében, amelyek ideális hossza arányos a gráf távolságával, a feszültség majorizálás nagyon jó viselkedést (azaz monoton konvergenciát ) [5] és matematikailag elegáns módszert ad ennek a különbségnek a minimalizálására, és ezáltal a gráf csúcspontjainak jó elhelyezésére.

Használhat olyan mechanizmusokat is, amelyek közvetlenül keresik az energiaminimumot, nem pedig fizikai modell szerint. Az ilyen mechanizmusok, amelyek az általános globális optimalizálási technikák példái, magukban foglalják a szimulált lágyítást és a genetikai algoritmusokat .

Előnyök

A következő tulajdonságok az erőalgoritmusok legfontosabb előnyei:

Jó minőségű eredmények Legalábbis közepes méretű gráfok esetében (50-500 csúcsig) a kapott eredmények általában nagyon jó gráfmintázatot mutatnak a következő kritériumok szerint: élhosszúságok egyenletessége, csúcsok egyenletes eloszlása ​​és szimmetria. Az utolsó kritérium a legfontosabb és legnehezebben teljesíthető más típusú algoritmusoknál. Rugalmasság Az erőalgoritmusok könnyen adaptálhatók és bővíthetők további esztétikai kritériumok szerint. Ez az algoritmusokat a gráfvizualizációs algoritmusok általánosabb osztályaivá teszi. Példák a meglévő bővítményekre az irányított gráf-algoritmusok, a 3D-s gráfvizualizáció [6] , a klasztergráf-vizualizáció, a korlátozott gráf-vizualizáció és a dinamikus gráfvizualizáció. Intuitivitás Mivel az algoritmusok ismert objektumok, például rugók fizikai analógjain alapulnak, az algoritmusok viselkedése viszonylag könnyen megjósolható és megérthető. Ez nem található meg más típusú gráfvizualizációs algoritmusokban. Egyszerűség A tipikus erőalgoritmusok egyszerűek, és néhány sornyi kóddal megvalósíthatók. A megjelenítési algoritmusok más osztályai, például az ortogonális elhelyezéseken alapulóak, általában sokkal több munkát igényelnek. interaktivitás Az algoritmusok ezen osztályának másik előnye az interaktivitás. A grafikon közbülső szakaszainak megrajzolásával a felhasználó nyomon követheti a grafikon változásait, nyomon követheti az evolúciót a rendetlen rendetlenségtől a szép konfigurációig. Egyes interaktív grafikonrajzoló eszközökben a felhasználó egy vagy több csomópontot kidobhat az egyensúlyi állapotból, és figyelheti, ahogy a csomópontok áttérnek az új egyensúlyi állapotba. Ez előnyt jelent az algoritmusoknak a dinamikus és online gráfvizualizációs rendszerekben. Szigorú elméleti támogatás Míg az egyszerű erőalgoritmusok gyakran megjelennek a szakirodalomban és a gyakorlatban (mivel viszonylag egyszerűek és érthetőek), az ésszerűbb megközelítések száma kezd növekedni. A statisztikusok az 1930-as évek óta foglalkoznak hasonló problémákkal a többdimenziós skálázásban ( MDS ) , és a fizikusok is hosszú múltra tekintenek vissza az n test mozgásának modellezésének kapcsolódó problémáival , tehát vannak meglehetősen kiforrott megközelítések. Példaként említjük, hogy a metrikus MDS stressz majorizációs megközelítése alkalmazható gráfvizualizációra, amely esetben a monoton konvergencia bizonyítható [5] . A monoton konvergencia, az a tulajdonság, hogy az algoritmus minden iterációnál csökkenti a csúcsok elhelyezésének stresszét vagy költségét, azért fontos, mert biztosítja, hogy az elhelyezés végül elérje a lokális minimumot, és az algoritmus leálljon. Az oszcilláció csillapítása az algoritmus leállását okozza, de nem garantálja, hogy a valódi lokális minimumot elérjük. 

Hátrányok

Az erőalgoritmusok fő hátrányai:

Remek munkaidő A tipikus erőalgoritmusok futásideje általában O (n 3 ), ahol n a csomópontok száma a bemeneti gráfban. Ennek az az oka, hogy az iterációk számát O(n) értékre becsüljük, és minden iterációnál meg kell nézni az összes csomópontpárt, és ki kell számítani a kölcsönös taszító erőket. Ez hasonló a fizika N-test problémájához . Mivel azonban a taszító erők lokális jellegűek, a gráf felosztható úgy, hogy csak a szomszédos csúcsokat veszi figyelembe. Az algoritmusok által használt fő technikák a csomópontok nagy gráfokban való elhelyezkedésének meghatározására a nagydimenziós beágyazások [7] , a réteges ábrázolások és az n-test probléma modellezésével kapcsolatos egyéb technikák . Például a Barnes-Hut szimuláción alapuló FADE metódus [8] javíthatja a futási időt n*log(n)-re iterációnként. Durva becslésként néhány másodpercen belül maximum 1000 csomópont rajzolására számíthatunk a standard n 2 technikával iterációnként és 100 000 csomópont megrajzolására az n*log(n) technikával iterációnként [8] . Az erőalgoritmusok réteges megközelítéssel kombinálva milliónyi csomópontot tartalmazó gráfokat tudnak rajzolni [9] . Rossz helyi minimumok Könnyen belátható, hogy az erőalgoritmus minimális energiájú gráfot ad, konkrétan ez csak lokális minimum lehet . A talált lokális minimum sok esetben lényegesen rosszabb lehet, mint a globális minimum, ami rossz minőségű ábrázoláshoz vezet. Számos algoritmus esetében, különösen azok esetében, amelyek csak gradiens süllyedést tesznek lehetővé , a végeredményt nagymértékben befolyásolhatja a legtöbb esetben véletlenszerűen generált kezdeti pozíció. A rossz lokális minimum problémája különösen fontossá válik a gráfcsúcsok számának növekedésével. Különböző algoritmusok kombinálása segít a probléma megoldásában [10] . Például a Kamada-Kawai algoritmus [11] segítségével gyorsan létrehozhat egy elfogadható kezdeti elhelyezést, majd a Fruchterman-Reinhold algoritmust [12] a szomszédos csomópontok helyzetének javítására. Egy másik technika a globális minimum megszerzésére a többszintű megközelítés alkalmazása [13] .

Történelem

Az erőgráf-vizualizációs módszerek Tutt munkájához nyúlnak vissza [14] amelyben megmutatta, hogy konvex lapokkal rendelkező síkra poliéder gráfok rajzolhatók, ha konvex helyzetbe ágyazó síkgráf külső felületének csúcsait rögzítjük , rugót elhelyezve. mint a vonzó erők minden élen, és lehetővé teszik a rendszer egyensúlyi állapotba kerülését [15] . Tekintettel az erők egyszerű természetére, ebben az esetben a rendszer nem akad meg egy lokális minimumban, hanem egyetlen globális optimális konfigurációhoz konvergál. Ennek a cikknek a fényében a konvex lapokkal rendelkező síkgráfok beágyazásait néha Tutt-beágyazásoknak nevezik .

A gráf szomszédos csúcsainak vonzerőinek és az összes csúcsra vonatkozó taszító erők kombinációját először Eads [16] [17] alkalmazta . Fruchterman és Reingold [18] jelent meg egy másik úttörő munkát az ilyen típusú haderő-elhelyezésről . Kamada és Kawai [19] [11] nevéhez fűződik az az ötlet, hogy minden csúcspár között csak rugóerőt használjunk, és ideális rugóhosszúság megegyezik a gráf távolságával .

Lásd még

  • Cytoscape , egy biológiai hálózat vizualizációs program. Az alapcsomag az egyik beépített módszerként tartalmazza az erőkihelyezéseket.
  • Gephi , interaktív vizualizációs és feltáró platform mindenféle hálózathoz és összetett rendszerhez, dinamikus és hierarchikus gráfokhoz.
  • Graphviz , egy olyan szoftvereszköz, amely többszintű erőelhelyezési algoritmust valósít meg (többek között), amely képes nagyon nagy grafikonok kezelésére.
  • Tulip , a legtöbb erőelhelyezési algoritmust (GEM, LGL, GRIP, FM³) megvalósító szoftvereszköz.
  • Prefuse

Jegyzetek

  1. ↑ Grandjean, 2015 , p. 109–128.
  2. ↑ Koburov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Csernobelszkij, Cunningham, Goodrich, Kobourov, Trott, 2011 , p. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , p. 163-180.
  6. ↑ Vose, Aaron 3D Phylogenetic Tree Viewer . Letöltve: 2012. június 3.  (elérhetetlen link)
  7. ↑ Harel, Koren, 2002 , p. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , p. 197-210.
  9. ↑ Nagy grafikonok galériája . Letöltve: 2017. október 22. Az eredetiből archiválva : 2021. május 25.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , p. 77–86.; Rizs. a 212. oldalon.
  11. ↑ 1 2 Kamada, Kawai, 1989 , p. 7-15.
  12. ↑ Fruchterman és Reingold 1991 , p. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Archiválva : 2021. augusztus 12. a Wayback Machine -nél A többszintű algoritmus kényszerirányított gráfrajzhoz
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , p. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , p. 149–160.
  18. ↑ Fruchterman és Reingold 1991 , p. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Irodalom

  • Martin Grandjean. Introduction à la visualization de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19 . — 2015.
  • Stephen G. Kobourov. Tavaszi beágyazók és kényszerirányított gráfrajzi algoritmusok . - 2012. - . - arXiv : 1201.3011 .
  • Bannister M. J, Eppstein MJ, Goodrich MT, Trott L. Erőirányítású gráfrajz társadalmi gravitáció és skálázás segítségével // Proc. 20. Int. Symp. grafikon rajz. — 2012.
  • Chernobelskiy R., Cunningham K., Goodrich MT, Kobourov SG, Trott L. Force-directed Lombardi-style graph drawing // Proc. 19. Grafikonrajzi Szimpózium . – 2011.
  • Jan de Leeuw. A majorizációs módszer konvergenciája többdimenziós skálázáshoz // Journal of Classification. - Springer, 1988. - V. 5 , 1. sz. 2 . - S. 163-180 . - doi : 10.1007/BF01897162 .
  • David Harel, Yehuda Koren. Grafikonrajz nagydimenziós beágyazással // Proceedings of the 9th International Symposium on Graph Drawing . - 2002. - S. 207-219. — ISBN 3-540-00158-1 .
  • Aaron Quigley, Peter Eades. FADE: Graph Drawing, Clustering, and Visual Abstraction // Proceedings of the 8th International Symposium on Graph Drawing . - 2001. - S. 197-210. — ISBN 3-540-41554-8 . Archiválva : 2006. május 21. a Wayback Machine -nél
  • Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. Rendszer a szoftverek fejlődésének grafikon alapú megjelenítéséhez // A 2003-as ACM Szoftvervizualizációs Szimpózium (SoftVis '03) anyaga . - New York, NY, USA: ACM, 2003. - S. 77-86; o. ábrái. 212. - ISBN 1-58113-642-0 . doi : 10.1145 / 774833.774844 . Idézet: Az esztétikus grafikon elrendezés eléréséhez módosított Fruchterman-Reingold erők alkalmazása szükséges, mivel a Kamada-Kawai módszer nem ad kielégítő eredményt, de jó közelítő elrendezést hoz létre, amelyből a Fruchterman-Reingold számítások gyorsan "befejezhetők" az elrendezés.
  • Tutte WT Hogyan rajzoljunk grafikont // Proceedings of the London Mathematical Society. - 1963. - T. 13 , sz. 52 . - doi : 10.1112/plms/s3-13.1.743 .
  • Peter Eades. Heurisztika a gráfrajzhoz // Congressus Numerantium. - 1984. - T. 42 , sz. 11 .
  • Thomas MJ Fruchterman, Edward M. Reingold. Grafikonrajz kényszerirányított elhelyezéssel // Szoftver – gyakorlat és tapasztalat. - Wiley, 1991. - T. 21 , 1. sz. 11 . - doi : 10.1002/spe.4380211102 .
  • Tomihisa Kamada, Satoru Kawai. Algoritmus általános irányítatlan gráfok rajzolásához // Information Processing Letters. - Elsevier, 1989. - T. 31 , 1. sz. 1 . - doi : 10.1016/0020-0190(89)90102-6 .

Olvasás további olvasáshoz

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Grafikonrajz: Algoritmusok a grafikonok megjelenítéséhez. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Grafikonok rajzolása: módszerek és modellek / Michael Kaufmann, Dorothea Wagner. - Springer, 2001. - (Számítástechnikai előadásjegyzetek, 2025). - ISBN 978-3-540-42062-0 . - doi : 10.1007/3-540-44969-8 .

Link