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

Зображення графів знаходиться на перетині математики та комп'ютерних наук, тому, що об'єднує ^[en] теорію графів з візуалізацією інформації для отримання двовимірних зображень графів, що виникають в практичних задачах аналізу соціальних мереж, картографії, лінгвістики, та біоінформатики.

Графічне представлення всесвітньої мережі за одну хвилину через гіперпосилання

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

Домовленості

Орієнтований граф з кінцями, що вказують на напрям ребра

Графи зазвичай зображуються як діаграми, що наголошують на зв'язках між вузлами, де вершини представлені у вигляді дисків, коробок або текстових міток, і ребер, зображених відрізками, ламаними або кривими в евклідовому просторі. Такі діаграми можна побачити у роботах 13-го століття Раймунда Луллія, які він використовував для зображення повних графів, з метою аналізу усіх попарних комбінацій для множини метафізичних понять.

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

• Альтернативні домовленості використовують такі уявлення суміжності, як ^[en], де вершини представлені у вигляді областей в площині, що не перетинаються, а ребра зображені як примикання між областями.
• Зображення перетинів, в яких вершини зображені, як геометричні об'єкти, що не перетинаються, а ребра — їх перетинами.
• Зображення видимості, в яких вершини представлені областями в площині, а ребра областями, що мають безперешкодну пряму видимість одне одного.
• Зображення зливання, на яких ребра — гладкі, криві в межах математичних ^[en].
• Зображення у вигляді тканини, де вершини представлені у вигляді горизонтальних ліній, а ребра у вигляді вертикальних ліній.
• Зображення матриці суміжності графа.

Критерії якості

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

Планарний граф зображений без перетинів ребер

• (Числом схрещень) креслення є число пар ребер, що перетинаються між собою. Якщо цей граф є планарним, то часто буває зручно зобразити його без будь-яких перетинів ребер; тобто, в такому випадку, графік являє собою граф вкладення. Однак неплоскі графи часто виникають у додатках, тому алгоритми малювання графа, як правило, повинні дозволяти перетин ребер.
• Площина зображення — це найменша територія (вікна обмеження) графа, щодо найближчої відстані між будь-якими двома вершинами. Креслення з меншою площею, як правило, краще, ніж з більшою площею, бо вони дозволяють зберегти особливості малюнка, що будуть показані в більшому розмірі й, отже, більш розбірливо. (Співвідношення сторін) обмежувального блоку також може бути важливим.
• Симетрія зображення — це проблема пошуку груп симетрії у даному графі, і знаходження зображення, що є найбільш симетричним. Деякі методи розташування автоматично ведуть до симетричних зображень; з іншого боку, деякі методи зображення починаються зі знаходження симетрії отриманого графа для його зображення.
• Важливо, що ребра мають якомога простішу форму, аби оку людини було легше їх відстежувати. У полілінійних кресленнях, важкість конструкції ребра може вимірюватися у ^[en], і багато методів мають на меті надати креслення з невеликою кількістю загальних згинів або кількома згинами на ребро. Подібним чином для сплайн-кривих складність ребра може бути виміряна кількістю контрольних точок на ребрі.
• Кілька популярних критеріїв якості, пов'язаних з довжиною ребер: в загальному випадку бажано звести до мінімуму загальну довжину країв, а також максимальну довжину будь-якого краю. Крім того, для довжин ребер може бути кращим залишатися однаковими, а не різноманітними.
• (Кутова роздільність) — це міра найгострішого кута у зображенні графа. Якщо граф має вершини з великими степенями, то він обов'язково матиме не велику кутову роздільність, але кутова роздільність може бути обмежена знизу функцією степеня.
• Число нахилів графа — це мінімальна кількість різних нахилів, що потрібні для зображення прямими лініями ребер сегмента (з перетином). Кубічний граф має кількість нахилів не більше чотирьох, але граф з п'ятьма кутами може мати необмежену кількість нахилів; ще залишається не зрозумілим, чи обмежена кількість нахилів 4-кутного графа.

Методи макетування

(Силова візуалізація) мережі.

Існує багато стратегій компонування графів:

