Bachelor
2020/2021
Analysis and Visualization of Networks
Type:
Elective course (Applied Mathematics and Information Science)
Area of studies:
Applied Mathematics and Information Science
Delivered by:
School of Data Analysis and Artificial Intelligence
Where:
Faculty of Computer Science
When:
4 year, 3 module
Mode of studies:
distance learning
Language:
English
ECTS credits:
4
Contact hours:
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.