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

Графічне представлення хвилинної фракції WWW, що зображує гіперпосилання

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

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

Графічні конвенції

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

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

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

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

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

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

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

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

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

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

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

• У системі силового компонування, программи зображення графів змінюють початкове розміщення вершин шляхом безперервного переміщення вершин відповідно до системи сил, заснованої на фізичних метафорах, пов'язаних з системами пружин або молекулярної механіки. Зазвичай, ці системи поєднують в собі сили тяжіння між сусідніми вершинами з силами відштовхування між усіма парами вершин, щоб знайти макет, в якому довжини сторін малі в той час як вершини добре розділені. Ці системи можуть виконуати метод найшвидшого спуску на основі мінімізації з функції енергії, або ж вони можуть перевести свої сили безпосередньо в швидкості або прискорення для рухомих вершин.
• Метод спектрального макету використовує власні вектори матриці такі як Лапласів отриманного з матриці суміжності графа.
• Ортогональні методи компонування, що дозволяють ребрам графа йти горизонтально або вертикально, паралельно осям координат макета. Ці методи були спочатку розроблені для НВІС, [[Друкована плата|ДП ] ] і проблем компонування, але вони також були пристосовані до зображення графів.

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

• Алгоритми макету дерева показують корінь дерева- як формацію, що підходить для [[дерева ( теорії графів ) | дерева ] ] . Часто , в техніці під назвою " Повітряна куля макета " , нащадки кожного вузла в дереві намальовані на окружності навколо вузла , з радіусами цих кіл спадної на більш низьких рівнях в дереві так , щоб ці кола не перетинаються. Зазвичай, у техніці, що називається "Кульовий макет", нащадок кожного вузла у дереві малюється на колі, що оточує вузол, із радіусом цих кіл, спадаючими на нижчих рівнях дерева так, щоб ці кола не накладалися одне на одного.
• Методи багаторівневого зображення графу ( часто звані зображення у стилі Сугияма ) найкраще підходять для орієнтованного ациклічного графу або графів, близьких до ациклічних, таких як графи залежностей між модулями або функціями в програмній системі. У цих методах, вузли графа розташовані на горизонтальних шарах з використанням методів, таких як Алгоритм Коффмана-Грекхема, таким чином, що більшість ребер йдуть вниз від одного шару до іншого; після цього кроку, вузли в межах кожного шару виконані з метою мінімізації перетинів.

Arc diagram

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

Додатки-особливі зображення графів

Graphs and graph drawings arising in other areas of application include

• Sociograms, drawings of a social network, as often offered by social network analysis software
• Hasse diagrams, a type of graph drawing specialized to partial orders
• Dessin d'enfants, a type of graph drawing used in algebraic geometry
• State diagrams, graphical representations of finite state machines
• Computer network diagrams, depictions of the nodes and connections in a computer network
• Flow charts, drawings in which the nodes represent the steps of an algorithm and the edges represent control flow between steps.
• Data flow diagrams, drawings in which the nodes represent the components of an information system and the edges represent the movement of information from one component to another.
• Bioinformatics including phylogenetic trees, protein-protein interaction networks, and metabolic pathways.

In addition, the placement and routing steps of electronic design automation (EDA) are similar in many ways to graph drawing, as is the problem of greedy embedding in distributed computing, and the graph drawing literature includes several results borrowed from the EDA literature. However, these problems also differ in several important ways: for instance, in EDA, area minimization and signal length are more important than aesthetics, and the routing problem in EDA may have more than two terminals per net while the analogous problem in graph drawing generally only involves pairs of vertices for each edge.

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

Software, systems, and providers of systems for drawing graphs include:

• BioFabric, open-source software from the Institute of Systems Biology for visualizing large networks by drawing nodes as horizontal lines.
• Cytoscape, open-source software for visualizing molecular interaction networks
• Gephi, open-source network analysis and visualization software
• Graphviz, an open-source graph drawing system from AT&T Corporation
• Mathematica, a general purpose computation tool that includes 2D and 3D graph visualization and graph analysis tools.
• Microsoft Automatic Graph Layout, a .NET library (formerly called GLEE) for laying out graphs
• Tom Sawyer Software Tom Sawyer Perspectives is graphics-based software for building enterprise-class graph and data visualization and analysis applications. It is a Software Development Kit (SDK) with a graphics-based design and preview environment.
• Tulip (software), an open source data visualization tool
• yEd, a graph editor with graph layout functionality
• PGF/TikZ 3.0 with the graphdrawing package (requires LuaTeX).

Посилання

Footnotes

General references

• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), Algorithms for Drawing Graphs: an Annotated Bibliography, Computational Geometry: Theory and Applications, 4: 235—282, doi:10.1016/0925-7721(94)00014-x.
• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4.
• Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, 6 (1): 24—43, doi:10.1109/2945.841119.
• Jünger, Michael; Mutzel, Petra (2004), Graph Drawing Software, Springer-Verlag, ISBN 978-3-540-00881-1.
• Kaufmann, Michael; Wagner, Dorothea, ред. (2001), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, т. 2025, Springer-Verlag, doi:10.1007/3-540-44969-8.
• Tamassia, Roberto, ред. (2014), Handbook of Graph Drawing and Visualization, CRC Press.

Specialized subtopics

• Anderson, James Andrew; Head, Thomas J. (2006), Automata Theory with Modern Applications, Cambridge University Press, с. 38—41, ISBN 978-0-521-84887-9.
• Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), Biological Networks, у Tamassia, Roberto (ред.), Handbook of Graph Drawing and Visualization, CRC Press, с. 621—651.
• Bastert, Oliver; Matuszewski, Christian (2001), Layered drawings of digraphs, у Kaufmann, Michael; Wagner, Dorothea (ред.), 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), Theory of Spectral Graph Layout, Tech. Report MSR-TR-94-04, Microsoft Research.
• Brandes, Ulrik; Freeman, Linton C.; Wagner, Dorothea (2014), Social Networks, у Tamassia, Roberto (ред.), Handbook of Graph Drawing and Visualization, CRC Press, с. 805—839.
• Di Battista, Giuseppe; Rimondini, Massimo (2014), Computer Networks, у Tamassia, Roberto (ред.), 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; Wagner, Dorothea (ред.), 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.
• Garg, Ashim; Tamassia, Roberto (1995), Upward planarity testing, Order, 12 (2): 109—133, doi:10.1007/BF01108622, MR 1354797.
• Holten, Danny; Isenberg, Petra; van Wijk, Jarke J.; Fekete, Jean-Daniel (2011), An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs, IEEE Pacific Visualization Symposium (PacificVis 2011) (PDF), с. 195—202, doi:10.1109/PACIFICVIS.2011.5742390.
• Holten, Danny; van Wijk, Jarke J. (2009), A user study on visualizing directed edges in graphs, Proceedings of the 27th International Conference on Human Factors in Computing Systems (CHI '09) (PDF), с. 2299—2308, doi:10.1145/1518701.1519054.
• Koren, Yehuda (2005), Drawing graphs by eigenvectors: theory and practice (PDF), Computers & Mathematics with Applications, 49 (11-12): 1867—1888, doi:10.1016/j.camwa.2004.08.015, MR 2154691.
• Longabaugh, William (2012), Combing the hairball with BioFabric: a new approach for visualization of large networks (PDF), BMC Bioinformatics, 13: 275, doi:10.1186/1471-2105-13-275, PMID 23102059{{citation}}: Обслуговування 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; Nishizeki, Takao; Quan, Wu (ред.), Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers, Lecture Notes in Computer Science, т. 4875, Springer-Verlag, с. 389—394, doi:10.1007/978-3-540-77537-9_38.
• Pach, János; Sharir, Micha (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.
• 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, Social network analysis: a handbook (вид. 2nd), Sage, с. 64—69, ISBN 978-0-7619-6339-4.
• Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109—125, doi:10.1109/TSMC.1981.4308636, MR 0611436.
• Tantau, Till (2013), Graph Drawing in TikZ, Journal of Graph Algorithms and Applications, 17 (4): 495—513, doi:10.7155/jgaa.00301.
• Zapponi, Leonardo (August 2003), What is a Dessin d'Enfant (PDF), Notices of the American Mathematical Society, 50: 788—789.

Зовнішні посилання

• GraphX library for .NET: open-source WPF library for graph calculation and visualization. Supports many layout and edge routing algorithms.
• Graph drawing e-print archive: including information on papers from all Graph Drawing symposia.
• Візуалізація графів, каталог посилань Open Directory Project for many additional links related to graph drawing.