Networks and Graphs

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
• conduct simple analyses of networks, and construct networks, using Mathematica
• read and understand introductory, popular texts on networks

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 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.

TEACHING METHODS
The course takes the form of lectures, excercise classes with mandatory tasks, and homework assignments. Mathematica is used to construct, analyze, and visualize graphs.

TYPE OF ASSESSMENT
A combination of exams and homework assessments. Details can be found on www.distributed-systems.net