Візуалізація графів

 

 Ще з кінця XX століття візуалізація інформації та даних зазнала широкого розповсюдження. Це дало сильний поштовх для розвитку цілого та самостійного напрямку «Візуалізація графів та структур даних». Кількість алгоритмів візуалізації графів швидко збільшується із плином часу. Алгоритми візуалізації графів мають дуже широке застосування, починаючи від хімії та біології закінчуючи інформаційними технологіями та бізнес аналітикою.

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

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

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

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

Ще одним популярним класом візуалізації графів можна виділити Circular (Круговий). До цього класу відносяться два основних алгоритми: Circular та Circular Hierarchical.

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

Алгоритм Kozo Sugiyama (Кoзо Сугіяма) описаний у праці  «Методи візуального розуміння ієрархічних систем» опублікованій у 1981 році [2]. Описаний алгоритм також називають схемою Sugiyama. Схема Сугіяма призначена перш за все для оптимізації візуальних критеріїв, таких як зведення до мінімуму перетинів між ребрами і їх довжин. Алгоритм відноситься до методів порівневої візуалізації, тобто такі методи, в яких вершини розміщенні на різних рівнях(горизонтальних чи вертикальних).

У статті [3] автор описує новий евристичний метод для зображення графів, що носить назву «Magnetic spring model». Як вказує сам автор, К.Сугіяма усі описані до цього моделі були зорієнтовані на візуалізацію неорієнтованих графів. На сьогоднішній день існує безліч прикладів використання «Magnetic spring model», статистично доведено ефективність даного методу.

Ще одним великим класом алгоритмів візуалізації графів є «Force Directed Placement», що в перекладі означає «Розміщення під дією сили». Цей клас алгоритмів спрямований на вирішення задачі візуалізації графів із  хаотично-розміщеними вузлами, таким чином, щоб отримане в результаті представлення задовольняло візуально - естетичне  представлення, тобто симетричність та мінімальність перетинаючи ребер. Алгоритми FDP активно вивчалися Г. Баттістою (G. Battista) та описані у його роботі [4], що присвячена алгоритмам зображення графів.

Одним із представників «Force Directed» алгоритмів є алгоритм Fruchterman-Reingold, в основі назви якого лежать імена його творців T. M. J. Fruchterman та E. M. Reingold. Даний алгоритм описаний у статті [5].

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

Іншим представником  «Force Directed» алгоритмів є алгоритм Kamada-Kawai Algorithm. Основна задача алгоритму залишається такою ж, як і у Fruchterman-Reingold алгоритмі. Основна відмінність алгоритму Kamada-Kawai полягає у мінімізації енергії шляхом пошуку похідної від рівнянь сили.

Алгоритм Kamada-Kawai [6] виконує впорядкування вузлів графу досить швидко і тому може бути застосований для графів любих розмірів. Але, попри це, згідно загально-естетичних критеріїв результат, отриманий при використання цього алгоритму часто залишає бажати кращого, і тому досить часто після алгоритму Kamada-Kawai використовують Fruchterman-Reingold алгоритм.

Важливим класом методів є методи, що представляють інформацію у вигляді деревовидних структур. Одним із представників такого методу є алгоритм Radial Tree (Променеве дерево) [7]. Суть алгоритму полягає у розміщенні самостійної вершини по центру екрану, а всі решта вершин, що залежать від цієї розміщуються навколо.

Задача візуалізації графових структур є надзвичайно актуальною та потребує з кожним роком більш якісного розв’язку. Адже із розповсюдженням Web-технологій, розвитком нових напрямків у науці та впровадженням новітніх підходів до організації освітнього і управлінського процесів, все частіше і частіше виникає потреба у графічному представленні графових структур даних різного походження. Особливо актуальною ця задача стає при потребі візуалізації структур значних розмірів — зокрема при вирішенні різнорідних проблем наукового, корпоративного та навіть державного характеру. Актуальність даної теми додатково підсилюється тим, що вона не є вузько спеціалізованою, тобто не орієнтована для застосування лише у певній галузі або сфері, а навпаки є легко застосовною в багатьох галузях людської діяльності. Програмне забезпечення для візуалізації графових структур створюється з метою вирішення цих проблем.


 

СПИСОК ЛІТЕРАТУРИ

1.             Gruber T. R. A translation approach to portable ontologies // Knowledge acquisition. — 1993. — № 5 (2). — P. 199 – 220.

2.             Sugiyama K., Tagawa S., Toda M. Methods for visual understanding of hierarchical systems // IEEE Transactions on Systems, Man and Cybernetics. — February 1981. — SMC–11 (2). — P. 109 – 125.

3.             Kozo Sugiyama and Kazuo Misue. Graph Drawing by the Magnetic Spring Model // Journal of Visual Languages and Computing. — September 1995. — Volume 6. — Issue 3. — P. 217 – 231.

4.             Battista G. , Eades P., Tamassia R. and Tollis I. G. Algorithms for drawing graphs: An annotated bibliography // Computational Geometry: Theory and Applications. — 1994. — № 4 (5). — P. 235 – 282.

5.             Fruchterman T. M. J. and Reingold E. M. Graph Drawing by Force-Directed Placement // Software: Practice and Experience. — 1991 — № 21 (11).

6.             Kamada T. and Kawai S. An algorithm for drawing general undirected graphs // Information Processing Letters. — 1989. — № 31. — P. 7 – 15.

7.             Di Battista G., Eades P., Tamassia R. and Tollis I. G. Graph Drawing: Algorithms for the Visualization of Graphs. — Upper Saddle River, NJ: Prentice Hall. — 1999.

8.             Gruber T. R. A translation approach to portable ontologies // Knowledge acquisition. — 1993. — № 5 (2). — P. 199 – 220.