Description

Leader of the group Life Sciences and Health: Leen Stougie.

Our research group creates fundamental knowledge and applied solutions in the broad field of life sciences. We promote understanding of how biological processes work in detail. Our interdisciplinary team of computer scientists, mathematicians and theoretical biologists develops new models, theories, and decision support systems in collaboration with experimental biologists and medical experts. We are motivated by applications of our work in practice

 

Watch our group video to get a glimpse of our activities or click here for more information about our group structure.

 

News

Current events

Inaugural speech Peter Bosman

  • 2019-09-06T15:00:00+02:00
  • 2019-09-06T15:45:00+02:00
September 6 Friday

Start: 2019-09-06 15:00:00+02:00 End: 2019-09-06 15:45:00+02:00

Aula Conference Centre - TU Delft

Following my appointment as part-time professor of Evolutionary Algorithms at the department of Software Technology of the faculty of Electrical Engineering, Mathematics and Computer Science of Delft University of Technology, I will give my inaugural speech on Friday, September 6, 2019 at 15:00 hours in the Aula of the Delft University of Technology.

Prior to my inaugural speech a symposium will be held, featuring the work of world-leading researchers who are active at the frontiers of the design, development, analysis, and application of evolutionary algorithms.

You are cordially invited to attend both events. However, if you plan to attend the symposium, please register HERE due to limited seating at the symposium (120 seats). No registration is required for the inaugural speech (there are sufficient seats in the Aula).

More information on the program of the day and travel information can be found HERE.

I hope to see you there!

Peter

Networks Workshop on Random graphs, counting and sampling

  • 2019-09-11T13:30:00+02:00
  • 2019-09-11T17:00:00+02:00
September 11 Wednesday

Start: 2019-09-11 13:30:00+02:00 End: 2019-09-11 17:00:00+02:00

CWI, room L120

Organisers: Viresh Patel and Leen Stougie

Location: CWI, Science Park 123, 1098 XG Amsterdam, lecture room L120. 

Registration is free of charge, expressing your intention to attend is highly appreciated by using the electronic registration form here.


Topic
A main theme of the workshop concerns efficient approximation algorithms for counting different types of combinatorial objects. By considering the appropriate generating functions, the problem naturally extends to that of approximately evaluating corresponding partition functions and this in turn has close connections to phase transitions in statistical physics. One approach to the sampling (and hence also to the counting) problem is through suitably defining Markov chains on the space of all the objects to be sampled and then to show that this chain mixes rapidly. This brings together ideas from combinatorics, probability, algorithms, and statistical physics. A second closely related theme is  that of random graphs and their typical properties, another very active area of research in probability and discrete mathematics.
 
Speakers
Martin Dyer (University of Leeds, UK)
Catherine Greenhill (University of New South Wales, Sydney)
Pieter Kleer (CWI, Amsterdam)
Matteo Sfragara (University of Leiden)
 
Program
13:30  Matteo Sfragara
14:15  Martin Dyer
15:00  Coffee / tea
15:30  Catherine Greenhill
16:15  Pieter Kleer
17:00  Drinks

Titles and abstracts

Martin Dyer
Title: Counting independent sets in (fork,odd hole)-free graphs
Abstract: Jerrum, Sinclair and Vigoda showed that the permanent of any square matrix can be estimated in polynomial time. This can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are known to be precisely the class of (claw,diamond,odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to all (claw,odd hole)-free graphs, and then show that it extends to the even larger class of (fork,odd hole)-free graphs.
(Joint work with Mark Jerrum, Haiko Müller and Kristina Vušković.)

Catherine Greenhill
Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth
Abstract: In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting matchings in a given graph G is rapidly mixing. This chain can equivalently be viewed as counting independent sets in line graphs. We generalise their approach to the class of all graphs with the  following property: every bipartite induced subgraph of G has pathwidth at most p. Here p is a positive integer and the mixing time of the Markov chain will depend on p. We also describe two classes of graphs (described in terms of forbidden induced subgraphs) that satisfy this condition. Both of these classes generalise the class of claw-free graphs.
 
Pieter Kleer
Title: The switch Markov chain for generating regular graphs with a partition constraint
Abstract: The switch Markov chain is a simple procedure to randomize network topologies while preserving the degree sequence of the network. It proceeds by uniformly at random selecting two edges, and switching them if this is possible. For d-regular graphs, it is known that a polynomial number of switch suffices to get an almost uniform sample from the set of all d-regular graphs. In this work we consider an extension of the problem where, given some partition of the nodes into two parts, it is also specified how much edges there should be between the two parts of the partition, i.e., we are interested in d-regular graphs with a partition constraint. This is a special case of the joint degree matrix problem. In this talk, we show that a polynomial number of switches suffices to get d-regular graph, satisfying the partition constraint, which is close to being a uniform sample from the set of all graphs with the given partition constraint.

Matteo Sfragara
Title: Spectrum of Adjacency and Laplacian Matrices of Inhomogeneous Erdős-Rényi Random Graphs
Abstract: In homogeneous Erdős-Rényi random graphs G_N on N vertices in the non-dense regime are considered in this talk. The edge between the pair of vertices {i, j} is retained with probability ε_N f(i/N , j/N), 1≤i=jN, independently of other edges, where f: [0,1]x[0,1] → [0,∞) is a continuous function such that f(x,y) = f(y,x) for all x, y ∈ [0,1]. We study the empirical distribution of the adjacency matrix A_N associated with G_N in the limit as N → ∞ when lim_(N→∞) ε_N= 0 and lim_(N→∞) Nε_N=∞. In particular, it is shown that the empirical spectral distribution of A_N, after appropriate scaling and centering, converge to deterministic limits weakly in probability. For the special case where f(x, y) = r(x)r(y) with r: [0,1]→[0,∞) a continuous function, we give an explicit characterization of the limiting distribution. Furthermore, applications of the results to Chung-Lu random graphs and social networks are shown.

 

Support: We gratefully acknowledge funding from Networks
 
 

Members

Associated Members

Publications

Software

Current projects with external funding

  • 3D dose reconstruction for children with long-term follow-up Toward improved decision making in radiation treatment for children with cancer
  • Enhancing protein-drug binding prediction
  • ICT based Innovations in the Battle against Cancer – Next - Generation Patient -Tailored Brachytherapy Cancer Treatment Planning
  • Statistical Models for Structural Genetic Variants in the Genome of the Netherlands
  • Fusible Evolutionary Deep Neural Network Mixture Learning from Distributed Data for Robust Medical Image Analysis (FEDMix)
  • Multi-Objective Deformable Image Registration (MODIR) – An Innovative Synergy of Multi-Objective Optimization, Machine Learning, and Biomechanical Modeling for the Registration of Medical Images with (MODIR)
  • Networks

Related partners

  • AMC Medical Research
  • Elekta Limited
  • Nucletron Operations BV
  • Xomnia
  • Academisch Medisch Centrum
  • Biomedical Imaging Group Rotterdam
  • Erasmus Universiteit Rotterdam
  • KiKa
  • Universiteit Leiden