• У (системі силового компонування), програми зображення графів змінюють початкове розміщення вершин шляхом безперервного переміщення вершин відповідно до системи сил, заснованої на фізичних метафорах, пов'язаних з системами пружин або молекулярної механіки. Зазвичай, ці системи поєднують в собі сили тяжіння між сусідніми вершинами з силами відштовхування між усіма парами вершин, щоб знайти макет, в якому довжини ребер малі, в той час, як вершини добре розділені. Ці системи можуть виконувати метод найшвидшого спуску на основі мінімізації з (функції енергії), або ж вони можуть перевести свої сили безпосередньо у швидкості або прискорення для рухомих вершин.
• Метод ^[en] використовує власні вектори матриці, такі як ^[en] отриманого з матриці суміжності графа.
• Ортогональні методи компонування, що дозволяють ребрам графа йти горизонтально або вертикально, паралельно осям координат макета. Ці методи були спочатку розроблені для (схем надвеликого рівня інтеграції), друкованих плат і проблем компонування, але вони також були пристосовані до зображення графів. Вони зазвичай включають багатофазний підхід, в якому введення графа вирівнюється шляхом заміни точок перетину вершинами, знаходиться топологічне вкладення планаризованного графа, орієнтація сторін вибирається так, щоб звести до мінімуму вигини, вершини розташовуються послідовно з цими орієнтаціями, і, нарешті, етап ущільнення макету зменшує площу малюнка.
• Алгоритми макету дерев використовують для зображення (деревоподібних) структур з коренем, зокрема, це пасує для дерев. Зазвичай, у техніці, що називається «кульовий макет» (англ. balloon layout), нащадок кожного вузла у дереві малюється на колі, що оточує вузол, із радіусом цих кіл, що спадає на нижчих рівнях дерева так, щоб ці кола не накладалися одне на одного.
• Методи ^[en] (які часто називають зображеннями у стилі Сугияма) найкраще підходять для орієнтованого ациклічного графа або графів, близьких до ациклічних, таких як графи залежностей між модулями або функціями в програмній системі. У цих методах, вузли графа розташовані на горизонтальних шарах з використанням методів, таких як ^[en], таким чином, що більшість ребер йдуть вниз від одного шару до іншого; після цього кроку вузли в кожному шарі розташовуються з метою мінімізації перетинів.

(Дугова діаграма) графа

• (Дугова діаграма), це стиль компонування, відомий з 1960-х років, розташуємо вершини в одну лінію; ребра можуть бути зображені як півкола вище або нижче лінії, або як плавні криві, з'єднані з декількох півкіл.
• У коловій схемі вершини обережно розташовані по колу, з метою зменшення перетинів та розташування сусідніх вершин якомога ближче одне до одного. Ребра можуть бути зображені як хорди кола чи його арки зсередини або зовні. Іноді можуть бути використані декілька кіл.
• У ^[en] вершини записуються таким чином, що кожна вершина знаходиться вище, справа, або з обох боків від іншої, тоді й тільки тоді, коли вона ^[en] з цієї вершини. Таким чином, стиль макета робить відношення досяжності графа візуально очевидним.

Графічні креслення для конкретних додатків

Графи та зображення графа, що виникають в інших областях застосування, включають:

