Power Graph -visualisointialgoritmit

Tehograafin visualisointialgoritmit  ovat luokka graafisen visualisointialgoritmeja esteettisesti miellyttävällä tavalla. Heidän tavoitteenaan on järjestää graafin solmut 2D- tai 3D-avaruudessa siten, että kaikki reunat ovat suunnilleen saman pituisia, ja minimoida reunojen leikkauspisteiden määrä kohdistamalla voimia useille kulmille ja solmuille niiden suhteellisen sijainnin perusteella ja sitten käyttämällä nämä voimat joko simuloivat reunojen ja solmujen liikettä tai minimoivat niiden energiaa [2] .

Vaikka graafien visualisointi voi olla vaikea tehtävä, voima-algoritmit, jotka ovat fyysisiä malleja, eivät yleensä vaadi erityistä graafiteorian osaamista, kuten graafin tasomaisuutta .

Voimia

Voimakuvaajan visualisointialgoritmit osoittavat voimia graafin reunojen ja solmujen joukkoon . On yleistä käyttää Hooken lakiin perustuvia jousimaisia ​​houkuttelevia voimia määrittämään voimia graafin reunan päiden pareihin. Samaan aikaan kaikkien solmuparien erottamiseen käytetään hylkiviä voimia, jotka ovat samanlaisia ​​kuin sähköisesti varautuneiden hiukkasten hylkiminen Coulombin lain perusteella. Tämän voimajärjestelmän tasapainotilan saavuttamiseksi reunat pyrkivät saamaan tasaisen pituuden (jousien vaikutuksesta), ja solmut, joita ei ole liitetty reunalla, sijaitsevat yleensä etäisyyden päässä toisistaan ​​(johtuen hylkivien voimien toiminta). Vetovoimat (rivat) ja hylkivät voimat (solmut) voidaan määritellä funktioilla, jotka eivät perustu jousien ja hiukkasten fysikaaliseen käyttäytymiseen. Esimerkiksi joissakin tehojärjestelmissä käytetään jousia, joiden voimat vaihtelevat logaritmisesti pikemminkin kuin lineaarisesti.

Vaihtoehtoinen malli ottaa huomioon jousimaiset voimat jokaiselle solmuparille, jossa kunkin jousen ihanteellinen pituus on verrannollinen kaavion solmujen i ja j väliseen etäisyyteen , eikä hylkiviä voimia käytetä. Euklidisen ja ideaalisen solmuetäisyyden välisen eron (yleensä eron neliön) minimoiminen vastaa monimuuttujan skaalausmetriikkaongelmaa .

Voimakäyrä voi käyttää muita voimia kuin mekaanisia jousia ja varauksen hylkäysvoimia. Painovoiman kaltaista voimaa voidaan käyttää vetämään pisteitä kohti kiinteää pistettä graafin piirtoavaruudessa. Tämän avulla voidaan tiivistää irrallisen graafin eri toisiinsa liittyvät komponentit yhdeksi kokonaisuudeksi, muuten nämä osat lennättäisivät toisistaan ​​irti hylkivien voimien vaikutuksesta. Sen avulla voit myös saada solmuja, joissa on parannettu keskiasema kuvassa [3] . Tämä voi myös vaikuttaa kärkien välisiin etäisyyksiin samassa yhdistetyssä komponentissa. Magneettikenttien analogeja voidaan käyttää suunnatuissa kaavioissa. Repulsiivisia voimia voidaan sijoittaa sekä reunoihin että solmuihin päällekkäisyyksien tai lähes päällekkäisyyksien välttämiseksi lopullisessa piirustuksessa. Piirustuksissa, joissa on kaarevia reunoja, kuten ympyräkaareja tai splineitä , voimia voidaan sijoittaa myös näiden käyrien ohjauspisteisiin esimerkiksi kulmaresoluution parantamiseksi [4] .

Menetelmät

Kun solmujen ja reunojen voimat on määritetty, koko graafin käyttäytyminen näiden voimien alaisuudessa voidaan mallintaa iteratiivisesti ikään kuin se olisi fyysinen järjestelmä. Tällaisessa tilanteessa solmuihin vaikuttavat voimat yrittävät vetää niitä lähemmäs tai työntää niitä poispäin toisistaan. Tämä jatkuu, kunnes järjestelmä tulee mekaanisen tasapainon tilaan , eli solmujen sijainti ei muutu iteraatiosta iteraatioon. Solmujen sijaintia tässä tasapainotilassa käytetään graafin piirustuksen luomiseen.

