Training Week 1

Computational Geometry and Random Graphs


On 24-28 August NETWORKS organized the first Training Week for PhD Students. The topics of this Training Week are computational geometry and random graphs.


About Training Weeks

One of the exciting aspects of NETWORKS is that it covers stochastic and algorithmic
aspects of networks. This provides a unique opportunity to educate young researchers in both
areas. To reach that goal, NETWORKS organizes Training Weeks. Each training week will combine two topics, one from stochastics and one from algorithmics. The training weeks will be held off-campus, so that they also serve as community-building activities.


Target group

All NETWORKS PhD students are expected to participate in these Training Weeks, but other researchers from NETWORKS are very welcome as well. 


Training Week 1: Computational geometry and Random graphs

Computational geometry is the field within algorithms research dealing with the design and analysis of algorithms and data structures for spatial data, combining clever algorithmic techniques with beautiful geometric concepts. Computational geometry can be seen as the fundamental study of algorithmic problems arising in various application areas that deal involve spatial data. In this training week, after briefly reviewing a few standard concepts about algorithms and data structures in general, we will discuss some of the basic techniques from computational geometry. We will also give examples of the use of probabilistic arguments in the analysis of geometric algorithms, and we will discuss one or two modern research topics.

Random graphs are models for complex networks where the connections are formed through some random process. In this course, we present the basics of random graph theory, as well as give a glimpse of current research that is being performed, within and outside the Networks program. In more detail, we discuss preliminaries needed to investigate random graphs, such as the first and second moment methods, branching processes and coupling. After this, we investigate the classical Erdoes-Renyi random graph and its adaptations that incorporate vertex inhomogeneities, such as the generalized random graph, the configuration model, and preferential attachment models. We focus on the degree structure, on connectivity properties and on distances within these graphs. Current research topics include the critical behavior of such graphs and various processes on them, such as information diffusion and competition processes.



Hofstad van der, Remco_websiteBerg de, MarkThe main lecturers during this Training Week were Remco van der Hofstad and Mark de Berg.