Algoritmi de vizualizare a graficului de putere

Algoritmii de vizualizare a graficului de putere  sunt o clasă de algoritmi de vizualizare a graficului într-un mod plăcut din punct de vedere estetic. Scopul lor este de a aranja nodurile graficului în spațiu 2D sau 3D, astfel încât toate muchiile să aibă mai mult sau mai puțin aceeași lungime și de a minimiza numărul de intersecții ale muchiilor prin alocarea de forțe mai multor muchii și noduri pe baza pozițiilor lor relative și apoi folosind aceste forțe fie să simuleze mișcarea muchiilor și nodurilor, fie să minimizeze energia acestora [2] .

În timp ce vizualizarea graficelor poate fi o sarcină dificilă, algoritmii de forță, fiind modele fizice, de obicei nu necesită cunoștințe speciale în teoria graficelor, cum ar fi planaritatea graficului .

Forțe

Algoritmii de vizualizare a graficului de forță atribuie forțe asupra unui set de muchii și noduri ale unui grafic . Este obișnuit să se folosească forțe atractive asemănătoare arcurilor bazate pe legea lui Hooke pentru a atribui forțe perechilor de capete ale muchiei unui grafic. În același timp, forțele de respingere, similare cu respingerea particulelor încărcate electric bazate pe legea lui Coulomb , sunt folosite pentru a separa toate perechile de noduri. Pentru a obține o stare de echilibru a acestui sistem de forțe, muchiile tind să capete lungimi uniforme (datorită acțiunii arcurilor), iar nodurile care nu sunt legate printr-o muchie tind să fie situate la distanță unele de altele (datorită acţiunea forţelor de respingere). Forțele de atracție (nervuri) și forțele de respingere (noduri) pot fi definite folosind funcții care nu se bazează pe comportamentul fizic al arcurilor și particulelor. De exemplu, unele sisteme de alimentare folosesc arcuri ale căror forțe variază mai degrabă logaritmic decât liniar.

Un model alternativ ia în considerare forțele de tip arc pentru fiecare pereche de noduri în care lungimea ideală a fiecărui arc este proporțională cu distanța din grafic dintre nodurile i și j și nu sunt utilizate forțe de respingere. Minimizarea diferenței (de obicei, pătratul diferenței) dintre distanța euclidiană și ideală dintre noduri este echivalentă cu problema metricii de scalare multivariată .

Un grafic de forță poate folosi alte forțe decât arcurile mecanice și forțele de repulsie a sarcinii. O forță similară gravitației poate fi folosită pentru a trage vârfurile către un punct fix în spațiul de desenare a graficului. Acest lucru poate fi folosit pentru a reduce diferitele componente conectate ale unui graf deconectat într-un singur întreg, altfel aceste părți s-ar separa una de cealaltă sub acțiunea forțelor de respingere. De asemenea, vă permite să obțineți noduri cu o poziție centrală îmbunătățită în Figura [3] . Acest lucru poate afecta, de asemenea, distanța dintre vârfuri din aceeași componentă conectată. Analogii câmpurilor magnetice pot fi utilizați pentru graficele direcționate. Forțele de respingere pot fi plasate atât pe margini, cât și pe noduri pentru a evita suprapunerea sau aproape suprapunerea în desenul final. În desenele cu margini curbate, cum ar fi arce circulare sau spline , forțele pot fi, de asemenea, localizate în punctele de control ale acelor curbe, de exemplu, pentru a îmbunătăți rezoluția unghiulară [4] .

Metode

Odată ce forțele de la noduri și muchii sunt determinate, comportamentul întregului grafic sub aceste forțe poate fi modelat iterativ ca și cum ar fi un sistem fizic. Într-o astfel de situație, forțele care acționează asupra nodurilor încearcă să le tragă mai aproape sau să le împingă unul de celălalt. Aceasta continuă până când sistemul ajunge într-o stare de echilibru mecanic , adică poziția nodurilor nu se schimbă de la iterație la iterație. Poziția nodurilor în această stare de echilibru este utilizată pentru a genera desenul graficului.

