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 .
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] .
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ö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.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] .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] .