Milestones in Network Science
Seminar, Winter 26
Note
The kick-off will take place on 12 October 13:30.
This proseminar teaches the basics of academic writing and literature research, using topics selected from a few milestone papers in the area of network science.
The work is done in teams, with 2 students per team. As part of the proseminar, students have to attend the literature workshop at the computer science library.
The available seminar paper topics and their abstracts are listed at the bottom of this page.
Requirements for Successful Participation
There are three main requirements for successful attendance of the seminar:
- You write a short paper on the topic, providing more detail than the talk.
- You present your topic concisely in a 12-minute talk to the other seminar students and are able to answer questions on the topic.
- You successfully complete the milestones on the way, as outlined in moodle.
You will have multiple meetings with your seminar supervisor, discussing the topic and your progress. One part of the milestones is to be able to explain all of your writing and writing process to your supervisor at any of these meetings.
Paper
The papers will be written in conference style, using a provided LaTeX template. This means that you will write your paper and submit it for “peer review” by the other seminar members. You will receive constructive feedback on how to improve the paper and then be able to submit an updated, final version which is the one that will be graded. Note that this implies that you will have to write some short reviews on the papers submitted by other seminar attendees as well.
Presentation
In contrast to the paper, the talk is not supposed to describe everything in full detail, but should provide an overview on your topic and highlight the important concepts and ideas.
After motivating the broader topic, it should focus on a few ideas fundamental to your paper and explain them in more detail: this gives the audience something substantial to learn, and adds much value to your presentation.
Remember to adjust the content and pace of your presentation to your target audience, which in this case is a group of your student peers.
The talk format will be 12 minutes + 5 minutes for questions, answers and discussions.
Organisation
- All organizational details will be discussed in the mandatory introductory meeting.
- Topics will be assigned during or after the introductory meeting.
- Final presentations will take place in a block seminar.
Please account for the milestone deadlines when planning your semester and/or holidays.
Preliminary Timetable
Throughout the semester, students have to write and present their seminar paper in several milestones as outlined below:
| Milestone | Date |
|---|---|
| Kick-off Meeting | 12th October 2026, 12:30 |
| Paper Outline | 25th October 2026 |
| Discussion Meeting | 28th October 2026, 10:00 |
| Paper Sketch | 15th November 2026 |
| Full Paper Draft | 13th December 2026 |
| Teaser presentations | 16th December 2026 |
| Conference Submission | 10th January 2026 |
| Peer Reviews | 17th January 2027 |
| Camera-ready Paper | 24th January 2027 |
| Final Presentations | 1st–5th February 2027 |
Seminar Topics
Erdős–Rényi and Gilbert random graphs
The Erdős–Rényi and Gilbert models are the prototypical random graph models: each possible edge between a fixed set of nodes exists independently with probability p. Their simplicity has made them equally popular for theoretical studies, for benchmarking algorithms, as well as reference models to measure significance. Possible directions include the emergence of a giant connected component (percolation), other random graph models that better match observed networks, and further theoretical results on their properties.
References
- P. Erdős and A. Rényi. “On random graphs I.” Publicationes Mathematicae Debrecen 6 (1959): 290–297.
- E. N. Gilbert. “Random graphs.” The Annals of Mathematical Statistics 30.4 (1959): 1141–1144.
- B. Bollobás. “Mathematical results on scale-free random graphs.” In Handbook of Graphs and Networks, Wiley-VCH (2002), §§1.2–1.3.
PageRank
Which nodes of a network are the most important? PageRank, introduced by Sergey Brin and Larry Page to rank search results in Google, uses random walks on the graph to answer this question this by scoring. Building on this, the topic can be extended to other centrality measures and their respective strengths and weaknesses. Alternatively, one could also further explore the role of random walks and spectral methods in network science.
References
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems, 30.1–7 (1998): 107–117.
- D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Processing Magazine, 30.3 (2013): 83–98.
Community structure in networks
Many real-world networks contain communities: groups of nodes that are more densely connected among themselves than to the rest of the network. Girvan and Newman proposed one of the first methods to find them, which iteratively removes the “bridging” edges between communities. For the theoretically-oriented, this topic can be broadened to include other community detection approaches such as modularity maximisation. Alternatively, there are also myriad practical applications of community-detection to explore.
References
- M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99.12 (2002): 7821–7826.
- M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103.23 (2006): 8577–8582.
Label propagation for semi-supervised learning
Label propagation assigns labels to the nodes of a network from its structure and a few initially labelled nodes. The known labels spread along the edges to their neighbours, in a process analogous to diffusion, until every unlabelled node has received a label. Thanks in part to its simplicity, this is one of the foundational methods for semi-supervised learning on graphs. Students interested in machine learning applications may especially be interested in relating this approach to message-passing graph neural networks, a training algorithm which uses a conceptual similar mechanism. Alternatively, the relation to diffusion or Gaussian processes can be explored in more detail.
References
- X. Zhu and Z. Ghahramani. “Learning from labeled and unlabeled data with label propagation.” Technical report CMU-CALD-02-107, Carnegie Mellon University (2002).
- Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions, Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, 912–919.