Pentru forțele definite din arcuri a căror lungime ideală este proporțională cu distanța din grafic, majorarea tensiunilor dă un comportament foarte bun (adică, convergență monotonă ) [5] și o modalitate elegantă din punct de vedere matematic de a minimiza această diferență și, prin urmare, la o bună plasare a vârfurilor graficului.

De asemenea, puteți utiliza mecanisme care caută minimul de energie mai direct, decât după un model fizic. Astfel de mecanisme, care sunt exemple de tehnici generale de optimizare globală , includ recoacere simulată și algoritmi genetici .

Beneficii

Următoarele proprietăți sunt cele mai importante avantaje ale algoritmilor de forță:

Rezultate de bună calitate Cel puțin pentru graficele de dimensiuni medii (până la 50-500 de vârfuri), rezultatele obținute au de obicei modele grafice foarte bune pentru următoarele criterii: uniformitatea lungimii muchiilor, distribuția uniformă a vârfurilor și simetria. Ultimul criteriu este cel mai important și dificil de realizat în alte tipuri de algoritmi. Flexibilitate Algoritmii de forță pot fi ușor adaptați și extinși pentru criterii estetice suplimentare. Acest lucru face din algoritmi clase mai generale de algoritmi de vizualizare a graficelor. Exemple de extensii existente sunt algoritmii de grafice direcționate, vizualizarea grafică 3D [6] , vizualizarea grafică în cluster, vizualizarea grafică constrânsă și vizualizarea grafică dinamică. Intuitivitatea Deoarece algoritmii se bazează pe analogi fizici ai obiectelor familiare, cum ar fi arcurile, comportamentul algoritmilor este relativ ușor de prezis și de înțeles. Acest lucru nu se găsește în alte tipuri de algoritmi de vizualizare grafică. Simplitate Algoritmii tipici de forță sunt simpli și pot fi implementați în câteva linii de cod. Alte clase de algoritmi de randare, cum ar fi cei bazați pe plasări ortogonale, necesită de obicei mult mai multă muncă. interactivitate Un alt avantaj al acestei clase de algoritmi este aspectul de interactivitate. Desenând etapele intermediare ale graficului, utilizatorul poate urmări cum se modifică graficul, urmărind evoluția de la o mizerie dezordonată la o configurație arătătoare. În unele instrumente interactive de desenare grafică, utilizatorul poate renunța la unul sau mai multe noduri din starea de echilibru și poate urmări nodurile migrând la noua stare de echilibru. Acest lucru oferă algoritmilor un avantaj pentru sistemele de vizualizare grafică dinamică și online Sprijin teoretic strict În timp ce algoritmi simpli de forță apar adesea în literatură și în practică (pentru că sunt relativ simpli și de înțeles), numărul abordărilor mai rezonabile începe să crească. Statisticienii au rezolvat probleme similare în scalarea multidimensională ( MDS ) încă din anii  1930, iar fizicienii au, de asemenea, o istorie lungă de lucru cu probleme conexe de modelare a mișcării n corpuri , așa că există abordări destul de mature. Ca exemplu, abordarea majorării tensiunilor la MDS metrice poate fi aplicată vizualizării grafice, caz în care convergența monotonă poate fi demonstrată [5] . Convergența monotonă, proprietatea că algoritmul va reduce stresul sau costul plasării vârfurilor la fiecare iterație, este importantă deoarece asigură că plasarea ajunge în cele din urmă la un minim local și algoritmul se oprește. Oscilațiile de amortizare determină oprirea algoritmului, dar nu garantează că va fi atins un minim local adevărat.

Dezavantaje

Principalele dezavantaje ale algoritmilor de forță:

Timp de lucru grozav Algoritmii de forță tipici sunt în general considerați a avea timpi de rulare echivalenti cu O(n 3 ), unde n este numărul de noduri din graficul de intrare. Acest lucru se datorează faptului că numărul de iterații este estimat la O(n), iar la fiecare iterație este necesar să se analizeze toate perechile de noduri și să se calculeze forțele de respingere reciproce. Aceasta este similară cu problema N-corpilor din fizică. Cu toate acestea, deoarece forțele de respingere sunt de natură locală, graficul poate fi împărțit astfel încât să fie luate în considerare numai vârfurile învecinate. Principalele tehnici utilizate de algoritmi pentru a determina plasarea nodurilor în grafuri mari includ înglobări de dimensiuni mari [7] , reprezentări stratificate și alte tehnici legate de modelarea problemei n-corpuri . De exemplu, metoda FADE [8] bazată pe simularea Barnes-Hut poate îmbunătăți timpul de rulare la n*log(n) per iterație. Ca o estimare aproximativă, în câteva secunde vă puteți aștepta să desenați maximum 1000 de noduri cu tehnica standard n 2 per iterație și 100.000 cu tehnica n*log(n) per iterație [8] . Algoritmii de forță, atunci când sunt combinați cu o abordare stratificată, pot desena grafice cu milioane de noduri [9] . Minime locale proaste Este ușor de observat că algoritmul de forță oferă un grafic cu energie minimă, în special, poate fi doar un minim local . Minimul local constatat poate fi, în multe cazuri, semnificativ mai rău decât minimul global, ceea ce duce la o reprezentare de proastă calitate. Pentru mulți algoritmi, în special cei care permit doar mișcarea de coborâre în gradient , rezultatul final poate fi puternic influențat de poziția inițială, care este generată aleatoriu în majoritatea cazurilor. Problema unui minim local prost devine deosebit de importantă pe măsură ce numărul vârfurilor graficului crește. Combinarea diferiților algoritmi ajută la rezolvarea acestei probleme [10] . De exemplu, se poate folosi algoritmul Kamada-Kawai [11] pentru a genera rapid o plasare inițială acceptabilă, iar apoi algoritmul Fruchterman-Reinhold [12] pentru a îmbunătăți poziția nodurilor învecinate. O altă tehnică pentru obținerea unui minim global este utilizarea unei abordări multinivel [13] .

Istorie

Metodele de vizualizare a graficului de forță se întorc la lucrarea lui Tutt [14] în care el a arătat că graficele poliedrice pot fi desenate pe un plan cu fețe convexe prin fixarea vârfurilor feței exterioare a unui grafic plan încorporat într-o poziție convexă , plasând arc- ca forțele atractive pe fiecare muchie și permit sistemului să ajungă la o stare de echilibru [15] . Având în vedere natura simplă a forțelor, în acest caz sistemul nu poate rămâne blocat într-un minim local, ci converge către o singură configurație globală optimă. Având în vedere acest articol, înglobările de grafice plane cu fețe convexe sunt uneori numite înglobări Tutt .

Combinația de forțe atractive ale vârfurilor adiacente ale unui grafic și forțe de repulsie pentru toate nodurile a fost folosită pentru prima dată de Eads [16] [17] . O altă lucrare de pionierat asupra acestui tip de plasare a forței a fost publicată de Fruchterman și Reingold [18] . Ideea de a folosi doar forțele elastice între toate perechile de vârfuri cu lungimi ideale ale arcului egale cu distanța din grafic se datorează lui Kamada și Kawai [19] [11] .

Vezi și

  • Cytoscape , un program de vizualizare a rețelelor biologice. Pachetul de bază include plasări de forță ca una dintre metodele încorporate.
  • Gephi , platformă interactivă de vizualizare și explorare pentru tot felul de rețele și sisteme complexe, grafice dinamice și ierarhice.
  • Graphviz , un instrument software care implementează un algoritm de plasare a forței pe mai multe niveluri (printre altele) capabil să gestioneze grafice foarte mari.
  • Tulip , un instrument software care implementează majoritatea algoritmilor de plasare a forței (GEM, LGL, GRIP, FM³).
  • Prefuzare

