Power Graph Visualization Algoritmer

Effektgrafvisualiseringsalgoritmer  är en klass av grafvisualiseringsalgoritmer på ett estetiskt tilltalande sätt. Deras mål är att arrangera grafnoder i 2D- eller 3D-rymden så att alla kanter är mer eller mindre lika långa, och att minimera antalet kantskärningar genom att tilldela krafter till flera kanter och noder baserat på deras relativa positioner, och sedan genom att använda dessa krafter antingen för att simulera rörelsen av kanter och noder, eller för att minimera deras energi [2] .

Även om visualisering av grafer kan vara en svår uppgift, kräver kraftalgoritmer, eftersom de är fysiska modeller, vanligtvis inga speciella kunskaper i grafteori, såsom grafplanaritet .

Tvingar

Algoritmer för visualisering av kraftgrafer tilldelar krafter på en uppsättning kanter och noder på en graf . Det är vanligt att använda fjäderliknande attraktionskrafter baserade på Hookes lag för att tilldela krafter till par av ändar på en kant av en graf. Samtidigt används repulsiva krafter, liknande repulsionen av elektriskt laddade partiklar baserade på Coulombs lag , för att separera alla par av noder. För att erhålla ett jämviktstillstånd för detta kraftsystem tenderar kanterna att få enhetliga längder (på grund av fjädrarnas verkan), och de noder som inte är förbundna med en kant tenderar att vara belägna på avstånd från varandra (pga. verkan av frånstötande krafter). Attraktionskrafter (ribbor) och repulsiva krafter (knutar) kan definieras med hjälp av funktioner som inte är baserade på fjädrars och partiklars fysiska beteende. Till exempel använder vissa kraftsystem fjädrar vars krafter varierar logaritmiskt snarare än linjärt.

En alternativ modell tar hänsyn till fjäderliknande krafter för varje nodpar där den ideala längden för varje fjäder är proportionell mot avståndet i grafen mellan noderna i och j , och inga repulsiva krafter används. Att minimera skillnaden (vanligtvis kvadraten på skillnaden) mellan euklidiskt och idealiskt avstånd mellan noder är ekvivalent med det multivariata skalningsmetriska problemet .

En kraftgraf kan använda andra krafter än mekaniska fjädrar och laddningsrepulsionskrafter. En kraft som liknar gravitation kan användas för att dra hörn mot en fast punkt i grafritningsutrymmet. Detta kan användas för att reducera de olika sammankopplade komponenterna i en frånkopplad graf till en enda helhet, annars skulle dessa delar flyga isär från varandra under inverkan av frånstötande krafter. Det låter dig också få noder med en förbättrad central position i figur [3] . Detta kan också påverka avståndet mellan hörn i samma anslutna komponent. Analoger av magnetfält kan användas för riktade grafer. Avstötande krafter kan placeras på både kanter och noder för att undvika överlappning eller nästan överlappande i den slutliga ritningen. I ritningar med böjda kanter, såsom cirkulära bågar eller splines , kan krafter också placeras vid kontrollpunkterna för dessa kurvor, till exempel för att förbättra vinkelupplösningen [4] .

Metoder

När väl krafterna vid noderna och kanterna har bestämts, kan beteendet för hela grafen under dessa krafter iterativt modelleras som om det vore ett fysiskt system. I en sådan situation försöker krafterna som verkar på noderna dra dem närmare eller trycka bort dem från varandra. Detta fortsätter tills systemet kommer till ett tillstånd av mekanisk jämvikt , dvs nodernas position ändras inte från iteration till iteration. Positionen för noderna i detta jämviktstillstånd används för att generera ritningen av grafen.

För krafter definierade från fjädrar vars ideala längd är proportionell mot avståndet i grafen, ger spänningsmajorisering mycket bra beteende (d.v.s. monoton konvergens ) [5] och ett matematiskt elegant sätt att minimera denna skillnad och följaktligen till bra grafvertexplacering.

Du kan också använda mekanismer som letar efter energiminimum mer direkt, snarare än enligt en fysisk modell. Sådana mekanismer, som är exempel på generella globala optimeringstekniker , inkluderar simulerad annealing och genetiska algoritmer .

Fördelar

Följande egenskaper är de viktigaste fördelarna med kraftalgoritmer:

