Силові алгоритми візуалізації графів

Візуалізація соціальної мережі за допомогою силового алгоритму візуалізації графа

Візуалізація зв'язків сторінок у Вікі за допомогою силового алгоритму візуалізації розміщення.

Силові́ алгори́тми візуаліза́ції гра́фів — клас алгоритмів візуалізації графів у естетично приємному вигляді. Їх мета — розмістити вузли графа в двовимірному або тривимірному просторі так, щоб усі ребра мали б більш-менш однакову довжину, і звести до мінімуму число перетинів ребер, призначивши сили для множини ребер і вузлів, ґрунтуючись на їх відносних положеннях, а потім використовуючи ці сили або для моделювання руху ребер і вузлів, або для мінімізації їх енергії.

Тоді як візуалізація графів може виявитися складною задачею, силові алгоритми, як фізичні моделі, зазвичай не вимагають спеціальних знань з теорії графів, таких як планарність графа.

Сили

Силові алгоритми візуалізації графів призначають сили на множині ребер та вузлів графа. Зазвичай використовують сили притягання, подібні до пружинних, на основі закону Гука для призначення сил парам кінців ребер графа. Разом з тим, щоб розділити всі пари вузлів, використовують сили відштовхування, подібні до відштовхування електричних зарядів на основі закону Кулона. Для отримання рівноважного стану цієї системи сил ребра прагнуть набути однорідних довжин (через дію пружин), а вузли, не пов'язані ребром, прагнуть віддалитися один від одного (через дію сил відштовхування). Сили притягання (ребра) та сили відштовхування (вузли) можна визначити за допомогою функцій, які не засновані на фізичній поведінці пружин та частинок. Наприклад, деякі силові системи використовують пружини, сили яких змінюються логарифмічно, а не лінійно.

Альтернативна модель розглядає сили, подібні до пружинних, для кожної пари вузлів $(i,j)$, де ідеальна довжина $\delta _{ij}$ кожної пружини пропорційна відстані у графі між вузлами i і j, а сили відштовхування не використовуються. Мінімізація різниці (зазвичай, квадрата різниці) між евклідовою та ідеальною відстанню між вузлами еквівалентна метричній задачі багатовимірного шкалювання.

Силовий граф може використовувати сили, відмінні від механічних пружин та сил відштовхування зарядів. Силу, аналогічну гравітації, можна використати для тяжіння вершин у бік фіксованої точки простору малювання графа. Це можна використати для зведення різних компонент зв'язності незв'язного графа в одне ціле, інакше ці частини розлетілися б одна від одної під дією сил відштовхування. Також це дозволяє краще центрувати вузли на малюнку. Це також може вплинути на відстань між вершинами одного компонента зв'язності. Для орієнтованих графів можна використовувати аналоги магнітних полів. Щоб уникнути накладення або майже накладення на кінцевому малюнку, як на ребрах, так і на вузлах можна розташувати сили відштовхування. На малюнках з кривими ребрами, такими як дуги кіл або сплайни, сили можуть розташовуватися в контрольних точках цих кривих, наприклад, щоб поліпшити кутову роздільність .

Методи

Як тільки сили на вузлах і ребрах визначено, поведінку всього графа під дією цих сил можна ітеративно промоделювати, подібно до поведінки фізичної системи. У такій ситуації сили, що діють на вузли, намагаються стягнути їх ближче або відштовхнути їх один від одного. Це триває, поки система не набуде стану механічної рівноваги, тобто припиниться змінення положення вузлів від ітерації до ітерації. Положення вузлів у цьому стані рівноваги використовують для побудови малюнка графа.

Для сил, визначених пружинами, ідеальна довжина яких пропорційна відстані в графі, мажорування стресу дає дуже хорошу поведінку (тобто монотонну збіжність) і математично елегантний шлях мінімізації цієї різниці і, отже, до хорошого розміщення вершин графа.