• ^[en], зображення соціальної мережі, що часто пропонується ^[en].
• Діаграма Гассе, це спеціалізований тип зображення графа, спеціалізований на частково впорядковані множини.
• ^[en] (фр. дитячий малюнок), тип графічного малювання, що використовується в алгебричній геометрії.
• Діаграма станів автомата, графічне зображення скінченного автомата.
• (Схема комп'ютерної мережі), зображення вузлів і з'єднань Комп'ютерної мережі.
• Блок-схема, зображення, у якому вузли представляють кроки алгоритму, та сторони — Потік керування між кроками.
• Діаграма потоків даних, зображення в якому вузли беруться за компоненти Інформаційної системи та сторони — рух інформації з одного компонента у інший.
• Біоінформатика включає філогенетичне дерево, мережу білок-білкової взаємодії, та ^[en].

Крім того, ^[en] та трасування — кроки (автоматизації проєктування електроніки) (EDA) схожі у багатьох аспектах до зображення графів, оскільки існує проблема ^[en] у розподілених обчисленнях, та література з зображення графів містить декілька результатів, позичених з літератури EDA. Однак, ці проблеми також різняться у деяких важливих аспектах: наприклад, у EDA, область мінімізації та довжина сигналу важливіші за естетичність, але проблеми зв'язку у EDA можуть мати понад два термінали на мережу у той час, як аналогічна проблема у зображенні графа зазвичай містить пари вершин для кожного ребра.

Програмне забезпечення

Програмне забезпечення, системи та провайдери систем для малювання графів:

• ^[en], програма з відкритим вихідним кодом від ^[en] для зображення великих мереж шляхом малювання вузлів у вигляді горизонтальних ліній.
• ^[en], програмне забезпечення з відкритим вихідним кодом для візуалізації мереж молекулярної взаємодії.
• (Gephi), програмне забезпечення для аналізу та візуалізації мережі з відкритим кодом.
• (graph-tool) — безкоштовна бібліотека Python для аналізу графів.
• (Graphviz), система для малювання графів з відкритим вихідним кодом від ^[en].
• ^[en], програмне забезпечення для комерційного аналізу та візуалізації мережі для (графових баз даних).
• Mathematica, засіб обчислення загального призначення, що містить 2D і 3D візуалізації графа та інструменти аналізу графів.
• ^[en], бібліотека .NET (раніше називалася GLEE) з відкритим кодом для зображення графів.
• (NetworkX) — це бібліотека Python для вивчення графів та мереж.
• ^[en] — інструмент візуалізації даних з відкритим кодом.
• (yEd), редактор графів з функціоналом розмітки.
• ^[en] 3.0 з graphdrawing пакетом (необхідно мати ^[en]).
• ^[en], програмне забезпечення для візуалізації великих мереж з відкритим кодом.

Див. також

• (Одночасне вкладення графів)

Примітки

Виноски

1. Di Battista та ін., (1994), pp. vii–viii; Herman, Melançon та Marshall, (2000), Section 1.1, «Typical Application Areas».
2. Di Battista та ін., (1994), p. 6.
3. Di Battista та ін., (1994), p. viii.
4. Misue та ін., (1995)
5. Knuth, Donald E. (2013), Two thousand years of combinatorics, у Wilson, Robin; Watkins, John J. (ред.), Combinatorics: Ancient and Modern, Oxford University Press, с. 7—37.
6. Holten та van Wijk, (2009); Holten та ін., (2011).
7. Garg та Tamassia, (1995).
8. Longabaugh, (2012).
9. Di Battista та ін., (1994), Section 2.1.2, Aesthetics, pp. 14–16; Purchase, Cohen та James, (1997).
10. Di Battista та ін., (1994), p 14.
11. Di Battista та ін., (1994), p. 16.
12. Pach та Sharir, (2009).
13. Published in Grandjean, Martin (2014). . Les Cahiers du Numérique. 10 (3): 37—54. doi:10.3166/lcn.10.3.37-54. Архів оригіналу за 27 червня 2015. Процитовано 15 жовтня 2014.
14. Di Battista та ін., (1994), Section 2.7, «The Force-Directed Approach», pp. 29–30, and Chapter 10, «Force-Directed Methods», pp. 303—326.
15. Beckman, (1994); Koren, (2005).
16. Di Battista та ін., (1994), Chapter 5, «Flow and Orthogonal Drawings», pp. 137—170; (Eiglsperger, Fekete та Klau, 2001).
17. Herman, Melançon та Marshall, (2000), Section 2.2, «Traditional Layout — An Overview».
18. Sugiyama, Tagawa та Toda, (1981); Bastert та Matuszewski, (2001); Di Battista та ін., (1994), Chapter 9, «Layered Drawings of Digraphs», pp. 265—302.
19. Saaty, (1964).
20. Doğrusöz, Madden та Madden, (1997).
21. Di Battista та ін., (1994), Section 4.7, «Dominance Drawings», pp. 112—127.
22. Scott, (2000); Brandes, Freeman та Wagner, (2014).
23. Di Battista та ін., (1994), pp. 15-16, and Chapter 6, «Flow and Upward Planarity», pp. 171—214; Freese, (2004).
24. Zapponi, (2003).
25. Anderson та Head, (2006).
26. Di Battista та Rimondini, (2014).
27. Bachmaier, Brandes та Schreiber, (2014).
28. «Graphviz and Dynagraph — Static and Dynamic Graph Drawing Tools», by John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull, in Jünger та Mutzel, (2004).
29. GraphPlot [ 3 лютого 2014 у Wayback Machine.] Mathematica documentation
30. . Архів оригіналу за 12 вересня 2013. Процитовано 20 березня 2016.
31. Nachmanson, Robertson та Lee, (2008).
32. «Tulip — A Huge Graph Visualization Framework», by David Auber, in Jünger та Mutzel, (2004).
33. «yFiles — Visualization and Automatic Layout of Graphs», by Roland Wiese, Markus Eiglsperger, and Michael Kaufmann, in Jünger та Mutzel, (2004).
34. Tantau, (2013); see also the older GD 2012 presentation [ 27 травня 2016 у Wayback Machine.]

Загальні посилання

• Di Battista, Giuseppe; ; ; Tollis, Ioannis G. (1994), , , 4: 235—282, doi:10.1016/0925-7721(94)00014-x, архів оригіналу за 27 березня 2016, процитовано 20 березня 2016.
• Di Battista, Giuseppe; ; ; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN .
• Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), , IEEE Transactions on Visualization and Computer Graphics, 6 (1): 24—43, doi:10.1109/2945.841119, архів оригіналу за 23 липня 2011, процитовано 20 березня 2016.
• Jünger, Michael; (2004), Graph Drawing Software, Springer-Verlag, ISBN .
• Kaufmann, Michael; , ред. (2001), Drawing Graphs: Methods and Models, , т. 2025, Springer-Verlag, doi:10.1007/3-540-44969-8.
• , ред. (2014), , CRC Press, архів оригіналу за 15 серпня 2013, процитовано 20 березня 2016.

