11th Networks - day
On Wednesday September 25th, the 11th NETWORKS-day is organized by Onno Boxma and Jop Briët.
09.30-10.00 Welcome and coffee
10.00-10.30 Introduction by Michel Mandjes
10.30-11.15 Presentation by Ines Lindner (VU): "Innovation and Inequality in a Small World"
11.15-11.45 Coffee break
11.45-12.30 Presentation by Bert Zwart (CWI & TU/e): "Why are blackouts in power grids
12.30-13.30 Lunch / room to discuss
13.30-14.15 Presentation by Julia Komjathy (TU/e)
14.15-14.45 Introductory talk by Mark Jones (postdoc CWI): "Reconstructing Phylogenetic
14.45-15.00 Introduction new PhD students: Maurizio Moreschi (UvA) and Nikki Levering (UvA)
15.00-15.30 Coffee break
15.30-16.00 Introductory talk by Martín Zubeldía (postdoc TU/e & UvA): "A lower bound on the
queueing delay in resource constrained load balancing"
16.00-16.45 Presentation by Monique Laurent (CWI & UvT): "Ordering data with combinatorial
Title: Innovation and Inequality in a Small World
We present a multi-country theory of economic growth and R&D driven technological progress in which countries are connected by a network of knowledge exchange. Technological progress in any country depends on the state of technology in the countries it exchanges knowledge with. The diusion of knowledge throughout the world explains a period of increasing world inequality after the take-o of the forerunners of the industrial revolution, followed by decreasing relative inequality. Knowledge diusion through a Small World network produces an extraordinary diversity of country growth performances, including the overtaking of individual countries and the replacement of the technologically leading country in the course of world development.
Title: Why are blackouts in power grids heavy-tailed?
Blackouts in power grids are among the most disruptive events in our society. They can occur through a variety of ways. The intricate interaction of various physical (weather, electricity) and man-made (economics, human errors) features make the propagation of cascading failures hard to predict on a microscopic level.
Nevertheless, there is a macroscopic feature of blackouts that is easy to describe: US data suggests that blackout sizes follow a Pareto distribution. The origin of this law is attributed to self-organized criticality in the engineering and physics literature. We provide arguments in support of an alternative hypothesis, armed with data, a theorem, and a case study.
Joint work with Tommaso Nesti (CWI) and Fiona Sloothaak (TU/e).
Title: Reconstructing Phylogenetic Networks
Phylogenetic networks represent the evolutionary history of a set of species or individuals. An important question in phylogenetics is how to determine the structure of a phylogenetic network, given only information about present-day species. In particular, it may be possible to use the DNA sequence data of existing species to derive the likely structure of a network, under certain models of DNA evolution.
In this talk, I will discuss a number of approaches to this question, and related algorithmic problems.
Title: A lower bound on the queueing delay in resource constrained load balancing
Consider the following distributed service model: jobs with unit mean, general distribution, and independent processing times arrive as a renewal process of rate L.N, with 0<L<1, and are immediately dispatched to one of several FIFO queues associated with N identical servers with unit processing rate. The dispatching decisions are assumed to be made by a central controller endowed with a finite memory, and with the ability to exchange messages with the servers in order to obtain the state of their queues. In this setting, I will show that, within a certain broad class of "symmetric" policies, every dispatching policy with an average message rate of the order of N, and with a memory of the order of log(N) bits, results in an average queueing delay which is bounded away from zero, uniformly in N.
Joint work with David Gamarnik and John Tsitsiklis.
Title: Ordering data with combinatorial graph algorithms
Finding a ranking of a set of objects based on information on their pairwise similarities is a fundamental problem in data analysis. A widely used approach is seriation, which aims to order the objects in such a way that similar objects are placed close to each other. Seriation roots in early works by the archeologists Flinders Petrie (1899) and Robinson (1951), who used it for chronological sequencing of Egyptian tombs based on historical remains (like potteries) found in them. Recent applications of seriation include genome sequencing and ranking in recommender systems.
In our lecture we discuss, next to a classical spectral approach, new combinatorial algorithms for this problem of reordering similarity data matrices. We highlight links to some graph properties that can be exploited to design efficient ranking algorithms. In a nutshell, these algorithms rely on a natural extension to the setting of matrices (weighted graphs) of basic graph search primitives like breadth-first search.