Note

  1. ↑ Grandjean, 2015 , p. 109–128.
  2. ↑ Koburov, 2012 .
  3. ↑ Bannister, Eppstein, Goodrich, Trott, 2012 .
  4. ↑ Cernobelski, Cunningham, Goodrich, Kobourov, Trott, 2011 , p. 78–90.
  5. ↑ 1 2 de Leeuw, 1988 , p. 163-180.
  6. ↑ Vose, Aaron 3D Phylogenetic Tree Viewer . Preluat: 3 iunie 2012.  (link inaccesibil)
  7. ↑ Harel, Koren, 2002 , p. 207-219.
  8. ↑ 1 2 Quigley, Eades, 2001 , p. 197-210.
  9. ↑ O galerie de grafice mari . Preluat la 22 octombrie 2017. Arhivat din original la 25 mai 2021.
  10. ↑ Collberg, Kobourov, Nagra, Pitts, Wampler, 2003 , p. 77–86; Orez. la pagina 212.
  11. ↑ 1 2 Kamada, Kawai, 1989 , p. 7-15.
  12. ↑ Fruchterman și Reingold 1991 , p. 1129-1164.
  13. ↑ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Arhivat pe 12 august 2021 la Wayback Machine A Multilevel Algorithm for Force-Directed Graph-Drawing
  14. ↑ Tutte, 1963 .
  15. ↑ Tutte, 1963 , p. 743–768.
  16. ↑ Eades, 1984 .
  17. ↑ Eades, 1984 , p. 149–160.
  18. ↑ Fruchterman și Reingold 1991 , p. 1129-1164.
  19. ↑ Kamada, Kawai, 1989 .

Literatură

  • Martin Grandjean. Introduction à la visualization de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19 . — 2015.
  • Ştefan G. Kobourov. Spring Embedders și algoritmi de desenare a graficelor direcționate prin forță . - 2012. - Cod . - arXiv : 1201.3011 .
  • Bannister M. J, Eppstein MJ, Goodrich MT, Trott L. Desen grafic dirijat de forță folosind gravitatea socială și scalarea // Proc. 20 Int. Symp. desen grafic. — 2012.
  • Chernobelskiy R., Cunningham K., Goodrich MT, Kobourov SG, Trott L. Desen grafic în stil Lombardi dirijat de forță // Proc. Al 19-lea simpozion despre desenarea grafică . — 2011.
  • Jan de Leeuw. Convergența metodei majorizării pentru scalarea multidimensională // Journal of Classification. - Springer, 1988. - V. 5 , nr. 2 . - S. 163-180 . - doi : 10.1007/BF01897162 .
  • David Harel, Yehuda Koren. Desen grafic prin încorporare dimensională înaltă // 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 . Arhivat pe 21 mai 2006 la Wayback Machine
  • Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. Un sistem de vizualizare bazată pe grafice a evoluției software-ului // Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03) . - New York, NY, SUA: ACM, 2003. - S. 77-86; cifrele de la p. 212. - ISBN 1-58113-642-0 . doi : 10.1145 / 774833.774844 . Citat: Pentru a obține un aspect grafic plăcut din punct de vedere estetic, este necesar să se utilizeze forțe Fruchterman-Reingold modificate, deoarece metoda Kamada-Kawai nu dă rezultate satisfăcătoare, dar creează un aspect aproximativ bun din care calculele Fruchterman-Reingold se pot „termina” rapid. schema.
  • Tutte WT Cum se desenează un grafic // Proceedings of the London Mathematical Society. - 1963. - T. 13 , nr. 52 . - doi : 10.1112/plms/s3-13.1.743 .
  • Peter Eades. O euristică pentru desenarea grafică // Congressus Numerantium. - 1984. - T. 42 , nr. 11 .
  • Thomas MJ Fruchterman, Edward M. Reingold. Desen grafic prin plasare direcționată de forță // Software – Practică și experiență. - Wiley, 1991. - T. 21 , nr. 11 . - doi : 10.1002/spe.4380211102 .
  • Tomihisa Kamada, Satoru Kawai. Un algoritm pentru desenarea graficelor generale nedirecționate // Litere de procesare a informațiilor. - Elsevier, 1989. - T. 31 , nr. 1 . - doi : 10.1016/0020-0190(89)90102-6 .

Lectură pentru lecturi suplimentare

  • Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Desen grafic: algoritmi pentru vizualizarea graficelor. - Prentice Hall, 1999. - ISBN 978-0-13-301615-4 .
  • Desenarea graficelor: metode și modele / 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 .

Link