Networks and Graphs

2019-2020

Course Objective

After taking this course, you will be able to describe what the science
of networks is all about, making use of terminology from graph theory
and basic probabilities. You will also be able to use (simple) discrete
math for notations and proofs. In particular, you can
- model simple real-world situations expressed in graphs/networks
- show the (in)correctness of mathematical statements about graphs
- construct networks and conduct simple analyses of existing ones
- read and understand introductory, popular texts on networks

There are eight learning goals:

G1: Learn the basic notions and notations used in Graph Theory
G2: Learn the various types of graphs and their properties
G3: Familiarize with standard algorithms that work on graphs
G4: Familiarize with well- known applications of complex networks on the
Web and social networks
G5: Learn the most important models for complex networks and be able to
compare them
G6: Use existing metrics for the analysis of complex networks
G7: Learn to argument using a formal language about properties of graphs
and graph algorithms
G8: Able to model a realistic situation using a graph and/or complex
network

Course Content

The world around us is becoming increasingly connected. This increased
connectivity is leading to new phenomena that are not that easy to
understand:

- why is it difficult, if not impossible, to remove data from the Web?
- why does the Internet continue to function despite big disasters?
- why is Google so effective and efficient?
- why are navigation systems so responsive to traffic jams?
- why do certain diseases spread so rapidly and others not?

The core of the answers to these questions is formed by the notion of
"network:" a mathematical concept consisting of nodes that are joined by
edges. Networks are also called graphs. In the last 20 years we have
seen an increase in interests for networks/graphs. Many real-world
phenomena turned out to be conveniently modeled by networks, and in such
a way that it allowed us to better understand those phenomena.

In this course, graph theory and its applications are the main focus
point. We'll be paying attention to the math that underlies graphs and
networks, as well as the application to real-world situations. In
particular, you will be conducting simple experiments dealing with the
construction and analyses of networks. Application domains that are
discussed are selected from:

- the Internet
- the Web
- biological networks
- social communities and online social networks

We'll putting emphasis on:

1. Standard mathematical terminology and techniques, including:

- directed and undirected graphs
- planar graphs
- graph embeddings
- edge and vertex coloring
- optimal routing
- trees

2. Experimental analyses of networks.

To this end, we'll be discussing various ways to measure network
properties, like the relative position of (important) nodes, clustering
coefficients, diameter, eccentricities, and so on.

Teaching Methods

There are two main lectures per week. Moreover, there are also one or
two exercise classes per week. Attendance is not mandatory but highly
encouraged.

Method of Assessment

The final grade is determined by two written exams: The midterm and the
final exam. Both exams account for 50% of the total grade. There are
also four mandatory homework assignments. Students need to pass at least
one homework in the first part of the course and one homework in the
second part of the course to be admitted to the exams.

Literature

Most of the material is covered in the book "Van Steen, M., Graph Theory
and Complex Networks: An Introduction.
2010". Online available through www.distributed_systems.net. Some other
topics are described in several online papers.

Target Audience

1CS, 1-IMM.

General Information

Course Code X_401010
Credits 6 EC
Period P5
Course Level 200
Language of Tuition English
Faculty Faculty of Science
Course Coordinator J. Urbani
Examiner J. Urbani
Teaching Staff J. Urbani

Practical Information

You need to register for this course yourself

Last-minute registration is available for this course.

Teaching Methods Seminar, Lecture
Target audiences

This course is also available as: