News
 May 29: Added RUBRICS for grading of presentation and term paper. See the section on course work.
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 indepth 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
 A. Barabasi, Network Science. For free online and at bol.com and Amazon.com
 Papers
Course work
For this class, you will have to work on the following.
 Exam: There will be an exam on the studied chapters of the book by Barabasi.
 Term paper (in pairs): Students are challenged to explore a topic in Network Science, for which they will write a term paper. The term paper should contain a comprehensive literature study on their topic as well as an indepth explanation of the material of two papers of their choosing on the topic. Students are to work in pairs, although each student should individually write their explanation of one of the two selected papers. So the papers should consist of a section introducing the topic and the literature, a section on Paper 1, a section on Paper 2, and a conclusion where you mention relevant open questions or other remarks of interest. The selected papers should be announced and discussed with the lecturer around the midway point of the class, as per the deadlines in the class schedule. The term paper should be written in English, be roughly 10 pages long (max. 15) on A4paper with 11pt font, and submitted as PDF. The deadline is Saturday, June 23, 08:00. RUBRICS
 Presentation (in pairs): Students are expected to give a presentation on their topic in English. The presentation should last 3035 minutes, and allow at least 10 minutes for a discussion with the responders (see below) and other students. RUBRICS
 Respond: Students will be assigned one presentation for which they are a responder (this implies exactly two responders per presentation). Responders should prepare (at least) two questions on the presented material and submit these questions to the lecturer (at least) one day prior to the presentation.
 Participate: Students are encouraged to participate actively in the class. For the student presentations, attendance is recorded.
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 reexam. In order to qualify, you must have given a presentation for the class and responded to one.
Tentative class schedule
Week  Monday 1113  Wednesday 911  Wednesday 1113  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  Scalefree Networks Barabasi Ch. 3 + 4 
BarabasiAlbert model Barabasi Ch. 4 
Tutorial on Ch. 4 Exercises 
Submit proposal before Saturday 08:00 
3  BarabasiAlbert 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  Handin 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: externalmemory algorithms, algorithms for Kronecker graphs, algorithms for graph visualization/drawing, etc.
1. PolynomialTime Algorithms: Limits and Beyond Limits
Recent research suggests that the polynomialtime 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.
 [Ruben, Zino] Polynomialtime algorithms for computing paths and centrality indices
 Brandes, A Faster Algorithm for Betweenness Centrality
 Chan, More algorithms for allpairs shortest paths in weighted graphs
 Williams, Faster allpairs shortest paths via circuit complexity
 [Jasper, Stefan] Lower bounds for polynomialtime algorithms
 Vassilevska Williams, Hardness of Easy Problems
 Abboud, Grandoni, Vassilevska Williams, Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
 Goldstein, Kopelowitz, Lewenstein, Porat, Conditional Lower Bounds for Space/Time Tradeoffs
 [Daniel, Maaike] Approximation algorithms for polynomialtime problems
 Roddity, Vassilevska Williams, Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
 Abboud, Vassilevska Williams, Wang, Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
 Dor, Halperin, Zwick, AllPairs Almost Shortest Paths
 [Ferenc, Ruben] Parameterized algorithms for polynomialtime problems
 Brach, Cygan, Lacki, Sankowski, Algorithmic Complexity of Power Law Networks
 Cabello, Knauer, Algorithms for graphs of bounded treewidth via orthogonal range searching
 Coudert, Ducoffe, Popa, Fully polynomial FPT algorithms for some classes of bounded cliquewidth graphs
 Faster algorithms on graph classes
 Cabello, Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
 Chepoi, Dragan, A lineartime algorithm for finding a central vertex of a chordal graph
 Atallah, Chen, Lee, An optimal algorithm for shortest paths on weighted interval and circulararc graphs, with applications
This topic explores the fastest polynomialtime algorithms, including the ideas that shave logfactors from known running times.
This topic explores the lower bounds known for polynomialtime algorithms, based on polynomialtime reductions between problems.
This topic explores how we can speed up algorithms for known polynomialtimesolvable problems by using approximation.
This topic explores how we can speed up algorithms for known polynomialtimesolvable problems by using parameterization.
This topic explores how we can speed up algorithms for known polynomialtimesolvable 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.
 [Frank, Jelle] Streaming algorithms
 McGregor, Graph Stream Algorithms: A Survey
 Zelke, Algorithms for streaming graphs
 Braverman, Ostrovsky, Vilenchik, How Hard is Counting Triangles in the Streaming Model
 Kane, Mehlhorn, Sauerwald, Sun, Counting Arbitrary Subgraphs in Data Streams
 Sublineartime algorithms
 Czumaj, Sohler, Sublineartime algorithms
 Indyk, Mahabadi, Rubinfeld, Vakilian, Yodpinyanee, Set Cover in Sublinear Time
 Gonen, Ron, Counting Stars and Other Small Subgraphs in Sublinear Time
 Graph compression
 Fedor, Motwani, Clique Partitions, Graph Compression and SpeedingUp Algorithms
 Chierichetti, Kumar, Lattanzi, Mitzenmacher, Panconesi, Raghavan, On Compressing Social Networks
 [Gijs, Yorick] Sparsification
 Krauthgamer, Rika, Mimicking Networks and Succinct Representations of Terminal Cuts
 Gajjar, Radhakrishnan, DistancePreserving Subgraphs of Interval Graphs
 Goranci, Henzinger, Peng, Improved Guarantees for Vertex Sparsification in Planar Graphs
 [Hristo, Niels] Sampling algorithms