Jousista määritellyille voimille, joiden ihanteellinen pituus on verrannollinen kaavion etäisyyteen, jännitysten suurentaminen tuottaa erittäin hyvän käyttäytymisen (eli monotonisen konvergenssin ) [5] ja matemaattisesti tyylikkään tavan minimoida tämä ero ja siten hyvä kuvaajan kärkipisteiden sijoittelu.

Voit myös käyttää mekanismeja, jotka etsivät energiaminimiä suoremmin fyysisen mallin sijaan. Tällaisia ​​mekanismeja, jotka ovat esimerkkejä yleisistä globaaleista optimointitekniikoista , ovat simuloitu hehkutus ja geneettiset algoritmit .

Edut

Seuraavat ominaisuudet ovat voimaalgoritmien tärkeimmät edut:

Hyvälaatuiset tulokset Ainakin keskikokoisten graafien (jopa 50-500 kärkeä) kohdalla saaduissa tuloksissa on yleensä erittäin hyvät graafimallit seuraaville kriteereille: reunapituuksien tasaisuus, kärkien tasainen jakautuminen ja symmetria. Viimeinen kriteeri on tärkein ja vaikein saavuttaa muun tyyppisissä algoritmeissa. Joustavuus Voima-algoritmeja voidaan helposti mukauttaa ja laajentaa esteettisiä lisäkriteerejä varten. Tämä tekee algoritmeista yleisempiä kuvaajan visualisointialgoritmien luokkia. Esimerkkejä olemassa olevista laajennuksista ovat suunnatut graafialgoritmit, 3D-graafin visualisointi [6] , klusterigraafin visualisointi, rajoitettu graafin visualisointi ja dynaaminen graafin visualisointi. Intuitiivisuus Koska algoritmit perustuvat tuttujen kohteiden, kuten jousien, fysikaalisiin analogeihin, algoritmien käyttäytyminen on suhteellisen helppo ennustaa ja ymmärtää. Tätä ei löydy muun tyyppisistä graafin visualisointialgoritmeista. Yksinkertaisuus Tyypilliset voima-algoritmit ovat yksinkertaisia ​​ja ne voidaan toteuttaa muutamalla koodirivillä. Muut renderöintialgoritmien luokat, kuten ortogonaaliseen sijoitteluun perustuvat, vaativat yleensä paljon enemmän työtä. interaktiivisuus Toinen tämän luokan algoritmien etu on interaktiivisuus. Piirtämällä kaavion välivaiheet käyttäjä voi seurata kaavion muutoksia ja seurata kehitystä sotkuisesta sotkusta hyvännäköiseen kokoonpanoon. Joissakin interaktiivisissa graafin piirtämistyökaluissa käyttäjä voi pudottaa yhden tai useamman solmun tasapainotilasta ja katsella solmujen siirtymistä uuteen tasapainotilaan. Tämä antaa algoritmeille edun dynaamisissa ja online graafin visualisointijärjestelmissä. Tiukka teoreettinen tuki Vaikka yksinkertaisia ​​voimaalgoritmeja esiintyy usein kirjallisuudessa ja käytännössä (koska ne ovat suhteellisen yksinkertaisia ​​ja ymmärrettäviä), järkevämpien lähestymistapojen määrä alkaa kasvaa. Tilastomiehet ovat ratkaisseet samanlaisia ​​ongelmia moniulotteisessa skaalauksessa ( MDS ) 1930-luvulta lähtien  , ja fyysikot ovat myös työskennelleet pitkään liittyvien n kappaleen liikkeen mallintamiseen liittyvien ongelmien parissa , joten on olemassa melko kypsiä lähestymistapoja. Esimerkkinä metrisen MDS:n jännitysmajoituslähestymistapaa voidaan soveltaa graafin visualisointiin, jolloin monotoninen konvergenssi voidaan todistaa [5] . Monotoninen konvergenssi, ominaisuus, että algoritmi vähentää jännitystä tai kustannuksia pisteiden sijoittamisesta kussakin iteraatiossa, on tärkeä, koska se varmistaa, että sijoitus saavuttaa lopulta paikallisen minimin ja algoritmi pysähtyy. Vaimennusvärähtelyt pysäyttävät algoritmin, mutta eivät takaa todellisen paikallisen minimin saavuttamista.

Haitat

Voima-algoritmien tärkeimmät haitat:

