Networks and Graphs

2019-2020
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

Doel vak

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

Inhoud vak

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.

Onderwijsvorm

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.

Toetsvorm

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.

Literatuur

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.

Doelgroep

1CS, 1-IMM.

Algemene informatie

Vakcode X_401010
Studiepunten 6 EC
Periode P5
Vakniveau 200
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator J. Urbani
Examinator J. Urbani
Docenten J. Urbani

Praktische informatie

Voor dit vak moet je zelf intekenen.

Voor dit vak kun je last-minute intekenen.

Werkvormen Werkcollege, Deeltoets extra zaalcapaciteit, Hoorcollege
Doelgroepen

Dit vak is ook toegankelijk als: