Silom usmereno crtanje grafova

Vizualizacija veza između stranica na Vikipediji koji koristi silom usmereni raspored.

Algoritmi za usmereno crtanje grafova su klasa algoritama za crtanje grafova na estetski najpogodniji način. Njihova uloga je da pozicioniraju čvorove grafa u dvodimenzionalnom ili trodimenzionalnom prostoru, ali tako da su ivice približno jednakih dužina i da ih je što manje, koristeći sile između postavljenih ivica i postavljenih čvorova, bazirane na njihovoj relativnoj poziciji, koje se mogu koristiti za kretanje između ivica i čvorova, ili za minimizaciju njihovih energija.

Dok crtanje grafova može biti težak problem, algoritmi za silom usmereno crtanje grafova, predstavljaju fizičku simulaciju i obično ne zahtevaju specijalno znanje o teoriji grafova kao planimetrija.

Sile

Algoritmi za silom usmereno crtanje grafova dodeljuju sile između ivica i između čvorova prilikom crtanja grafova. Obično, privlačne sile slične opruzi bazirane na Hukovom zakonu, se koriste da međusobno privuku par krajnjih tačaka sa ivica grafa, dok istovremeno odbojne sile poput čestica sa električnim nabojem, bazirane na Kulonovom zakonu, se koriste da razdvoje sve parove čvorova. U stanju ravnoteže ovog sistema sila, ivice teže da imaju propisanu dužinu (zbog sila sličnih opruzi), i čvorovi koji nisu povezani ivicama teže da budu što dalje (zbog električnog odbijanja). Privlačenje ivica i sile za odbijanje najviše tačke mogu biti definisane koristeći funkcije koje nisu bazirane na fizičkom ponašanju opruge i čestica; Na primer: Neki prinudni sistemi koriste sredstva čije su privlačne sile više logaritamske nego linearne.

Alternativni model razmatra silu sličnu opruzi za svaki par čvorova $(i,j)$, gde je savršena dužina ${\delta }_{ij}$ svake opruge proporcionalna dužini definisanoj teoriji grafova između čvorova i i j, ne koristeći odbojne sile. Minimizacija razlike (obično razlike kvadrata) između Euklidovog i idealnog rastojanja između čvorova je ekvivalentna metričkom multidimenzionom skalirajućem problemu.

Silom usmereni graf može obuhvatiti i druge sile osim mehaničkih opruga i električnog odbijanja. Sila analogna gravitaciji može biti korištena da privuče temena ka fiksiranim tackama u prostoru crtanja i može biti korištena da privuče zajedno različite povezane komponente nepovezanog grafa, koje bi inače težile da lebde jedna između druge zbog odbojnih sila, i prilikom nacrta čvorova sa velikom centralnošću ka centralnoj poziciji u crtanju; to takođe može uticati na prostor najviših temena unutar jedinstvene komponente. Analozi magnetnih polja mogu biti korišteni za direktne grafove, odbojne sile, takođe mogu biti pozicionirani na ivicama kao i na čvorovima jedan po jedan, u redosledu da bi se izbeglo preklapanje ili približno preklapanje u konačnom crtanju. U crtežima sa zaobljenim ivicama kao sto je kružni luk ili dugačka kriva, sile mogu takođe biti postavljene na kontrolne tačke ovih krivih, na primer da poboljšaju njihovu rezoluciju uglova.

Metode

Jednom kada su sile čvorova i ivica grafa definisane, ponašanje čitavog grafa ispod ovih izvora može biti simulirano kao da je to bio fizički sistem. U takvoj simulaciji sile su primenjene na čvorove, njihovim povlačenjem blize ili guranjem dalje. Ovo je ponavljano iterativno dok sistem ne dođe u stanje maganičke ravnoteže; tj njihove relativne pozicije se više ne menjaju od jedne iteracije do druge. Pozicija čvorova u ovoj ravnoteži se koristi da generiše crtež grafa.

Za sile definisane kao opruga čija je idealna dužina proporcijalna dužini u teoriji grafova, pritisak majorizacije daje veoma učtiv (tj monotono konvergentan) i matematički korektan način za minimizaciju ovih razlika i, stoga, nalazi dobar raspored za graf.
Takođe je moguće upotrebiti mehanizam koji direktnije traži energiju minimuma, umesto ili u vezi sa fizičkom simulacijom. Takvi mehanizmi, koji su primeri metoda generalne globalne optimizacije, uključuju probabilističku tehniku i genetske algoritme.

Prednosti

Sledeće su među najvažnijim prednostima silom usmerenih algoritama:

Kvalitetni rezultati

Bar za grafove srednjih dimenzija (od 50-500 temena), dobijeni rezultati obično imaju veoma dobar uspeh baziran na sledećim kriterijumima: ujednačena dužina ivica, ujednačena podela najviše tačke i prikazane simetrije. Ovaj poslednji kriterijum je među najvažnijim i teško ga je postići sa bilo kojom drugom vrstom algoritma.

Fleksibilnost

Silom usmereni algoritmi mogu biti lako prilagođeni i dopunjeni da ispune dodatni estetski kriterijum. Ovo ih pravi najsvestranijom klasom algoritama za crtanje grafova. Primeri postojećih dopuna uključuju one za direktne grafove, 3D crtanje grafova,Шаблон:Чињеница klaster crtež grafa, ograničeno crtanje grafa,i dinamičko crtanje grafa.

Intuicija

Posto su oni bazirani na fizičkim analozima običnih objekata, kao opruga, ponašanje algoritama je relativno jednostavno predvideti i razumeti. Ovo nije slučaj sa drugim tipovima algoritama za crtanje grafa.

Jednostavnost

Tipični silom usmereni algoritmi su jednostavni i mogu biti implementirani u nekoliko linija koda. Druge klase algoritama za crtanje grafa kao one za ortogonalan raspored, su obično mnogo više zapetljane.

Interaktivnost

Druge prednosti ove klase algoritama su interaktivno gledište. U srednjim fazama crtanja grafa, korisnik može pratiti kako graf evoluira, gledajući to odvojeno od zamršenog nereda, u zgodnoj konfiguraciji. U nekim interaktivnim sredstvima za crtanje grafova, korisnik može povuci jedan ili više čvorova izvan njihovog stanja ravnoteže i može posmatrati kako se vraćaju nazad u poziciju. Ovo im omogućava izbor za dinamičke i onlajn sisteme za crtanje grafova.

Jaki teoretski temelji

Dok se jednostavni brzi silom usmereni algoritmi obično pojavljuju u literaturi i u praksi (zato što su relativno jednostavni za razumevanje) više razumni pristupi počinju da privlače pažnju. Statističari su rešavali slične probleme u dimenzionalnom skaliranju (-{MDS}-) još 1930, i fizičari takođe imaju dugu istoriju rada sa povezanim problemima n-tela, pa ekstremno zreli pristupi postoje.Kao primer, pritisak majorizacije koji pristupa metričkom MDS-u može biti primenjen za crtanje grafa kao što je opisano gore. Ovo je dokazano da konvergira monotono. Monotona konvergencija, osobina da ce algoritam u svakoj iteraciji smanjivati pritisak ili cenu rasporeda, je važan zato što garantuje da će raspored eventualno dostići lokalni minimum i stati. -{Damping }- raspored uzrokuje da algoritam stane, ali ne može garantovati da je pravi lokalni minimum dostignut.

Mane

Glavne mane silom usmerenih algoritama uključuju sledeće:

Dugačko vreme izvršavanja

Tipični silom usmereni algoritmi se generalno posmatraju kao da imaju vreme izvršavanja jednako $O(n^3)$, gde je -{n}- broj čvorova ulaznog grafa.To je zato što je procenjeno da broj iteracija bude $O(n)$, i u svakoj iteraciji, svi parovi čvorova moraju da budu posečeni i njihove uzajamno odbojne sile izračunate. Ovo je povezano sa -{n-body}- problemom u fizici. Međutim dok su odbojne sile lokalne po prirodi graf može biti podeljen tako da su samo susedni vrhovi razmatrani. Opšte tehnike korištene u algoritmima za određivanje rasporeda velikih grafova uključuju visoko dimenzionalno ugrađivanje, višeslojno crtanje i druge metode povezane sa -{n-body}- simulacijom. Na primer Bern-Hatova simulacija - zasnovana metoda -{FADE}- može poboljšati vreme izvršavanja do $n*log(n)$ po iteraciji. Kao grubo prevođenje, u nekoliko sekundi od jednog se može očekivati da nacrta najviše 1000 čvorova sa standardom $n^2$ po iteraciji. Silom usmereni algoritam, kada je kombinovan sa višestepenim pristupom, može nacrtati graf sa milionima čvorova.

