Networks and Graphs

2018-2019
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

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 15 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
- peer-to-peer computer systems
- 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

The course takes the form of lectures, exercise classes and homework
assignments.

Toetsvorm

A combination of exams and homework assessments.

Literatuur

Van Steen, M., Graph Theory and Complex Networks: An Introduction.
2010. Online avaiable through www.distributed_systems.net .

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: