Бакалавриат 2020/2021

Анализ и визуализация сетей

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 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
  1. The classification of graph analysis tasks.
  2. Main approaches to graph algorithms.
  3. Graph data file formats.
  4. Graph databases.
  5. The pool of main network analysis tools.
• Graphs, topology and geometry
  1. Adjacency and neighbourhood.
  2. Hierarchies, trees and taxonomies.
  3. Cliques and dense fragments.
  4. Centrality.
  5. Planarity.
• Visualization of small graphs: drawing and layout
  1. The classification of goals and constraints.
  2. Symmetry-based approaches.
  3. Hierarchical approaches.
  4. Iterative approaches.
  5. Force-directed drawing.
  6. Orthogonal drawing.
  7. Radial and circular drawing.
  8. Treemaps.
  9. Geographic layout and maps.
• Visualization of large graphs
  1. Scalability.
  2. Graph fragments and filters.
  3. Approximate drawing.
  4. Random walks and other randomization techniques.
• Interactive visualization of graphs
  1. Zoom, scale, pan, rotate.
  2. Dynamic visualization.
  3. Best practices in user interaction.
• Visualization of graphs and networks in real world applications
  1. Social networks analysis.
  2. Logistics and supply chains.
  3. Cheminformatics.
  4. Bioinformatics
• 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.