Slab lokalni minimum

Jednostavno je videti da silom usmereni algoritmi stvaraju graf sa minimalno energije, naročito one čija je totalna energija jedino lokalni minimum. Lokalni minimum može biti, u mnogim slučajevima, znatno gori nego globalni minimum, koji se pretvara u nisko-kvalitetno crtanje. Za mnoge algoritme, naročito one koji dopuštaju jedino strme pokrete temena, konačni rezultat može biti snažno uzrokovan početnim rasporedom, koji je u većini slučajeva slučajno generisan. Problem slabog lokalnog minimuma postaje značajniji kako broj temena grafa raste. Kombinovana primena različitih algoritama je od pomoći za rešavanje ovog problema. Na primer, koristeći Kamada-Kavaji algoritam za brzo generisanje razumnog početnog rasporeda i zatim Fruktenman-Reingold algoritam da poboljša položaj susednih čvorova. Druge tehnike za postizanje globalnog minimuma su korištenje višestepenog pristupa.

Istorija

Silom usmerene metode za crtanje grafova datiraju od rada Шаблон:Harvnb, koji je pokazao da poliedarski grafovi mogu biti nacrtani u području sa svim konveksnim licima fiksiranjem temena na spoljašnja lica ugrađenog planarnog grafa na konveksnu poziciju, postavljanjem privlačne sile slične opruzi na svaku ivicu i postavljanjem ustaljenog sistema u ravnotežu. Zbog jednostavne prirode sila u ovom slučaju, sistem ne može biti zaglavljen u lokalnom minimumu, ali utoliko pre konvergira optimalnoj globalnoj konfiguraciji. Zbog ovoga ugrađivanje planarnih grafova sa konveksnim licima je ponekad zvano Tutovo ugrađivanje. Kombinaciju privlačnih sila na susednim temenima, i odbojnih sila na svim temenima je najpre koristio Шаблон:Harvnb; dodatni pionirski rad na ovoj vrsti silom usmerenog rasporeda je urađeno od strane Шаблон:Harvnb. Ideja korištenja samo sila opruge između svih parova temena, sa idealnim silama opruge jednakim rastojanju temena u teoriji grafova, je od Шаблон:Harvnb.

Vidi još

• Citoscape, softver za vizualizaciju bioloških mreža. Osnovni paket uključuje silom usmerene rasporede kao jednu od gradivnih metoda.
• Gephi, interaktivna vizualizacija i istraživačka platforma za sve vrste mreža i kompleksnih sistema, dinamičkih i hijerarhijskih grafova.
• Graphviz, softver koji izvršava algoritam višestepenog silom usmerenog rasporeda (između mnogih ostalih) sposoban da rukuje veoma velikim grafovima,
• Tulipsoftver, koji implementira većinu algoritama silom usmerenog rasporeda(-{GEM}-, -{LGL}-, -{GRIP}-, -{FM}-).
• Prefuse
• LearnDiscavery, mobilni softver za IOS koji vizualizuje mapu uma engleske Wikipedije procenjen kao opterećen graf. To uključuje silom usmerene rasporede kao jednu od gradivnih metoda za prikazivanje i pristupanje povezanom grafu iz teme.

Literatura

• Шаблон:Citation
• Шаблон:Citation

Spoljašnje veze

• Шаблон:Cite web [dead link as of 27 May 2016]
• Live visualisation in flash + source code and description
• Daniel Tunkelang's dissertation (with source code and demonstration applet) on force-directed graph layout
• Hyperassociative Map Algorithm
• Interactive and real-time force-directed graphing algorithms used in an online database modeling tool