460-4055/01 – Graph Algorithms and Complex Networks (GAKS)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantorRNDr. Eliška Ochodková, Ph.D.Subject version guarantorRNDr. Eliška Ochodková, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year2Semesterwinter
Study languageCzech
Year of introduction2011/2012Year of cancellation2014/2015
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
OH140 RNDr. Eliška Ochodková, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+1
Part-time Credit and Examination 10+0

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/

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

Full-time form (validity from: 2011/2012 Winter semester, validity until: 2014/2015 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 45  23
        Examination Examination 55  20 3
Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner
V - ECTS - mgr. 2014/2015 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - mgr. 2013/2014 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - mgr. 2012/2013 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - mgr. 2011/2012 Full-time Czech Optional 401 - Study Office stu. block

Assessment of instruction



2014/2015 Winter
2013/2014 Winter
2011/2012 Winter