SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Graphs and networks - NDMI110
Title: Grafy a sítě
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 5
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
Teaching methods: full-time
Guarantor: prof. RNDr. Martin Loebl, CSc.
Class: Informatika Bc.
Classification: Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science
Annotation -
Complex networks are models of real-world systems such as the human brain, social networks, protein interactions, WWW, or stock markets. The analysis of these networks can help understand underlying systems. This course provides a graph-theoretical introduction to these types of networks. This course is designed for the second-grade Bachelor students; see details at https://iuuk.mff.cuni.cz/~hartman/graphs-and-networks
Last update: Hubička Jan, doc. Mgr., Ph.D. (26.06.2021)
Course completion requirements -

The course is organized in lectures providing basic theory on topics given above. Seminars are divided into two groups:

1) Seminars providing theoretical exercises making students more familiar with the theory,

2) practical seminars where some phenomena will be tested on real-world networks.

Continuous evaluation is based on combination of test and individual work based on theoretical or practical problems. Final evaluation consists of combined written and oral exam.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)
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.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.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/graphs-and-networks/

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.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 a written and an oral part.

The exam can be in contact or distance form.

Last update: Hubička Jan, doc. Mgr., Ph.D. (04.06.2021)
Syllabus -

1) Introduction to complex networks

  • 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) Characteristic structure of a complex network

  • Simplified Scale-free (SF) property generalizing degree sequence
  • Simplified small-world (SW) property generalizing reachability

and local density

  • Simplified community structure (CS) generalizing cliques of graphs

3) Network centrality

  • Network centrality generalizing vertex degree, distinguising

local and global centrality

  • Centralities based on distances generalizing eccentricity such as

closeness centrality

  • Betweenness centrality and its combinatorial properties

4) Computations of centralities

  • Comutation of Betweenness centrality (BC) and issues for large graphs.
  • Algorithm of Brandes for Betweeneess centrality.
  • Some bounds for Betweenness centrality simplifying its computations.

5) Combinatorial properties of centralities

  • General bounds for betweeness centrality..
  • Effects on adding/removing vertices/edges on BC.
  • Graphs with global conditions on centralities such as betweenness

uniform graphs.

6) Eigenvector centrality

  • Introduction to basic necessary notions of spectral graph theory.
  • Definition of eigenvector centrality as generalization of degree

centrality.

  • Introduction of generalizations such as PageRank.

7) Introduction to random graph

  • Recap or introduction of notions from probability and statistics.
  • Definition of basic Erdos-Renyi (ER) graph.
  • Basic properties of ER graph including emmergence of a giant component.

8) Properties of random graphs

  • Definition of properties of random graph through a limiting property.
  • Basic properties of ER model.
  • Definition of real-world graphs properties such as Small-world or

scale-free.

9) Real-world random graphs

  • Requirements for real-world random networks.
  • Introduction of degree preservning models such as configuration

model (CM) and its properties.

  • Introduction of network growing models such as Barabasi-Albert

(BA) model ans its propertis.

10) Community structure

  • Introduction to community structure (CS) for a graph and

community detection (CD) problem.

  • Community structure as MAX-CUT problem and consequent algorithmic

complexity.

  • Hierarchical approach to community and Girvan-Newman algorithm.

11) Evaluating community using modularity

  • Introduction of modularity measure and its utilization in

Girvan-Newman algorithm.

  • Maximization of modularity and basic bounds for this measure.
  • Anti-community structure and minimal modularity values.

12) Processes on networks

  • General definition of a process on a network.
  • Example os SIR model for epidemic spreading.
  • Properties of network processes and their stability.

13) Extended topics (if time allows)

  • Network motifs as representants of frequent subgraphs in complex netwoprks.
  • Percolation theory representing suddent change in complex networks.
  • Graphlets as small subgraphs generalizing neighborhood.

Last update: Hubička Jan, doc. Mgr., Ph.D. (27.06.2021)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html