Bra kvalitetsresultat Åtminstone för medelstora grafer (upp till 50-500 hörn) har de erhållna resultaten vanligtvis mycket goda grafmönster för följande kriterier: enhetlighet av kantlängder, enhetlig fördelning av hörn och symmetri. Det sista kriteriet är det viktigaste och svåraste att uppnå i andra typer av algoritmer. Flexibilitet Force algoritmer kan enkelt anpassas och utökas för ytterligare estetiska kriterier. Detta gör algoritmer till mer allmänna klasser av grafvisualiseringsalgoritmer. Exempel på befintliga tillägg är riktade grafalgoritmer, 3D-grafvisualisering [6] , klustergrafvisualisering, begränsad grafvisualisering och dynamisk grafvisualisering. Intuitivitet Eftersom algoritmer är baserade på fysiska analoger av välbekanta objekt som fjädrar, är beteendet hos algoritmer relativt lätt att förutsäga och förstå. Detta finns inte i andra typer av grafvisualiseringsalgoritmer. Enkelhet Typiska kraftalgoritmer är enkla och kan implementeras i några rader kod. Andra klasser av renderingsalgoritmer, såsom de som baseras på ortogonala placeringar, kräver vanligtvis mycket mer arbete. interaktivitet En annan fördel med denna klass av algoritmer är aspekten av interaktivitet. Genom att rita grafens mellanstadier kan användaren följa hur grafen förändras och spåra utvecklingen från en rörig röra till en snygg konfiguration. I vissa interaktiva grafritningsverktyg kan användaren ta bort en eller flera noder från jämviktstillståndet och se noderna migrera till det nya jämviktstillståndet. Detta ger algoritmerna en fördel för dynamiska och online grafvisualiseringssystem. Strikt teoretiskt stöd Medan enkla kraftalgoritmer ofta förekommer i litteraturen och i praktiken (eftersom de är relativt enkla och begripliga), börjar antalet mer rimliga tillvägagångssätt att öka. Statistiker har löst liknande problem inom multidimensionell skalning ( MDS ) sedan  1930-talet, och fysiker har också en lång historia av att arbeta med relaterade problem med att modellera rörelsen av n kroppar , så det finns ganska mogna tillvägagångssätt. Som ett exempel kan stressmajoriseringsmetoden för metrisk MDS tillämpas på grafvisualisering, i vilket fall monoton konvergens kan bevisas [5] . Monotonisk konvergens, egenskapen att algoritmen kommer att minska stressen eller kostnaden för att placera hörn vid varje iteration, är viktig eftersom den säkerställer att placeringen så småningom når ett lokalt minimum och att algoritmen stannar. Dämpande svängningar gör att algoritmen stannar, men garanterar inte att ett verkligt lokalt minimum uppnås.

Nackdelar

De största nackdelarna med kraftalgoritmer:

Bra arbetstid Typiska kraftalgoritmer anses generellt ha körtider motsvarande O(n 3 ), där n är antalet noder i ingångsgrafen. Detta beror på att antalet iterationer uppskattas till O(n), och vid varje iteration är det nödvändigt att titta på alla par av noder och beräkna de inbördes repulsiva krafterna. Detta liknar N-kroppsproblemet i fysiken. Men eftersom de frånstötande krafterna är lokala till sin natur, kan grafen delas upp så att endast närliggande hörn beaktas. De huvudsakliga teknikerna som används av algoritmer för att bestämma placeringen av noder i stora grafer inkluderar högdimensionella inbäddningar [7] , skiktade representationer och andra tekniker relaterade till modellering av n-kroppsproblemet . Till exempel kan FADE-metoden [8] baserad på Barnes-Hut -simuleringen förbättra körtiden till n*log(n) per iteration. Som en grov uppskattning kan du på några sekunder förvänta dig att rita maximalt 1000 noder med standard n 2 -tekniken per iteration och 100 000 med n*log(n)-tekniken per iteration [8] . Kraftalgoritmer, i kombination med en skiktad strategi, kan rita grafer med miljontals noder [9] . Dåliga lokala minima Det är lätt att se att kraftalgoritmen ger en graf med minimal energi, i synnerhet kan den bara vara ett lokalt minimum . Det hittade lokala minimumet kan i många fall vara betydligt sämre än det globala minimumet, vilket leder till en dålig representation. För många algoritmer, särskilt de som endast tillåter gradientnedstigning , kan slutresultatet påverkas kraftigt av den initiala positionen, som genereras slumpmässigt i de flesta fall. Problemet med ett dåligt lokalt minimum blir särskilt viktigt när antalet grafens hörn växer. Att kombinera olika algoritmer hjälper till att lösa detta problem [10] . Till exempel kan man använda Kamada-Kawai-algoritmen [11] för att snabbt generera en acceptabel initial placering, och sedan Fruchterman-Reinhold-algoritmen [12] för att förbättra positionen för närliggande noder. En annan teknik för att erhålla ett globalt minimum är att använda en multilevel approach [13] .

Historik

Visualiseringsmetoder för kraftgrafer går tillbaka till Tutts arbete [14] där han visade att polyedriska grafer kan ritas på ett plan med konvexa ytor genom att fixera hörnen på den yttre ytan av en plan graf som är inbäddad i en konvex position , placera fjäder- gillar attraktionskrafter på varje kant och låter systemet komma till ett jämviktstillstånd [15] . Med tanke på krafternas enkla natur kan systemet i detta fall inte fastna i ett lokalt minimum, utan konvergerar till en enda global optimal konfiguration. Med tanke på den här artikeln kallas ibland inbäddningar av plana grafer med konvexa ytor Tutt-inbäddningar .

