- May 29: Added RUBRICS for grading of presentation and term paper. See the section on course work.
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.
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 in-depth 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 mid-way 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 A4-paper 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 30-35 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.
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|
Barabasi Ch. 2
Barabasi Ch. 3
|Tutorial on Ch. 2+3
|Submit topic selection before Thursday 17:00|
Barabasi Ch. 3 + 4
Barabasi Ch. 4
|Tutorial on Ch. 4
|Submit proposal before Saturday 08:00|
Barabasi Ch. 5
Barabasi Ch. 5+6
|Tutorial on Ch. 5+6
Barabasi Ch. 8
Barabasi Ch. 8
|Tutorial on Ch. 8
Barabasi Ch. 10
|No tutorial||Submit draft literature survey on or before Monday, May 21
Definitive paper selection groups 1,2 on Wednesday
Barabasi Ch. 10
|Lecture groups 1,2||Tutorial on Ch. 10
|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|
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.
- [Ruben, Zino] Polynomial-time algorithms for computing paths and centrality indices
This topic explores the fastest polynomial-time algorithms, including the ideas that shave log-factors from known running times.
- Brandes, A Faster Algorithm for Betweenness Centrality
- Chan, More algorithms for all-pairs shortest paths in weighted graphs
- Williams, Faster all-pairs shortest paths via circuit complexity
This topic explores the lower bounds known for polynomial-time algorithms, based on polynomial-time reductions between problems.
- 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
This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by using approximation.
- 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, All-Pairs Almost Shortest Paths
This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by using parameterization.
- 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 clique-width graphs
This topic explores how we can speed up algorithms for known polynomial-time-solvable problems by making use of the structure of graph classes.
- Cabello, Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Chepoi, Dragan, A linear-time algorithm for finding a central vertex of a chordal graph
- Atallah, Chen, Lee, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
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
This topic explores how we can compute graph properties when not all the data can be stored in memory and the data is streamed.
- 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
This topic explores how we can obtain sublinear-time algorithms through the use of approximation and randomization.
- Czumaj, Sohler, Sublinear-time algorithms
- Indyk, Mahabadi, Rubinfeld, Vakilian, Yodpinyanee, Set Cover in Sub-linear Time
- Gonen, Ron, Counting Stars and Other Small Subgraphs in Sublinear Time
This topic explores how we can compress graphs without using (too much) accuracy on the answer in order to speed up computations.
- Fedor, Motwani, Clique Partitions, Graph Compression and Speeding-Up Algorithms
- Chierichetti, Kumar, Lattanzi, Mitzenmacher, Panconesi, Raghavan, On Compressing Social Networks
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.
- Krauthgamer, Rika, Mimicking Networks and Succinct Representations of Terminal Cuts
- Gajjar, Radhakrishnan, Distance-Preserving Subgraphs of Interval Graphs
- Goranci, Henzinger, Peng, Improved Guarantees for Vertex Sparsification in Planar Graphs
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.
- Cohen, Size-Estimation Framework with Applications to Transitive Cluster and Reachability
- Riondato, Kornaropoulos, Fast approximation of betweenness centrality through sampling
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.
- [Jonathan, Jop] Spreading: influence maximization and target set selection
This topic explores how information can be effectively spread and which users to target for this.
- 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
This topic explores how we can add structures to networks to guarantee that they survive attacks and remain robust.
- Bang-Jensen, 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
This topic explores how to partition a graph into pieces with the idea to better understand the community structure of the graph.
- Xiao, An Improved Divide-and-Conquer ALgorithm for Finding All Minimum k-Way Cuts
- Kernighan, Lin, An efficient heuristic procedure for partitioning graphs
- Kawarabayahsi, Thorup, Minimum k-way cut of bounded size is fixed-parameter tractable
- Buluc, Meyerhenke, Safro, Sanders, Schulz, Recent Advances in Graph Partitioning
This topic explores how to detect communities in graphs using k-cores and its variants.
- 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 Small-Diameter Subgraphs
- Bhawalkar, Kleinberg, Lewi, Roughgarden, Sharma, Preventing Unraveling in Social Networks: The Anchored k-Core Problem
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
This topic explores how we can classify chemical and biological compounds by comparing different networks.
- Shervashidze, Schweitzer, van Leeuwen, Mehlhorn, Borgwardt, Weisfeiler-Lehman Graph Kernels
- Babai, Luks, Canonical labeling of graphs
This topic explores how we can discover which species are connected by comparing (for example) gene networks.
- van Iersel, Hoe zijn ze verwant?
- Rodrigues, Sagot, Wakabayashi, The maximum agreement forest problem: Approximation algorithms and computational experiments
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
This topic explores practical, heuristic algorithms for community detection and why some of the concepts in the area are hard to compute.
- Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, Wagner, Maximizing Modularity is hard
- Traag, Faster unfolding of communities: speeding up the Louvain algorithm
This topic explores how the MapReduce framework can be used to compute graph properties efficiently.
- 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
This topic explores how GPGPUs can be used to compute graph properties efficiently.
- Djidjev, Chapuis, Andonov, Thulasidasan, Lavenier, All-Pairs Shortest Path algorithms for planar graphs for GPU-accelerated clusters
- Katz, Kider, All-pairs shortest-paths for large graphs on the GPU