Hieno työaika Tyypillisillä voimaalgoritmeilla katsotaan yleensä olevan ajoajat, jotka vastaavat O(n 3 ), missä n on solmujen lukumäärä syötekaaviossa. Tämä johtuu siitä, että iteraatioiden lukumääräksi arvioidaan O(n), ja jokaisessa iteraatiossa on tarpeen tarkastella kaikkia solmupareja ja laskea keskinäiset hylkimisvoimat. Tämä on samanlainen kuin fysiikan N-kappaleen ongelma . Koska hylkivät voimat ovat kuitenkin luonteeltaan paikallisia, graafi voidaan jakaa siten, että vain viereiset kärjet otetaan huomioon. Algoritmien tärkeimmät tekniikat solmujen sijoittelun määrittämisessä suurissa kaavioissa ovat korkeadimensionaaliset upotukset [7] , kerrostetut esitykset ja muut n-kappaleen ongelman mallintamiseen liittyvät tekniikat . Esimerkiksi Barnes-Hut -simulaatioon perustuva FADE-menetelmä [8] voi parantaa ajoaikaa n*log(n):iin iteraatiota kohti. Karkeana arviona voidaan odottaa, että muutamassa sekunnissa voit piirtää enintään 1000 solmua standardi n 2 -tekniikalla iteraatiota kohti ja 100 000 solmua n*log(n) -tekniikalla iteraatiota kohti [8] . Voima-algoritmit, kun ne yhdistetään kerrostettuun lähestymistapaan, voivat piirtää kuvaajia miljoonilla solmuilla [9] . Huonot paikalliset minimit On helppo nähdä, että voima-algoritmi antaa graafin, jolla on minimaalinen energia, erityisesti se voi olla vain paikallinen minimi . Löytynyt paikallinen minimi voi monissa tapauksissa olla merkittävästi huonompi kuin globaali minimi, mikä johtaa huonolaatuiseen esitykseen. Monissa algoritmeissa, erityisesti niissä, jotka sallivat vain gradienttilaskeutumisliikkeen , lopputulokseen voi vaikuttaa voimakkaasti alkusijainti, joka generoidaan useimmissa tapauksissa satunnaisesti. Huonon paikallisen minimin ongelma tulee erityisen tärkeäksi graafin kärkien määrän kasvaessa. Erilaisten algoritmien yhdistäminen auttaa ratkaisemaan tämän ongelman [10] . Voidaan esimerkiksi käyttää Kamada-Kawai-algoritmia [11] hyväksyttävän alkusijoittelun nopeaan luomiseen ja sitten Fruchterman-Reinhold-algoritmia [12] parantamaan naapurisolmujen sijaintia. Toinen tekniikka globaalin minimin saamiseksi on käyttää monitasoista lähestymistapaa [13] .

Historia

Voimagraafin visualisointimenetelmät juontavat juurensa Tuttin työhön [14] jossa hän osoitti, että monitahoisia kuvaajia voidaan piirtää tasolle, jolla on kupera pinta kiinnittämällä tasograafin ulkopinnan kärjet upotettuna kuperaan asentoon , asettamalla jousi- kuten vetovoimat jokaisessa reunassa ja antavat järjestelmän tulla tasapainotilaan [15] . Voimien yksinkertaisen luonteen vuoksi järjestelmä ei tässä tapauksessa voi juuttua paikalliseen minimiin, vaan konvergoi yhteen globaaliin optimaaliseen konfiguraatioon. Tämän artikkelin valossa kuperapintaisten tasokaavioiden upotuksia kutsutaan joskus Tutt-upotuksiksi .

Eads [16] [17] käytti ensimmäisenä graafin vierekkäisten pisteiden vetovoimien ja kaikkien kärkien hylkimisvoimien yhdistelmää . Fruchterman ja Reingold julkaisivat toisen uraauurtavan työn tämäntyyppisestä voimansijoittelusta [18] . Ajatus käyttää vain jousivoimia kaikkien kärkiparien välillä, joiden ihanteellinen jousipituus on yhtä suuri kuin graafinen etäisyys, johtuu Kamadasta ja Kawaista [19] [11] .

Katso myös

  • Cytoscape , biologisen verkon visualisointiohjelma. Peruspaketti sisältää voimasijoitukset yhtenä sisäänrakennetuista menetelmistä.
  • Gephi , interaktiivinen visualisointi- ja tutkimusalusta kaikenlaisille verkoille ja monimutkaisille järjestelmille, dynaamisille ja hierarkkisille kaavioille.
  • Graphviz , ohjelmistotyökalu, joka toteuttaa monitasoisen voimansijoitusalgoritmin (muun muassa), joka pystyy käsittelemään erittäin suuria kuvaajia.
  • Tulip , ohjelmistotyökalu, joka toteuttaa useimmat voimansijoitusalgoritmit (GEM, LGL, GRIP, FM³).
  • Prefuse