This topic explores how we can compute graph properties when not all the data can be stored in memory and the data is streamed.
This topic explores how we can obtain sublineartime algorithms through the use of approximation and randomization.
This topic explores how we can compress graphs without using (too much) accuracy on the answer in order to speed up computations.
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.
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 realworld 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.
 [Jonathan, Jop] Spreading: influence maximization and target set selection
 Kempe, Kleinberg, Tardos, Maximizing the Spread of Influence through a Social Network
 Bazgan, Chopin, Nichterlein, Sikora, Parameterized approximability of maximizing the spread of influence in networks
 Charikar, Naamad, Wirth, On Approximating Target Set Selection
 [Floris, Mats] Robustness: survivable network design
 BangJensen, Basavaraju, Klinkby, Misra, Ramanujan, Saurabh, Zehavi, Parameterized Algorithms for Survivable Network Design with Uniform Demands
 Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem
 [Chris, Daan] Community detection 1: graph partitioning
 Xiao, An Improved DivideandConquer ALgorithm for Finding All Minimum kWay Cuts
 Kernighan, Lin, An efficient heuristic procedure for partitioning graphs
 Kawarabayahsi, Thorup, Minimum kway cut of bounded size is fixedparameter tractable
 Buluc, Meyerhenke, Safro, Sanders, Schulz, Recent Advances in Graph Partitioning
 [Jimmy, Kevin, Tobias] Community detection 2: kcores/clubs/plexes
 Pattillo, Youssef, Butenko, On clique relaxation models in network analysis
 Batagelj, Zaversnik, An O(m) Algorithm for Cores Decomposition of Networks
 Schafer, Komusiewicz, Moser, Niedermeier, Parameterized Computational Complexity of Finding SmallDiameter Subgraphs
 Bhawalkar, Kleinberg, Lewi, Roughgarden, Sharma, Preventing Unraveling in Social Networks: The Anchored kCore Problem
This topic explores how information can be effectively spread and which users to target for this.
This topic explores how we can add structures to networks to guarantee that they survive attacks and remain robust.
This topic explores how to partition a graph into pieces with the idea to better understand the community structure of the graph.
This topic explores how to detect communities in graphs using kcores 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.
 [Bart, Jasper, Lukas] Graph isomorphism and classification
 Shervashidze, Schweitzer, van Leeuwen, Mehlhorn, Borgwardt, WeisfeilerLehman Graph Kernels
 Babai, Luks, Canonical labeling of graphs
 Phylogeny and the classification of species
 van Iersel, Hoe zijn ze verwant?
 Rodrigues, Sagot, Wakabayashi, The maximum agreement forest problem: Approximation algorithms and computational experiments
This topic explores how we can classify chemical and biological compounds by comparing different networks.
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.
 [Naomi, Surabhi] Community detection 3: practical algorithms
 Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, Wagner, Maximizing Modularity is hard
 Traag, Faster unfolding of communities: speeding up the Louvain algorithm
 MapReduce algorithms
 Karloff, Suri, Vassilvitskii, A Model of Computation for MapReduce
 Pagh, Tsourakakis, Colorful Triangle Counting and a MapReduce Implementation
 Kumar, Moseley, Vassilvitskii, Vattani, Fast Greedy Algorithms in MapReduce and Streaming
 Kang, Papadimitriou, Sun, Tong, Centralities in large Networks: Algorithms and Observations
 [Ivo, Joris] GPGPU algorithms
 Djidjev, Chapuis, Andonov, Thulasidasan, Lavenier, AllPairs Shortest Path algorithms for planar graphs for GPUaccelerated clusters
 Katz, Kider, Allpairs shortestpaths for large graphs on the GPU
This topic explores practical, heuristic algorithms for community detection and why some of the concepts in the area are hard to compute.
This topic explores how the MapReduce framework can be used to compute graph properties efficiently.
This topic explores how GPGPUs can be used to compute graph properties efficiently.