News

Course content

Network science is an exciting new field that studies large and complex networks, such as social, biological, and computer networks. The class will address topics from network structure and growth to community detection and the spread of epidemics. We study the diverse algorithmic techniques and mathematical models that are used to analyze such large networks, and give an in-depth description of the theoretical results that underlie them.

The class consists of essentially two parts. In the first part of the class, the lecturer will teach the mathematical models that underlie Network Science. To this end, we will mostly follow the book by Barabasi, which is available online for free. In the second part of the class, students will give short presentations on diverse topics for which they will write a term paper.

Material

Course work

For this class, you will have to work on the following.

Grading

In order to pass this class, you must have given a presentation and responded to one. Your grade will be 40% of the grade of the exam, 25% of the grade of the presentation, and 35% of the grade of the term paper. You will be given a bonus of 1 point if you participate in all but two of the student presentations, and of 0.5 point if you participate in all but three of the student presentations; no bonus will be given if you miss four or more student presentations. The number refers to the number of time slots (i.e. if you don't come on a Monday, this counts as 1 miss. Wednesday could count as 2 if you miss both time slots.) After adding the bonus, the total grade shall be capped at 10.

It is possible to do a re-exam. In order to qualify, you must have given a presentation for the class and responded to one.

Tentative class schedule

Week Monday 11-13 Wednesday 9-11 Wednesday 11-13 Deadlines
1 Intro
Barabasi Ch. 2
Random graphs
Barabasi Ch. 3
Tutorial on Ch. 2+3
Exercises
Submit topic selection before Thursday 17:00
2 Scale-free Networks
Barabasi Ch. 3 + 4
Barabasi-Albert model
Barabasi Ch. 4
Tutorial on Ch. 4
Exercises
Submit proposal before Saturday 08:00
3 Barabasi-Albert model
Barabasi Ch. 5
Evolving Networks
Barabasi Ch. 5+6
Tutorial on Ch. 5+6
Exercises
wc3_base.py
4 Robustness
Barabasi Ch. 8
Robustness
Barabasi Ch. 8
Tutorial on Ch. 8

Exercises
5 NO LECTURE
(Pentecost)
Spreading
Barabasi Ch. 10
No tutorial Submit draft literature survey on or before Monday, May 21
Definitive paper selection groups 1,2 on Wednesday
6 Spreading
Barabasi Ch. 10
Lecture groups 1,2 Tutorial on Ch. 10
Exercises
Definitive paper selection groups 3,4 on Monday
Definitive paper selection groups 5,6,7 on Wednesday
7 Lecture groups 3,4 Lecture groups 5,6 Lecture groups 7 Definitive paper selection groups 8,9 on Monday
Definitive paper selection groups 10,11,12 on Wednesday
8 Lecture groups 8,9 Lecture groups 10,11 Lecture groups 12 Definitive paper selection groups 13,14 on Monday
9 Lecture groups 13,14 Hand-in term paper on Saturday before 08:00
10 Final exam

Topics

Below is a list of potential topics, organized in broad categories. For each topic, I have suggested several papers from which you could start your literature search. It is also possible to propose your own topic. Further ideas that I have not explored yet: external-memory algorithms, algorithms for Kronecker graphs, algorithms for graph visualization/drawing, etc.

1. Polynomial-Time Algorithms: Limits and Beyond Limits

Recent research suggests that the polynomial-time algorithms known for many problems relevant to network science might not be improvable. This category contains a range of topics that explores this research, both from the perspective of lower bounds and of the different algorithmic approaches sought to circumvent them.

  1. [Ruben, Zino] Polynomial-time algorithms for computing paths and centrality indices
  2. This topic explores the fastest polynomial-time algorithms, including the ideas that shave log-factors from known running times.

  3. [Jasper, Stefan] Lower bounds for polynomial-time algorithms
  4. This topic explores the lower bounds known for polynomial-time algorithms, based on polynomial-time reductions between problems.

  5. [Daniel, Maaike] Approximation algorithms for polynomial-time problems
  6. This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by using approximation.

  7. [Ferenc, Ruben] Parameterized algorithms for polynomial-time problems
  8. This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by using parameterization.

  9. Faster algorithms on graph classes
  10. This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by making use of the structure of graph classes.

2. Dealing with Large Data Sets

Dealing with large data sets requires new computing paradigms. This category explores several paradigms that have been proposed in recent years.

  1. [Frank, Jelle] Streaming algorithms
  2. This topic explores how we can compute graph properties when not all the data can be stored in memory and the data is streamed.

  3. Sublinear-time algorithms
  4. This topic explores how we can obtain sublinear-time algorithms through the use of approximation and randomization.

  5. Graph compression
  6. This topic explores how we can compress graphs without using (too much) accuracy on the answer in order to speed up computations.

  7. [Gijs, Yorick] Sparsification
  8. This topic explores whether we can reduce the size of a graph for cut and distance problems and obtain a smaller network that mimicks the original.

  9. [Hristo, Niels] Sampling algorithms
  10. This topic explores how we can obtain fast algorithms for extremely large networks by only sampling a few parts of the graph and performing our computations only there.

3. Algorithms for Network Phenomena

Barabasi's book discusses many issues relevant for real-world networks, such as spreading, robustness, and community detection, but only rarely discusses potential algorithmic approaches to address these. This category explores the algorithms that are known for these issues.

  1. [Jonathan, Jop] Spreading: influence maximization and target set selection
  2. This topic explores how information can be effectively spread and which users to target for this.

  3. [Floris, Mats] Robustness: survivable network design
  4. This topic explores how we can add structures to networks to guarantee that they survive attacks and remain robust.

  5. [Chris, Daan] Community detection 1: graph partitioning
  6. This topic explores how to partition a graph into pieces with the idea to better understand the community structure of the graph.

  7. [Jimmy, Kevin, Tobias] Community detection 2: k-cores/clubs/plexes
  8. This topic explores how to detect communities in graphs using k-cores and its variants.

4. Biological networks

Much of the literature focusses on problems in social networks. However, there is equal interest for applications in biological networks. This category addresses topics in biological and medical networks, particularly with respect to classification.

  1. [Bart, Jasper, Lukas] Graph isomorphism and classification
  2. This topic explores how we can classify chemical and biological compounds by comparing different networks.

  3. Phylogeny and the classification of species
  4. This topic explores how we can discover which species are connected by comparing (for example) gene networks.

5. Practical computing at scale

In order to compute properties of large data sets, we need to use the latest computing technologies, such as MapReduce and GPGPUs. This category explores how to formalize these different technologies in computational models and how to design algorithms for them.

  1. [Naomi, Surabhi] Community detection 3: practical algorithms
  2. This topic explores practical, heuristic algorithms for community detection and why some of the concepts in the area are hard to compute.

  3. MapReduce algorithms
  4. This topic explores how the MapReduce framework can be used to compute graph properties efficiently.

  5. [Ivo, Joris] GPGPU algorithms
  6. This topic explores how GPGPUs can be used to compute graph properties efficiently.