Бакалавриат
2019/2020
Анализ и визуализация сетей
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Язык:
английский
Кредиты:
4
Контактные часы:
46
Course Syllabus
Abstract
This course introduces methods and algorithms for analysing and visualizing graphs and networks. The course includes a review of modern network analysis and visualization techniques with their applications in various domains. We will concern on three main topics: network analysis methods based on applied graph theory, graph drawing algorithms, applications of network analysis and visualization to real problems.
Learning Objectives
- To know the classification of main network analysis tasks, basic methods and algorithms, most popular software tools.
- To be able to define a graph-theoretic description of network analysis task and corresponding network visualization requirements.
- To be able to select reasonably an appropriate project solutions and tools for network analysis workflow.
- To be able to develop a new variants of graph drawing algorithms.
Expected Learning Outcomes
- Students know the basic concepts of analysing and visualizing graphs and networks.
- Students select and justify appropriate graph drawing method and algorithm.
- Students design and solve graph-theoretical mathematical models.
- Students use development techniques, skills and tools necessary to network visualization.
Course Contents
- Introduction<ol style="list-style-type: decimal;"><li>The classification of graph analysis tasks.</li> <li>Main approaches to graph algorithms.</li> <li>Graph data file formats.</li> <li>Graph databases.</li> <li>The pool of main network analysis tools.</li></ol>
- Graphs, topology and geometry<ol style="list-style-type: decimal;"><li>Adjacency and neighbourhood.</li> <li>Hierarchies, trees and taxonomies.</li> <li>Cliques and dense fragments.</li> <li>Centrality.</li> <li>Planarity.</li></ol>
- Visualization of small graphs: drawing and layout<ol style="list-style-type: decimal;"><li>The classification of goals and constraints.</li> <li>Symmetry-based approaches.</li> <li>Hierarchical approaches.</li> <li>Iterative approaches.</li> <li>Force-directed drawing.</li> <li>Orthogonal drawing.</li> <li>Radial and circular drawing.</li> <li>Treemaps.</li> <li>Geographic layout and maps.</li></ol>
- Visualization of large graphs<ol style="list-style-type: decimal;"><li>Scalability.</li> <li>Graph fragments and filters.</li> <li>Approximate drawing.</li> <li>Random walks and other randomization techniques.</li></ol>
- Interactive visualization of graphs<ol style="list-style-type: decimal;"><li>Zoom, scale, pan, rotate.</li> <li>Dynamic visualization.</li> <li>Best practices in user interaction.</li></ol>
- Visualization of graphs and networks in real world applications<ol style="list-style-type: decimal;"><li>Social networks analysis.</li> <li>Logistics and supply chains.</li> <li>Cheminformatics.</li> <li>Bioinformatics</li></ol>
- Modern trends in graph databases and network analysis software
Assessment Elements
- Home assignment 1
- Home assignment 2
- Home assignment 3
- In-class assignments
- Individual project
Interim Assessment
- Interim assessment (3 module)0.15 * Home assignment 1 + 0.15 * Home assignment 2 + 0.15 * Home assignment 3 + 0.15 * In-class assignments + 0.4 * Individual project
Bibliography
Recommended Core Bibliography
- Brath, R., Jonker, D. Graph Analysis and Visualization: Discovering Business Opportunity in Linked Data. – Wiley, 2015. – 513 pp.
Recommended Additional Bibliography
- Newman, M., Watts, D. J., and Barabási, A. The Structure and Dynamics of Networks. – Princeton University Press, 2006. – 592 pp.