### 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:

### Course Objective

After taking this course, you will be able to describe what the scienceof 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 increasedconnectivity 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 ortwo 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 thefinal 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 Theoryand Complex Networks: An Introduction.

2010". Online available through www.distributed_systems.net. Some other

topics are described in several online papers.