Можна також використати механізми, які шукають мінімум енергії пряміше, а не за фізичною моделлю. До таких механізмів, які є прикладами загальних методів глобальної оптимізації, належать імітація відпалу і генетичні алгоритми.

Переваги

Важливими перевагами силових алгоритмів є такі властивості:

Результати хорошої якості

Щонайменше для графів середнього розміру (до 50-500 вершин), отримані результати зазвичай мають дуже хороші малюнки графів за такими критеріями: однорідність довжин ребер, рівномірний розподіл вершин і симетрія. Останній критерій найважливіший і важкодосяжний в інших алгоритмах.

Гнучкість

Силові алгоритми можна легко пристосувати і розширити для додаткових естетичних критеріїв. Це робить алгоритми універсальнішими. Прикладами існуючих розширень є алгоритми для орієнтованих графів, візуалізація тривимірних графів, кластерна візуалізація графів, візуалізація графів з обмеженнями і динамічна візуалізація графів.

Інтуїтивність

Оскільки алгоритми засновані на фізичних аналогах звичних об'єктів, на зразок пружин, поведінку алгоритмів відносно просто передбачити і зрозуміти. Цього немає в інших алгоритмах візуалізації графів.

Простота

Типові силові алгоритми прості і можуть бути реалізовані кількома рядками коду. Інші класи алгоритмів візуалізації, такі як алгоритми на основі ортогональних розміщень, зазвичай вимагають значно більше роботи.

Інтерактивність

Ще однією перевагою цього класу алгоритмів є аспект інтерактивності. При малюванні проміжних етапів графа користувач може спостерігати, як змінюється граф, простежуючи еволюцію від безладного місива до гарної конфігурації. У деяких засобах інтерактивного малювання графа користувач може відсунути один або кілька вузлів зі стану рівноваги і спостерігати міграцію вузлів у новий стан рівноваги. Це дає алгоритмам перевагу для динамічних і онлайнових систем візуалізації графів.

Строга теоретична підтримка

Тоді як прості силові алгоритми часто з'являються в літературі і на практиці (оскільки вони відносно прості і зрозумілі), починає зростати число обгрунтованіших підходів. Статистики розв'язували подібні задачі в багатовимірному шкалюванні (БВШ, англ. multidimensional scaling) з 1930-х років, фізики також мають довгу історію роботи з пов'язаними задачами моделювання руху n тіл, так що існують цілком зрілі підходи. Як приклад, підхід мажорування стресу до метричних БВШ можна застосувати для візуалізації графа і в цьому випадку можна довести монотонну збіжність. Монотонна збіжність, властивість, що алгоритм буде на кожній ітерації зменшувати напругу або ціну розміщення вершин, важлива, оскільки це гарантує, що розміщення, зрештою, досягне локального мінімуму і алгоритм зупиниться. Глушіння коливань призводить до зупинки алгоритму, але не гарантує, що буде досягнуто істинного локального мінімуму.

Недоліки

Головні недоліки силових алгоритмів:

Великий час роботи

Вважається, що типові силові алгоритми в загальному випадку мають час роботи, еквівалентний $O(n^{3})$, де n — число вузлів вхідного графа. Це тому, що число ітерацій оцінюється в $O(n)$, а на кожній ітерації необхідно переглянути всі пари вузлів і обчислити взаємні сили відштовхування. Це схоже на задачу N-тіл у фізиці. Однак, оскільки сили відштовхування локальні за природою, граф можна розбити так, що будуть розглядатися тільки сусідні вершини. Основні техніки, використані в алгоритмах для визначення розміщення вузлів великих графів, включають вкладення високої розмірності, багаторівневі подання та інші методи, пов'язані з моделюванням задачі n тіл. Наприклад, заснований на моделюванні Барнса-Хата метод FADE може поліпшити час роботи до $n\cdot log(n)$ на ітерацію. Груба оцінка: за кілька секунд можна очікувати малювання максимум 1000 вузлів у стандартній техніці $n^{2}$ на ітерацію і 100 000 з технікою $n\cdot log(n)$ на ітерацію. Силові алгоритми, у комбінації з багаторівневим підходом, можуть малювати графи з мільйонами вузлів.