Спеціалізовані підтеми

• Anderson, James Andrew; Head, Thomas J. (2006), , Cambridge University Press, с. 38—41, ISBN , архів оригіналу за 23 червня 2013, процитовано 20 березня 2016.
• Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), Biological Networks, у (ред.), Handbook of Graph Drawing and Visualization, CRC Press, с. 621—651.
• Bastert, Oliver; Matuszewski, Christian (2001), Layered drawings of digraphs, у Kaufmann, Michael; (ред.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, т. 2025, Springer-Verlag, с. 87—120, doi:10.1007/3-540-44969-8_5.
• Beckman, Brian (1994), , Tech. Report MSR-TR-94-04, Microsoft Research, архів оригіналу за 1 квітня 2016, процитовано 20 березня 2016.
• Brandes, Ulrik; Freeman, Linton C.; (2014), Social Networks, у (ред.), Handbook of Graph Drawing and Visualization, CRC Press, с. 805—839.
• Di Battista, Giuseppe; Rimondini, Massimo (2014), Computer Networks, у (ред.), Handbook of Graph Drawing and Visualization, CRC Press, с. 763—803.
• Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), Circular layout in the Graph Layout toolkit, у North, Stephen (ред.), (Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings), Lecture Notes in Computer Science, т. 1190, Springer-Verlag, с. 92—100, doi:10.1007/3-540-62495-3_40.
• Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), Orthogonal graph drawing, у Kaufmann, Michael; (ред.), Drawing Graphs, Lecture Notes in Computer Science, т. 2025, Springer Berlin / Heidelberg, с. 121—171, doi:10.1007/3-540-44969-8_6.
• Freese, Ralph (2004), Automated lattice drawing, у Eklund, Peter (ред.), Concept Lattices: Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings (PDF), Lecture Notes in Computer Science, т. 2961, Springer-Verlag, с. 589—590, doi:10.1007/978-3-540-24651-0_12, архів оригіналу (PDF) за 14 березня 2016, процитовано 20 березня 2016.
• Garg, Ashim; Tamassia, Roberto (1995), Upward planarity testing, , 12 (2): 109—133, doi:10.1007/BF01108622, MR 1354797.
• Holten, Danny; Isenberg, Petra; ; Fekete, Jean-Daniel (2011), An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs, (PDF), с. 195—202, doi:10.1109/PACIFICVIS.2011.5742390, архів оригіналу (PDF) за 11 квітня 2016, процитовано 20 березня 2016.
• Holten, Danny; (2009), A user study on visualizing directed edges in graphs, (PDF), с. 2299—2308, doi:10.1145/1518701.1519054, архів оригіналу (PDF) за 6 листопада 2011, процитовано 20 березня 2016.
• Koren, Yehuda (2005), (PDF), Computers & Mathematics with Applications, 49 (11-12): 1867—1888, doi:10.1016/j.camwa.2004.08.015, MR 2154691, архів оригіналу (PDF) за 2 квітня 2012, процитовано 20 березня 2016.
• Longabaugh, William (2012), (PDF), BMC Bioinformatics, 13: 275, doi:10.1186/1471-2105-13-275, PMID 23102059, архів оригіналу (PDF) за 24 вересня 2015, процитовано 20 березня 2016{{}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом ().
• Madden, Brendan; Madden, Patrick; Powers, Steve; Himsolt, Michael (1996), Portable graph layout and editing, у Brandenburg, Franz J. (ред.), Graph Drawing: (Symposium on Graph Drawing, GD '95), Passau, Germany, September 20–22, 1995, Proceedings, Lecture Notes in Computer Science, т. 1027, Springer-Verlag, с. 385—395, doi:10.1007/BFb0021822.
• Misue, K.; Eades, P.; Lai, W.; Sugiyama, K. (1995), Layout Adjustment and the Mental Map, Journal of Visual Languages and Computing, 6 (2): 183—210, doi:10.1006/jvlc.1995.1010.
• Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), Drawing Graphs with GLEE (PDF), у Hong, Seok-Hee; ; Quan, Wu (ред.), (Graph Drawing, 15th International Symposium, GD 2007), Sydney, Australia, September 24–26, 2007, Revised Папери, Lecture Notes in Computer Science, т. 4875, Springer-Verlag, с. 389—394, doi:10.1007/978-3-540-77537-9_38.
• ; (2009), 5.5 Angular resolution and slopes, Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, т. 152, American Mathematical Society, с. 126—127.
• Purchase, H. C.; Cohen, R. F.; James, M. I. (1997), An experimental study of the basis for graph drawing algorithms (PDF), Journal of Experimental Algorithmics, 2, Article 4, doi:10.1145/264216.264222^{[недоступне посилання з квітня 2019]}.
• (Saaty, Thomas L.) (1964), The minimum number of intersections in complete graphs, Proc. Natl. Acad. Sci. U.S.A., 52: 688—690, doi:10.1073/pnas.52.3.688.
• Scott, John (2000), Sociograms and Graph Theory, (вид. 2nd), Sage, с. 64—69, ISBN , архів оригіналу за 22 червня 2013, процитовано 20 березня 2016.
• ; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), Methods for visual understanding of hierarchical system structures, , SMC-11 (2): 109—125, doi:10.1109/TSMC.1981.4308636, MR 0611436.
• Tantau, Till (2013), Graph Drawing in TikZ, , 17 (4): 495—513, doi:10.7155/jgaa.00301.
• Zapponi, Leonardo (August 2003), (PDF), (Notices of the American Mathematical Society), 50: 788—789, архів оригіналу (PDF) за 3 березня 2016, процитовано 20 березня 2016.

Посилання

• GraphX library for .NET [ 26 січня 2018 у Wayback Machine.]: WPF бібліотека з відкритим кодом для обчислення та візуалізації графів. Підтримує багато макетів та алгоритмів з'єднання сторін.
• Graph drawing e-print archive [ 12 березня 2016 у Wayback Machine.]: включає інформацію на папері з усього (симпозіуму з зображення графів).
• Візуалізація графів, каталог посилань Open Directory Project для багатьох додаткових посиланнь, що зв'язані з візуалізацією графів.