Complex network analysis - NDMI096
Title: Analýza komplexních sítí
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
Teacher(s): doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
Mgr. Dávid Kubek
Opinion survey results   SS schedule   Noticeboard   
Annotation -
Many real-world systems, such as the human brain, Internet, or stock market possess a network structure. It has been numerously shown that these systems' analyses can benefit from characterization of corresponding networks. We deal with these complex networks in this course, see details in https://iuuk.mff.cuni.cz/~hartman/teach/graphs-and-networks/ In this course, we recap some basic properties from the preceding course https://iuuk.mff.cuni.cz/~hartman/teach/complex-network-analysis/ and develop selected extended topics. The course is designed for Master students
Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)
Course completion requirements -

The course is organized in lectures providing basic theory on topics given above. Seminars deal with theoretical as well as practical problems of complex networks.

Continuous evaluation is based on a particular combination of test and individual work based on theoretical or practical problems. This may even include particular project aiming towards potential (diploma) thesis. Final evaluation consists of combined an oral exam.

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)
Literature -

Basic literature

Barabási, A.-L. Network science. Cambridge university press, 2016.

Newman, MEJ Networks: An Introduction. Oxford University press, 2010.

Latora, V., Nicosia, V, Russo, G. Complex networks, Cambridge University Press, 2017.

Extended literature

Nešetřil, K., Ossona de Mendez. P. Sparsity: Graphs, Structures, and Algorithms. Springer, 2012.

Frieze, A., Karoñski, M. Introduction to Random Graphs. Cambridge University Press, 2015.

Godsil, C., Royle, G.F. Algebraic graph theory. Springer-Verlag, 2001.

Brouwer, A.E., Haemers, W. H. Spectra of Graphs. Springer, 2012.

Bollobas, B, Kozma, R., Miklós, D. Handbook of Large-Scale Random Networks, Springer, 2010.

Lovász, L. Large Networks and Graph Limits. American Mathematical Society colloquium publications. American Mathematical Society, 2012.

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)
Teaching methods -

Teaching can take both personal as well as distance forms. Further information is available on the teachers' website:

https://iuuk.mff.cuni.cz/~hartman/teach/complex-network-analysis/

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)
Requirements to the exam -

The requirements for the exam correspond to the syllabus of the course to the extent that it was covered in lectures, exercises and self-study. It is required as well as the ability to apply the acquired knowledge in solving examples or corresponding tasks.

The exam has just an oral form.

The exam can be in contact or distance form.

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)
Syllabus -

1) Introduction to complex networks and recap of basic properties

  • Intruduction to area of complex networks
  • Application examples such as social network, Inet, WWW, protein-protein
  • Description of basic notions and phenomena such as scale-free,

small-world, community structure, etc.

2) Overview of basic properties

  • recap of basic properties of centralities
  • recap of basic properties of community structure
  • recap of basic properties of random graphs

3) Network centrality

  • more on combinatorial properties of centralities
  • bounds on betweenness of graphs and various versions of betweeness
  • betweenness uniform graphs

4) Assortativity and similarity in complex networks

  • degree correlations
  • Homophily and assortative mixing
  • Similarity in networks

5) Spectral graph theory

  • introduction to spectral graph theory
  • properties of spectrum and laplacian specturm of a graph
  • complex network spectral properties and its utilizations

6) Properties of random graphs

  • Properties of ER random graphs
  • First moment methods
  • Second moment methods

7) Properties of real-world random graphs

  • Properties of configuration model
  • Proprties of BA model
  • Other models and their properties

8) Community structure

  • Recap of community detection
  • definition based on almost cliques and its NP-completeness
  • Maximizing modularity and its NP-completeness

9) Possibility of community detection

  • Definition of community detection general task
  • Kleinberger impossibility therem
  • generalizations of Kleinberger theorem

10) Processes on networks

  • general dynamic systems on networks
  • synchronization and stability
  • application and utilizations

11) Network motifs and graphlets

  • Introduction to network motifs counting
  • Introduction to graphlets
  • connection with network similarity and automorphisms

12) Introduction to sparsity

  • Various approaches to sparsity
  • Definition of bounded expansion
  • properties of graphs with bounded expansions

13) Application of bounded expansion

  • Application of bounded expansion for complex networks
  • Simplification of algorithms for networks with bounded expansion
  • Radnom graph models with bounded expansion

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2021)