Силові́ алгори́тми візуаліза́ції гра́фів — клас алгоритмів візуалізації графів у естетично приємному вигляді. Їх мета — розмістити вузли графа в двовимірному або тривимірному просторі так, щоб усі ребра мали б більш-менш однакову довжину, і звести до мінімуму число перетинів ребер, призначивши сили для множини ребер і вузлів, ґрунтуючись на їх відносних положеннях, а потім використовуючи ці сили або для моделювання руху ребер і вузлів, або для мінімізації їх енергії.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHlMekl5TDFOdlkybGhiRTVsZEhkdmNtdEJibUZzZVhOcGN5NXdibWN2TWpVd2NIZ3RVMjlqYVdGc1RtVjBkMjl5YTBGdVlXeDVjMmx6TG5CdVp3PT0ucG5n.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODVMemt3TDFacGMzVmhiR2w2WVhScGIyNWZiMlpmZDJscmFWOXpkSEoxWTNSMWNtVmZkWE5wYm1kZmNISmxablZ6WlY5MmFYTjFZV3hwZW1GMGFXOXVYM0JoWTJ0aFoyVXVjRzVuTHpJMU1IQjRMVlpwYzNWaGJHbDZZWFJwYjI1ZmIyWmZkMmxyYVY5emRISjFZM1IxY21WZmRYTnBibWRmY0hKbFpuVnpaVjkyYVhOMVlXeHBlbUYwYVc5dVgzQmhZMnRoWjJVdWNHNW4ucG5n.png)
Тоді як візуалізація графів може виявитися складною задачею, силові алгоритми, як фізичні моделі, зазвичай не вимагають спеціальних знань з теорії графів, таких як планарність графа.
Сили
Силові алгоритми візуалізації графів призначають сили на множині ребер та вузлів графа. Зазвичай використовують сили притягання, подібні до пружинних, на основі закону Гука для призначення сил парам кінців ребер графа. Разом з тим, щоб розділити всі пари вузлів, використовують сили відштовхування, подібні до відштовхування електричних зарядів на основі закону Кулона. Для отримання рівноважного стану цієї системи сил ребра прагнуть набути однорідних довжин (через дію пружин), а вузли, не пов'язані ребром, прагнуть віддалитися один від одного (через дію сил відштовхування). Сили притягання (ребра) та сили відштовхування (вузли) можна визначити за допомогою функцій, які не засновані на фізичній поведінці пружин та частинок. Наприклад, деякі силові системи використовують пружини, сили яких змінюються логарифмічно, а не лінійно.
Альтернативна модель розглядає сили, подібні до пружинних, для кожної пари вузлів , де ідеальна довжина
кожної пружини пропорційна відстані у графі між вузлами i і j, а сили відштовхування не використовуються. Мінімізація різниці (зазвичай, квадрата різниці) між евклідовою та ідеальною відстанню між вузлами еквівалентна метричній задачі багатовимірного шкалювання.
Силовий граф може використовувати сили, відмінні від механічних пружин та сил відштовхування зарядів. Силу, аналогічну гравітації, можна використати для тяжіння вершин у бік фіксованої точки простору малювання графа. Це можна використати для зведення різних компонент зв'язності незв'язного графа в одне ціле, інакше ці частини розлетілися б одна від одної під дією сил відштовхування. Також це дозволяє краще центрувати вузли на малюнку. Це також може вплинути на відстань між вершинами одного компонента зв'язності. Для орієнтованих графів можна використовувати аналоги магнітних полів. Щоб уникнути накладення або майже накладення на кінцевому малюнку, як на ребрах, так і на вузлах можна розташувати сили відштовхування. На малюнках з кривими ребрами, такими як дуги кіл або сплайни, сили можуть розташовуватися в контрольних точках цих кривих, наприклад, щоб поліпшити кутову роздільність .
Методи
Як тільки сили на вузлах і ребрах визначено, поведінку всього графа під дією цих сил можна ітеративно промоделювати, подібно до поведінки фізичної системи. У такій ситуації сили, що діють на вузли, намагаються стягнути їх ближче або відштовхнути їх один від одного. Це триває, поки система не набуде стану механічної рівноваги, тобто припиниться змінення положення вузлів від ітерації до ітерації. Положення вузлів у цьому стані рівноваги використовують для побудови малюнка графа.
Для сил, визначених пружинами, ідеальна довжина яких пропорційна відстані в графі, мажорування стресу дає дуже хорошу поведінку (тобто монотонну збіжність) і математично елегантний шлях мінімізації цієї різниці і, отже, до хорошого розміщення вершин графа.
Можна також використати механізми, які шукають мінімум енергії пряміше, а не за фізичною моделлю. До таких механізмів, які є прикладами загальних методів глобальної оптимізації, належать імітація відпалу і генетичні алгоритми.
Переваги
Важливими перевагами силових алгоритмів є такі властивості:
- Результати хорошої якості
- Щонайменше для графів середнього розміру (до 50-500 вершин), отримані результати зазвичай мають дуже хороші малюнки графів за такими критеріями: однорідність довжин ребер, рівномірний розподіл вершин і симетрія. Останній критерій найважливіший і важкодосяжний в інших алгоритмах.
- Гнучкість
- Силові алгоритми можна легко пристосувати і розширити для додаткових естетичних критеріїв. Це робить алгоритми універсальнішими. Прикладами існуючих розширень є алгоритми для орієнтованих графів, візуалізація тривимірних графів, кластерна візуалізація графів, візуалізація графів з обмеженнями і динамічна візуалізація графів.
- Інтуїтивність
- Оскільки алгоритми засновані на фізичних аналогах звичних об'єктів, на зразок пружин, поведінку алгоритмів відносно просто передбачити і зрозуміти. Цього немає в інших алгоритмах візуалізації графів.
- Простота
- Типові силові алгоритми прості і можуть бути реалізовані кількома рядками коду. Інші класи алгоритмів візуалізації, такі як алгоритми на основі ортогональних розміщень, зазвичай вимагають значно більше роботи.
- Інтерактивність
- Ще однією перевагою цього класу алгоритмів є аспект інтерактивності. При малюванні проміжних етапів графа користувач може спостерігати, як змінюється граф, простежуючи еволюцію від безладного місива до гарної конфігурації. У деяких засобах інтерактивного малювання графа користувач може відсунути один або кілька вузлів зі стану рівноваги і спостерігати міграцію вузлів у новий стан рівноваги. Це дає алгоритмам перевагу для динамічних і онлайнових систем візуалізації графів.
- Строга теоретична підтримка
- Тоді як прості силові алгоритми часто з'являються в літературі і на практиці (оскільки вони відносно прості і зрозумілі), починає зростати число обгрунтованіших підходів. Статистики розв'язували подібні задачі в багатовимірному шкалюванні (БВШ, англ. multidimensional scaling) з 1930-х років, фізики також мають довгу історію роботи з пов'язаними задачами моделювання руху n тіл, так що існують цілком зрілі підходи. Як приклад, підхід мажорування стресу до метричних БВШ можна застосувати для візуалізації графа і в цьому випадку можна довести монотонну збіжність. Монотонна збіжність, властивість, що алгоритм буде на кожній ітерації зменшувати напругу або ціну розміщення вершин, важлива, оскільки це гарантує, що розміщення, зрештою, досягне локального мінімуму і алгоритм зупиниться. Глушіння коливань призводить до зупинки алгоритму, але не гарантує, що буде досягнуто істинного локального мінімуму.
Недоліки
Головні недоліки силових алгоритмів:
- Великий час роботи
- Вважається, що типові силові алгоритми в загальному випадку мають час роботи, еквівалентний
, де n — число вузлів вхідного графа. Це тому, що число ітерацій оцінюється в
, а на кожній ітерації необхідно переглянути всі пари вузлів і обчислити взаємні сили відштовхування. Це схоже на задачу N-тіл у фізиці. Однак, оскільки сили відштовхування локальні за природою, граф можна розбити так, що будуть розглядатися тільки сусідні вершини. Основні техніки, використані в алгоритмах для визначення розміщення вузлів великих графів, включають вкладення високої розмірності, багаторівневі подання та інші методи, пов'язані з моделюванням задачі n тіл. Наприклад, заснований на моделюванні Барнса-Хата метод FADE може поліпшити час роботи до
на ітерацію. Груба оцінка: за кілька секунд можна очікувати малювання максимум 1000 вузлів у стандартній техніці
на ітерацію і 100 000 з технікою
на ітерацію. Силові алгоритми, у комбінації з багаторівневим підходом, можуть малювати графи з мільйонами вузлів.
- Погані локальні мінімуми
- Легко бачити, що силовий алгоритм дає граф із мінімальною енергією, зокрема, це може бути лише локальний мінімум. Знайдений локальний мінімум може бути, у багатьох випадках істотно гіршим від глобального мінімуму, що призводить до низької якості подання. Для багатьох алгоритмів, особливо для тих, які дозволяють тільки рух градієнтного спуску, на кінцевий результат може дуже впливати початкове положення, яке в більшості випадків генерується випадково. Проблема поганого локального мінімуму стає особливо важливою при зростанні числа вершин графа. Комбінування різних алгоритмів допомагає вирішити цю проблему. Наприклад, для швидкого генерування прийнятного початкового розміщення можна використати алгоритм Камади — Каваї, а потім поліпшити положення сусідніх вузлів за алгоритмом Фрухтермана — Рейнгольда. Інша техніка отримання глобального мінімуму — використання багаторівневого підходу .
Історія
Силові методи візуалізації графів сходять до роботи Татта, в якій він показав, що поліедральні графи можна намалювати на площині з опуклими гранями, зафіксувавши вершин зовнішньої грані планарного вкладення графа в [en], розташувавши пружиноподібні сили притягання на кожному ребрі і дозволивши системі прийти в рівноважний стан. Зважаючи на просту природу сил у цьому випадку система не може застрягти в локальному мінімумі, а збігається до єдиної глобальної оптимальної конфігурації. Зважаючи на цю статтю, вкладення планарних графів із опуклими гранями іноді називають вкладеннями Татта.
Комбінацію сил притягання суміжних вершин графа і сил відштовхування для всіх вершин першим використав Ідс. Ще одну піонерську роботу щодо цього типу силового розміщення опублікували Фрухтерман і Рейнгольд. Ідея використання між усіма парами вершин лише сил пружин з ідеальними довжинами пружин, рівними відстані по графу, належить Камаді і Каваї.
Див. також
- [ru] — програма для візуалізації біологічних мереж. Базовий пакет включає силові розміщення як один із вбудованих методів.
- Gephi — інтерактивна візуалізація та дослідницька платформа exploration для всіх видів мереж та складних систем, динамічних та ієрархічних графів.
- Graphviz — програмний засіб, що реалізує багаторівневий силовий алгоритм розміщення (серед інших), здатний обробляти дуже великі графи.
- [en] — програмний засіб, що реалізує більшість силових алгоритмів розміщення (GEM, LGL, GRIP, FM3).
- [en]
Примітки
- Grandjean, 2015, с. 109–128.
- Kobourov, 2012.
- Bannister, Eppstein, Goodrich, Trott, 2012.
- Chernobelskiy, Cunningham, Goodrich, Kobourov, Trott, 2011, с. 78–90.
- de Leeuw, 1988, с. 163—180.
- Vose, Aaron. . Архів оригіналу за 10 серпня 2015. Процитовано 27 квітня 2022.
- Harel, Koren, 2002, с. 207—219.
- Quigley, Eades, 2001, с. 197—210.
- A Gallery of Large Graphs. Процитовано 22 жовтня 2017.
- Collberg, Kobourov, Nagra, Pitts, Wampler, 2003, с. 77–86; Рис. на стр. 212.
- Kamada, Kawai, 1989, с. 7—15.
- Fruchterman, Reingold, 1991, с. 1129—1164. Помилка цитування: Некоректний тег
<ref>
; назва «FOOTNOTEFruchterman, Reingold19911129—1164» визначена кілька разів з різним вмістом - http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf A Multilevel Algorithm for Force-Directed Graph-Drawing
- Tutte, 1963.
- Tutte, 1963, с. 743–768.
- Eades, 1984.
- Eades, 1984, с. 149–160.
- Kamada, Kawai, 1989.
Література
- Martin Grandjean. Introduction à la visualisation de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19. — 2015.
- Stephen G. Kobourov. Spring Embedders and Force-Directed Graph Drawing Algorithms. — 2012. — arXiv:1201.3011. — Bibcode: .
- Bannister M. J, Eppstein M. J., Goodrich M. T., Trott L. Force-directed graph drawing using social gravity and scaling // Proc. 20th Int. Symp. Graph Drawing. — 2012. — Bibcode:
- Chernobelskiy R., Cunningham K., Goodrich M. T., Kobourov S. G., Trott L. Force-directed Lombardi-style graph drawing // Proc. 19th Symposium on Graph Drawing. — 2011.
- Jan de Leeuw. Convergence of the majorization method for multidimensional scaling // Journal of Classification. — Springer, 1988. — Т. 5, вип. 2. — С. 163—180. — DOI: .
- David Harel, Yehuda Koren. Graph drawing by high-dimensional embedding // Proceedings of the 9th International Symposium on Graph Drawing. — 2002. — С. 207—219. — .
- Aaron Quigley, Peter Eades. FADE: Graph Drawing, Clustering, and Visual Abstraction // . — 2001. — С. 197—210. — . Архивная копия от 21 мая 2006 на Wayback Machine
- Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. A System for Graph-based Visualization of the Evolution of Software // Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03). — New York, NY, USA : ACM, 2003. — С. 77—86; figures on p. 212. — . — DOI: Цитата: Щоб отримати естетично приємне розміщення графа, слід використати модифіковані сили Фрухтермана — Рейнгольда, тому що метод Камади — Каваї не дає задовільних результатів, але створює хороше приблизне розміщення, з якого обчислення Фрухтермана — Рейнгольда можуть швидко «доробити» розміщення.
- Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13, вип. 52. — DOI: .
- Peter Eades. A Heuristic for Graph Drawing // Congressus Numerantium. — 1984. — Т. 42, вип. 11.
- Thomas M. J. Fruchterman, Edward M. Reingold. Graph Drawing by Force-Directed Placement // Software – Practice & Experience. — Wiley, 1991. — Т. 21, вип. 11. — DOI: .
- Tomihisa Kamada, Satoru Kawai. An algorithm for drawing general undirected graphs // Information Processing Letters. — Elsevier, 1989. — Т. 31, вип. 1. — DOI: .
Додаткова література
- Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1999. — .
- Drawing graphs: methods and models / Michael Kaufmann, Dorothea Wagner. — Springer, 2001. — (Lecture Notes in Computer Science 2025) — . — DOI:
Посилання
- Візуалізація на flash + сирці та опис
- Дисертація Даніеля Тункеланга про силове розміщення графа (доступні сирці на Github)
- Hyperassociative Map Algorithm
- Інтерактивні алгоритми малювання графа в реальному часі використані в засобі онлайнового моделювання бази даних
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Silovi algori tmi vizualiza ciyi gra fiv klas algoritmiv vizualizaciyi grafiv u estetichno priyemnomu viglyadi Yih meta rozmistiti vuzli grafa v dvovimirnomu abo trivimirnomu prostori tak shob usi rebra mali b bilsh mensh odnakovu dovzhinu i zvesti do minimumu chislo peretiniv reber priznachivshi sili dlya mnozhini reber i vuzliv gruntuyuchis na yih vidnosnih polozhennyah a potim vikoristovuyuchi ci sili abo dlya modelyuvannya ruhu reber i vuzliv abo dlya minimizaciyi yih energiyi Vizualizaciya socialnoyi merezhi za dopomogoyu silovogo algoritmu vizualizaciyi grafaVizualizaciya zv yazkiv storinok u Viki za dopomogoyu silovogo algoritmu vizualizaciyi rozmishennya Todi yak vizualizaciya grafiv mozhe viyavitisya skladnoyu zadacheyu silovi algoritmi yak fizichni modeli zazvichaj ne vimagayut specialnih znan z teoriyi grafiv takih yak planarnist grafa SiliSilovi algoritmi vizualizaciyi grafiv priznachayut sili na mnozhini reber ta vuzliv grafa Zazvichaj vikoristovuyut sili prityagannya podibni do pruzhinnih na osnovi zakonu Guka dlya priznachennya sil param kinciv reber grafa Razom z tim shob rozdiliti vsi pari vuzliv vikoristovuyut sili vidshtovhuvannya podibni do vidshtovhuvannya elektrichnih zaryadiv na osnovi zakonu Kulona Dlya otrimannya rivnovazhnogo stanu ciyeyi sistemi sil rebra pragnut nabuti odnoridnih dovzhin cherez diyu pruzhin a vuzli ne pov yazani rebrom pragnut viddalitisya odin vid odnogo cherez diyu sil vidshtovhuvannya Sili prityagannya rebra ta sili vidshtovhuvannya vuzli mozhna viznachiti za dopomogoyu funkcij yaki ne zasnovani na fizichnij povedinci pruzhin ta chastinok Napriklad deyaki silovi sistemi vikoristovuyut pruzhini sili yakih zminyuyutsya logarifmichno a ne linijno Alternativna model rozglyadaye sili podibni do pruzhinnih dlya kozhnoyi pari vuzliv i j displaystyle i j de idealna dovzhina dij displaystyle delta ij kozhnoyi pruzhini proporcijna vidstani u grafi mizh vuzlami i i j a sili vidshtovhuvannya ne vikoristovuyutsya Minimizaciya riznici zazvichaj kvadrata riznici mizh evklidovoyu ta idealnoyu vidstannyu mizh vuzlami ekvivalentna metrichnij zadachi bagatovimirnogo shkalyuvannya Silovij graf mozhe vikoristovuvati sili vidminni vid mehanichnih pruzhin ta sil vidshtovhuvannya zaryadiv Silu analogichnu gravitaciyi mozhna vikoristati dlya tyazhinnya vershin u bik fiksovanoyi tochki prostoru malyuvannya grafa Ce mozhna vikoristati dlya zvedennya riznih komponent zv yaznosti nezv yaznogo grafa v odne cile inakshe ci chastini rozletilisya b odna vid odnoyi pid diyeyu sil vidshtovhuvannya Takozh ce dozvolyaye krashe centruvati vuzli na malyunku Ce takozh mozhe vplinuti na vidstan mizh vershinami odnogo komponenta zv yaznosti Dlya oriyentovanih grafiv mozhna vikoristovuvati analogi magnitnih poliv Shob uniknuti nakladennya abo majzhe nakladennya na kincevomu malyunku yak na rebrah tak i na vuzlah mozhna roztashuvati sili vidshtovhuvannya Na malyunkah z krivimi rebrami takimi yak dugi kil abo splajni sili mozhut roztashovuvatisya v kontrolnih tochkah cih krivih napriklad shob polipshiti kutovu rozdilnist MetodiYak tilki sili na vuzlah i rebrah viznacheno povedinku vsogo grafa pid diyeyu cih sil mozhna iterativno promodelyuvati podibno do povedinki fizichnoyi sistemi U takij situaciyi sili sho diyut na vuzli namagayutsya styagnuti yih blizhche abo vidshtovhnuti yih odin vid odnogo Ce trivaye poki sistema ne nabude stanu mehanichnoyi rivnovagi tobto pripinitsya zminennya polozhennya vuzliv vid iteraciyi do iteraciyi Polozhennya vuzliv u comu stani rivnovagi vikoristovuyut dlya pobudovi malyunka grafa Dlya sil viznachenih pruzhinami idealna dovzhina yakih proporcijna vidstani v grafi mazhoruvannya stresu daye duzhe horoshu povedinku tobto monotonnu zbizhnist i matematichno elegantnij shlyah minimizaciyi ciyeyi riznici i otzhe do horoshogo rozmishennya vershin grafa Mozhna takozh vikoristati mehanizmi yaki shukayut minimum energiyi pryamishe a ne za fizichnoyu modellyu Do takih mehanizmiv yaki ye prikladami zagalnih metodiv globalnoyi optimizaciyi nalezhat imitaciya vidpalu i genetichni algoritmi PerevagiVazhlivimi perevagami silovih algoritmiv ye taki vlastivosti Rezultati horoshoyi yakosti Shonajmenshe dlya grafiv serednogo rozmiru do 50 500 vershin otrimani rezultati zazvichaj mayut duzhe horoshi malyunki grafiv za takimi kriteriyami odnoridnist dovzhin reber rivnomirnij rozpodil vershin i simetriya Ostannij kriterij najvazhlivishij i vazhkodosyazhnij v inshih algoritmah Gnuchkist Silovi algoritmi mozhna legko pristosuvati i rozshiriti dlya dodatkovih estetichnih kriteriyiv Ce robit algoritmi universalnishimi Prikladami isnuyuchih rozshiren ye algoritmi dlya oriyentovanih grafiv vizualizaciya trivimirnih grafiv klasterna vizualizaciya grafiv vizualizaciya grafiv z obmezhennyami i dinamichna vizualizaciya grafiv Intuyitivnist Oskilki algoritmi zasnovani na fizichnih analogah zvichnih ob yektiv na zrazok pruzhin povedinku algoritmiv vidnosno prosto peredbachiti i zrozumiti Cogo nemaye v inshih algoritmah vizualizaciyi grafiv Prostota Tipovi silovi algoritmi prosti i mozhut buti realizovani kilkoma ryadkami kodu Inshi klasi algoritmiv vizualizaciyi taki yak algoritmi na osnovi ortogonalnih rozmishen zazvichaj vimagayut znachno bilshe roboti Interaktivnist She odniyeyu perevagoyu cogo klasu algoritmiv ye aspekt interaktivnosti Pri malyuvanni promizhnih etapiv grafa koristuvach mozhe sposterigati yak zminyuyetsya graf prostezhuyuchi evolyuciyu vid bezladnogo misiva do garnoyi konfiguraciyi U deyakih zasobah interaktivnogo malyuvannya grafa koristuvach mozhe vidsunuti odin abo kilka vuzliv zi stanu rivnovagi i sposterigati migraciyu vuzliv u novij stan rivnovagi Ce daye algoritmam perevagu dlya dinamichnih i onlajnovih sistem vizualizaciyi grafiv Stroga teoretichna pidtrimka Todi yak prosti silovi algoritmi chasto z yavlyayutsya v literaturi i na praktici oskilki voni vidnosno prosti i zrozumili pochinaye zrostati chislo obgruntovanishih pidhodiv Statistiki rozv yazuvali podibni zadachi v bagatovimirnomu shkalyuvanni BVSh angl multidimensional scaling z 1930 h rokiv fiziki takozh mayut dovgu istoriyu roboti z pov yazanimi zadachami modelyuvannya ruhu n til tak sho isnuyut cilkom zrili pidhodi Yak priklad pidhid mazhoruvannya stresu do metrichnih BVSh mozhna zastosuvati dlya vizualizaciyi grafa i v comu vipadku mozhna dovesti monotonnu zbizhnist Monotonna zbizhnist vlastivist sho algoritm bude na kozhnij iteraciyi zmenshuvati naprugu abo cinu rozmishennya vershin vazhliva oskilki ce garantuye sho rozmishennya zreshtoyu dosyagne lokalnogo minimumu i algoritm zupinitsya Glushinnya kolivan prizvodit do zupinki algoritmu ale ne garantuye sho bude dosyagnuto istinnogo lokalnogo minimumu NedolikiGolovni nedoliki silovih algoritmiv Velikij chas roboti Vvazhayetsya sho tipovi silovi algoritmi v zagalnomu vipadku mayut chas roboti ekvivalentnij O n3 displaystyle O n 3 de n chislo vuzliv vhidnogo grafa Ce tomu sho chislo iteracij ocinyuyetsya v O n displaystyle O n a na kozhnij iteraciyi neobhidno pereglyanuti vsi pari vuzliv i obchisliti vzayemni sili vidshtovhuvannya Ce shozhe na zadachu N til u fizici Odnak oskilki sili vidshtovhuvannya lokalni za prirodoyu graf mozhna rozbiti tak sho budut rozglyadatisya tilki susidni vershini Osnovni tehniki vikoristani v algoritmah dlya viznachennya rozmishennya vuzliv velikih grafiv vklyuchayut vkladennya visokoyi rozmirnosti bagatorivnevi podannya ta inshi metodi pov yazani z modelyuvannyam zadachi n til Napriklad zasnovanij na modelyuvanni Barnsa Hata metod FADE mozhe polipshiti chas roboti do n log n displaystyle n cdot log n na iteraciyu Gruba ocinka za kilka sekund mozhna ochikuvati malyuvannya maksimum 1000 vuzliv u standartnij tehnici n2 displaystyle n 2 na iteraciyu i 100 000 z tehnikoyu n log n displaystyle n cdot log n na iteraciyu Silovi algoritmi u kombinaciyi z bagatorivnevim pidhodom mozhut malyuvati grafi z miljonami vuzliv Pogani lokalni minimumi Legko bachiti sho silovij algoritm daye graf iz minimalnoyu energiyeyu zokrema ce mozhe buti lishe lokalnij minimum Znajdenij lokalnij minimum mozhe buti u bagatoh vipadkah istotno girshim vid globalnogo minimumu sho prizvodit do nizkoyi yakosti podannya Dlya bagatoh algoritmiv osoblivo dlya tih yaki dozvolyayut tilki ruh gradiyentnogo spusku na kincevij rezultat mozhe duzhe vplivati pochatkove polozhennya yake v bilshosti vipadkiv generuyetsya vipadkovo Problema poganogo lokalnogo minimumu staye osoblivo vazhlivoyu pri zrostanni chisla vershin grafa Kombinuvannya riznih algoritmiv dopomagaye virishiti cyu problemu Napriklad dlya shvidkogo generuvannya prijnyatnogo pochatkovogo rozmishennya mozhna vikoristati algoritm Kamadi Kavayi a potim polipshiti polozhennya susidnih vuzliv za algoritmom Fruhtermana Rejngolda Insha tehnika otrimannya globalnogo minimumu vikoristannya bagatorivnevogo pidhodu IstoriyaSilovi metodi vizualizaciyi grafiv shodyat do roboti Tatta v yakij vin pokazav sho poliedralni grafi mozhna namalyuvati na ploshini z opuklimi granyami zafiksuvavshi vershin zovnishnoyi grani planarnogo vkladennya grafa v en roztashuvavshi pruzhinopodibni sili prityagannya na kozhnomu rebri i dozvolivshi sistemi prijti v rivnovazhnij stan Zvazhayuchi na prostu prirodu sil u comu vipadku sistema ne mozhe zastryagti v lokalnomu minimumi a zbigayetsya do yedinoyi globalnoyi optimalnoyi konfiguraciyi Zvazhayuchi na cyu stattyu vkladennya planarnih grafiv iz opuklimi granyami inodi nazivayut vkladennyami Tatta Kombinaciyu sil prityagannya sumizhnih vershin grafa i sil vidshtovhuvannya dlya vsih vershin pershim vikoristav Ids She odnu pionersku robotu shodo cogo tipu silovogo rozmishennya opublikuvali Fruhterman i Rejngold Ideya vikoristannya mizh usima parami vershin lishe sil pruzhin z idealnimi dovzhinami pruzhin rivnimi vidstani po grafu nalezhit Kamadi i Kavayi Div takozh ru programa dlya vizualizaciyi biologichnih merezh Bazovij paket vklyuchaye silovi rozmishennya yak odin iz vbudovanih metodiv Gephi interaktivna vizualizaciya ta doslidnicka platforma exploration dlya vsih vidiv merezh ta skladnih sistem dinamichnih ta iyerarhichnih grafiv Graphviz programnij zasib sho realizuye bagatorivnevij silovij algoritm rozmishennya sered inshih zdatnij obroblyati duzhe veliki grafi en programnij zasib sho realizuye bilshist silovih algoritmiv rozmishennya GEM LGL GRIP FM3 en PrimitkiGrandjean 2015 s 109 128 Kobourov 2012 Bannister Eppstein Goodrich Trott 2012 Chernobelskiy Cunningham Goodrich Kobourov Trott 2011 s 78 90 de Leeuw 1988 s 163 180 Vose Aaron Arhiv originalu za 10 serpnya 2015 Procitovano 27 kvitnya 2022 Harel Koren 2002 s 207 219 Quigley Eades 2001 s 197 210 A Gallery of Large Graphs Procitovano 22 zhovtnya 2017 Collberg Kobourov Nagra Pitts Wampler 2003 s 77 86 Ris na str 212 Kamada Kawai 1989 s 7 15 Fruchterman Reingold 1991 s 1129 1164 Pomilka cituvannya Nekorektnij teg lt ref gt nazva FOOTNOTEFruchterman Reingold19911129 1164 viznachena kilka raziv z riznim vmistom http jgaa info accepted 2003 Walshaw2003 7 3 pdf A Multilevel Algorithm for Force Directed Graph Drawing Tutte 1963 Tutte 1963 s 743 768 Eades 1984 Eades 1984 s 149 160 Kamada Kawai 1989 LiteraturaMartin Grandjean Introduction a la visualisation de donnees l analyse de reseau en histoire Geschichte und Informatik 18 19 2015 Stephen G Kobourov Spring Embedders and Force Directed Graph Drawing Algorithms 2012 arXiv 1201 3011 Bibcode 2012arXiv1201 3011K Bannister M J Eppstein M J Goodrich M T Trott L Force directed graph drawing using social gravity and scaling Proc 20th Int Symp Graph Drawing 2012 Bibcode 2012arXiv1209 0748B Chernobelskiy R Cunningham K Goodrich M T Kobourov S G Trott L Force directed Lombardi style graph drawing Proc 19th Symposium on Graph Drawing 2011 Jan de Leeuw Convergence of the majorization method for multidimensional scaling Journal of Classification Springer 1988 T 5 vip 2 S 163 180 DOI 10 1007 BF01897162 David Harel Yehuda Koren Graph drawing by high dimensional embedding 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 2001 S 197 210 ISBN 3 540 41554 8 Arhivnaya kopiya ot 21 maya 2006 na Wayback Machine Christian Collberg Stephen Kobourov Jasvir Nagra Jacob Pitts Kevin Wampler A System for Graph based Visualization of the Evolution of Software Proceedings of the 2003 ACM Symposium on Software Visualization SoftVis 03 New York NY USA ACM 2003 S 77 86 figures on p 212 ISBN 1 58113 642 0 DOI 10 1145 774833 774844 Citata Shob otrimati estetichno priyemne rozmishennya grafa slid vikoristati modifikovani sili Fruhtermana Rejngolda tomu sho metod Kamadi Kavayi ne daye zadovilnih rezultativ ale stvoryuye horoshe priblizne rozmishennya z yakogo obchislennya Fruhtermana Rejngolda mozhut shvidko dorobiti rozmishennya Tutte W T How to draw a graph Proceedings of the London Mathematical Society 1963 T 13 vip 52 DOI 10 1112 plms s3 13 1 743 Peter Eades A Heuristic for Graph Drawing Congressus Numerantium 1984 T 42 vip 11 Thomas M J Fruchterman Edward M Reingold Graph Drawing by Force Directed Placement Software Practice amp Experience Wiley 1991 T 21 vip 11 DOI 10 1002 spe 4380211102 Tomihisa Kamada Satoru Kawai An algorithm for drawing general undirected graphs Information Processing Letters Elsevier 1989 T 31 vip 1 DOI 10 1016 0020 0190 89 90102 6 Dodatkova literaturaGiuseppe di Battista Peter Eades Roberto Tamassia Ioannis G Tollis Graph Drawing Algorithms for the Visualization of Graphs Prentice Hall 1999 ISBN 978 0 13 301615 4 Drawing graphs methods and models 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 PosilannyaVizualizaciya na flash sirci ta opis Disertaciya Danielya Tunkelanga pro silove rozmishennya grafa dostupni sirci na Github Hyperassociative Map Algorithm Interaktivni algoritmi malyuvannya grafa v realnomu chasi vikoristani v zasobi onlajnovogo modelyuvannya bazi danih