Kombinationen av attraktionskrafter av angränsande hörn av en graf och repulsiva krafter för alla hörn användes först av Eads [16] [17] . Ett annat banbrytande arbete om denna typ av kraftplacering publicerades av Fruchterman och Reingold [18] . Idén att endast använda fjäderkrafter mellan alla par av hörn med ideala fjäderlängder lika med grafavståndet beror på Kamada och Kawai [19] [11] .

Se även

  • Cytoscape , ett biologiskt nätverksvisualiseringsprogram. Baspaketet innehåller kraftplaceringar som en av de inbyggda metoderna.
  • Gephi , interaktiv visualisering och utforskningsplattform för alla typer av nätverk och komplexa system, dynamiska och hierarkiska grafer.
  • Graphviz , ett mjukvaruverktyg som implementerar en kraftplaceringsalgoritm på flera nivåer (bland andra) som kan hantera mycket stora grafer.
  • Tulip , ett mjukvaruverktyg som implementerar de flesta kraftplaceringsalgoritmer (GEM, LGL, GRIP, FM³).
  • Prefuse

Anteckningar

  1. ↑ Grandjean, 2015 , sid. 109–128.
  2. ↑ Koburov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Chernobelskiy, Cunningham, Goodrich, Kobourov, Trott, 2011 , sid. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , sid. 163-180.
  6. ↑ Vose, Aaron 3D Phylogenetic Tree Viewer . Hämtad: 3 juni 2012.  (otillgänglig länk)
  7. ↑ Harel, Koren, 2002 , sid. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , sid. 197-210.
  9. ↑ Ett galleri med stora grafer . Hämtad 22 oktober 2017. Arkiverad från originalet 25 maj 2021.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , sid. 77–86; Ris. på sidan 212.
  11. ↑ 1 2 Kamada, Kawai, 1989 , sid. 7-15.
  12. ↑ Fruchterman och Reingold 1991 , sid. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Arkiverad 12 augusti 2021 på Wayback Machine A Multilevel Algorithm for Force-Directed Graph-Drawing
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , sid. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , sid. 149–160.
  18. ↑ Fruchterman och Reingold 1991 , sid. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Litteratur

  • Martin Grandjean. Introduktion à la visualization de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19 . — 2015.
  • Stephen G. Kobourov. Spring Embedders och Force-Directed grafritningsalgoritmer . - 2012. - . - arXiv : 1201.3011 .
  • Bannister M. J, Eppstein MJ, Goodrich MT, Trott L. Kraftriktad grafritning med social gravitation och skalning // Proc. 20:e Int. Symp. grafritning. — 2012.
  • Chernobelskiy R., Cunningham K., Goodrich MT, Kobourov SG, Trott L. Force-directed Lombardi-stil grafritning // Proc. 19:e symposiet om grafritning . — 2011.
  • Jan de Leeuw. Konvergens av majoriseringsmetoden för flerdimensionell skalning // Journal of Classification. - Springer, 1988. - V. 5 , nr. 2 . - S. 163-180 . - doi : 10.1007/BF01897162 .
  • David Harel, Yehuda Koren. Grafritning genom högdimensionell inbäddning // 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 . Arkiverad 21 maj 2006 på Wayback Machine
  • Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. Ett system för grafbaserad visualisering av mjukvaruutvecklingen // Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03) . - New York, NY, USA: ACM, 2003. - S. 77-86; siffror på sid. 212. - ISBN 1-58113-642-0 . doi : 10.1145 / 774833.774844 . Citat: För att få en estetiskt tilltalande graflayout är det nödvändigt att använda modifierade Fruchterman-Reingold-krafter, eftersom Kamada-Kawai-metoden inte ger tillfredsställande resultat, men skapar en bra ungefärlig layout från vilken Fruchterman-Reingolds beräkningar snabbt kan "sluta" layouten.
  • Tutte WT Hur man ritar en graf // Proceedings of the London Mathematical Society. - 1963. - T. 13 , nr. 52 . - doi : 10.1112/plms/s3-13.1.743 .
  • Peter Eades. En heuristik för grafritning // Congressus Numerantium. - 1984. - T. 42 , nr. 11 .
  • Thomas MJ Fruchterman, Edward M. Reingold. Grafritning efter tvångsriktad placering // Programvara – övning och erfarenhet. - Wiley, 1991. - T. 21 , nr. 11 . - doi : 10.1002/spe.4380211102 .
  • Tomihisa Kamada, Satoru Kawai. En algoritm för att rita allmänna oriktade grafer // Information Processing Letters. - Elsevier, 1989. - T. 31 , nr. 1 . - doi : 10.1016/0020-0190(89)90102-6 .

Läsning för vidare läsning

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Grafritning: Algoritmer för visualisering av grafer. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Rita grafer: metoder och modeller / Michael Kaufmann, Dorothea Wagner. - Springer, 2001. - (Lecture Notes in Computer Science 2025). - ISBN 978-3-540-42062-0 . - doi : 10.1007/3-540-44969-8 .

Länk