Muistiinpanot

  1. ↑ Grandjean, 2015 , s. 109–128.
  2. ↑ Koburov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Chernobelskiy, Cunningham, Goodrich, Kobourov, Trott, 2011 , s. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , s. 163-180.
  6. ↑ Vose, Aaron 3D Phylogenetic Tree Viewer . Haettu: 3. kesäkuuta 2012.  (linkki, jota ei voi käyttää)
  7. ↑ Harel, Koren, 2002 , s. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , s. 197-210.
  9. ↑ Suurien kaavioiden galleria . Haettu 22. lokakuuta 2017. Arkistoitu alkuperäisestä 25. toukokuuta 2021.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , s. 77–86; Riisi. sivulla 212.
  11. ↑ 1 2 Kamada, Kawai, 1989 , s. 7-15.
  12. ↑ Fruchterman ja Reingold 1991 , s. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Arkistoitu 12. elokuuta 2021 Wayback Machinessa Monitasoinen algoritmi pakotettuun graafisen piirtämiseen
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , s. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , s. 149-160.
  18. ↑ Fruchterman ja Reingold 1991 , s. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Kirjallisuus

  • Martin Grandjean. Introduction à la visualization de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19 . – 2015.
  • Stephen G. Kobourov. Spring Embedders ja Force-Directed Graph Drawing Algoriths . - 2012. - . - arXiv : 1201.3011 .
  • Bannister M. J, Eppstein MJ, Goodrich MT, Trott L. Force-directed graph piirtäminen käyttäen sosiaalista painovoimaa ja skaalaus // Proc. 20th Int. Symp. kaavion piirustus. – 2012.
  • Chernobelskiy R., Cunningham K., Goodrich MT, Kobourov SG, Trott L. Voimaohjattu Lombardi-tyylinen graafipiirros // Proc. 19. symposium kaavioiden piirtämisestä . – 2011.
  • Jan de Leeuw. Pääsääntömenetelmän konvergenssi moniulotteiseen skaalaukseen // Journal of Classification. - Springer, 1988. - V. 5 , no. 2 . - S. 163-180 . - doi : 10.1007/BF01897162 .
  • David Harel, Yehuda Koren. Graafisten piirtäminen korkeadimensioisella upotuksella // 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 . Arkistoitu 21. toukokuuta 2006 Wayback Machinessa
  • Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. Järjestelmä ohjelmistokehityksen graafiseen visualisointiin // Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03) . - New York, NY, USA: ACM, 2003. - S. 77-86; luvut s. 212. - ISBN 1-58113-642-0 . doi : 10.1145 / 774833.774844 . Lainaus: Esteettisesti miellyttävän graafisen asettelun saamiseksi on tarpeen käyttää modifioituja Fruchterman-Reingold-voimia, koska Kamada-Kawai-menetelmä ei anna tyydyttäviä tuloksia, mutta luo hyvän likimääräisen asettelun, josta Fruchterman-Reingold-laskelmat voivat nopeasti "päättää" asettelua.
  • Tutte WT Kuinka piirtää kaavio // Proceedings of the London Mathematical Society. - 1963. - T. 13 , no. 52 . - doi : 10.1112/plms/s3-13.1.743 .
  • Peter Eades. Heuristinen graafinen piirtäminen // Congressus Numerantium. - 1984. - T. 42 , no. 11 .
  • Thomas MJ Fruchterman, Edward M. Reingold. Kaavion piirtäminen pakko-ohjatulla sijoittelulla // Ohjelmisto – Käytäntö ja kokemus. - Wiley, 1991. - T. 21 , no. 11 . - doi : 10.1002/spe.4380211102 .
  • Tomihisa Kamada, Satoru Kawai. Algoritmi yleisten suuntaamattomien graafien piirtämiseen // Information Processing Letters. - Elsevier, 1989. - T. 31 , no. 1 . - doi : 10.1016/0020-0190(89)90102-6 .

Lue lisää lukemista varten

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Kuvaajan piirtäminen: Algoritmit graafien visualisoimiseksi. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Graafisten piirtäminen: menetelmät ja mallit / Michael Kaufmann, Dorothea Wagner. - Springer, 2001. - (Luentomuistiinpanot tietojenkäsittelytieteessä 2025). - ISBN 978-3-540-42062-0 . - doi : 10.1007/3-540-44969-8 .

Linkki