Погані локальні мінімуми

Легко бачити, що силовий алгоритм дає граф із мінімальною енергією, зокрема, це може бути лише локальний мінімум. Знайдений локальний мінімум може бути, у багатьох випадках істотно гіршим від глобального мінімуму, що призводить до низької якості подання. Для багатьох алгоритмів, особливо для тих, які дозволяють тільки рух градієнтного спуску, на кінцевий результат може дуже впливати початкове положення, яке в більшості випадків генерується випадково. Проблема поганого локального мінімуму стає особливо важливою при зростанні числа вершин графа. Комбінування різних алгоритмів допомагає вирішити цю проблему. Наприклад, для швидкого генерування прийнятного початкового розміщення можна використати алгоритм Камади — Каваї, а потім поліпшити положення сусідніх вузлів за алгоритмом Фрухтермана — Рейнгольда. Інша техніка отримання глобального мінімуму — використання багаторівневого підходу .

Історія

Силові методи візуалізації графів сходять до роботи Татта, в якій він показав, що поліедральні графи можна намалювати на площині з опуклими гранями, зафіксувавши вершин зовнішньої грані планарного вкладення графа в опуклому положенні, розташувавши пружиноподібні сили притягання на кожному ребрі і дозволивши системі прийти в рівноважний стан. Зважаючи на просту природу сил у цьому випадку система не може застрягти в локальному мінімумі, а збігається до єдиної глобальної оптимальної конфігурації. Зважаючи на цю статтю, вкладення планарних графів із опуклими гранями іноді називають вкладеннями Татта.

Комбінацію сил притягання суміжних вершин графа і сил відштовхування для всіх вершин першим використав Ідс. Ще одну піонерську роботу щодо цього типу силового розміщення опублікували Фрухтерман і Рейнгольд. Ідея використання між усіма парами вершин лише сил пружин з ідеальними довжинами пружин, рівними відстані по графу, належить Камаді і Каваї.

Див. також

• Cytoscape — програма для візуалізації біологічних мереж. Базовий пакет включає силові розміщення як один із вбудованих методів.
• Gephi — інтерактивна візуалізація та дослідницька платформа exploration для всіх видів мереж та складних систем, динамічних та ієрархічних графів.
• Graphviz — програмний засіб, що реалізує багаторівневий силовий алгоритм розміщення (серед інших), здатний обробляти дуже великі графи.
• Tulip — програмний засіб, що реалізує більшість силових алгоритмів розміщення (GEM, LGL, GRIP, FM3).
• Prefuse

Література

• 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: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. — Т. 5, вип. 2. — С. 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. — С. 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. — С. 197—210. — ISBN 3-540-41554-8. Архивная копия от 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. — ISBN 1-58113-642-0. — DOI:10.1145/774833.774844. Цитата: Щоб отримати естетично приємне розміщення графа, слід використати модифіковані сили Фрухтермана — Рейнгольда, тому що метод Камади — Каваї не дає задовільних результатів, але створює хороше приблизне розміщення, з якого обчислення Фрухтермана — Рейнгольда можуть швидко «доробити» розміщення.
• Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13, вип. 52. — DOI:10.1112/plms/s3-13.1.743.
• 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:10.1002/spe.4380211102.
• Tomihisa Kamada, Satoru Kawai. An algorithm for drawing general undirected graphs // Information Processing Letters. — Elsevier, 1989. — Т. 31, вип. 1. — DOI:10.1016/0020-0190(89)90102-6.

Додаткова література

• Giuseppe 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.

Посилання

• Візуалізація на flash + сирці та опис
• Дисертація Даніеля Тункеланга про силове розміщення графа (доступні сирці на Github)
• Hyperassociative Map Algorithm
• Інтерактивні алгоритми малювання графа в реальному часі використані в засобі онлайнового моделювання бази даних