460-4055/01 – Graph Algorithms and Complex Networks (GAKS)
| Gurantor department | Department of Computer Science | Credits | 4 |
| Subject guarantor | RNDr. Eliška Ochodková, Ph.D. | Subject version guarantor | RNDr. Eliška Ochodková, Ph.D. |
| Study level | undergraduate or graduate | Requirement | Optional |
| Year | 2 | Semester | winter |
| | Study language | Czech |
| Year of introduction | 2011/2012 | Year of cancellation | 2014/2015 |
| Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
After graduation student will be able to:
1. For solving given problems choose proper graph algorithms and implemnt it.
2. Experiment with chosen datasets and analyze achieved results.
3. Interpret experiments results and design possible modifications of used algorithms.
4. Summarize properties of real networks represented by used dataset.
5. Cooperate on project.
Teaching methods
Lectures
Tutorials
Project work
Summary
The goal is to acquaint students with complex networks, the area with a broad interdisciplinary overlap. Complex networks are a real wide area network (technological, informational, social and biological) whose characteristics, individual models and the development is the sstudy subject. The main subject areas of interest are the types of complex networks, efficient algorithms for network analysis, mathematical models of networks, generative models and dynamic processes in networks. Because the network is modeled as a graph, an essential part of the course is a repeatition or supplement of necessary mathematical tools from graph theory, linear algebra and statistics.
Compulsory literature:
1. M. E. J. Newman: The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003
2. A.L. Barabasi: Scale Free Networks
3. S. H. Strogatz: Exploring Complex Networks
4. R. Albert and L.A. Barabasi: Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002).
7. McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990.
8. Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990.
9. Bang-Jensen J., Guitn G.: Digraphs, Theory, Algorithms and Applications, Springer 2002
10. Jungnickel D.: Graphs, Networks and Algorithms, Springer 2005
Recommended literature:
1. The Stony Brook Algorithm Repository, http://www.cs.sunysb.edu/~algorith/
2. Journal of Graph Algorithms and Applications, ISSN: 1526-1719, http://www.cs.brown.edu/publications/jgaa/
Additional study materials
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Additional requirements are placed on the student.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
1. Introduction. Complex networks and their types. Empirical studies of complex networks.
2. Properties of networks.
3. Computer network representation.
4. Mathematical foundations of complex networks.
5. Graph theory and its applications in the field of complex networks.
6. Measurements and metrics for network analysis.
7. Fundamental algorithms.
8. Network model - a random network, Watts-Strogatz model.
9. Network model - scale-free network.
10. Models of network evolution.
11. Detection communities.
12. Processes in Networks - percolation, spreading of information.
13. Visualization of networks, algorithms used.
14. Software for work with complex networks.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction