Bayesian experimental design for percolation and other random graph models
Seminar Room 1, Newton Institute
The problem of optimal arrangement of nodes of a random graph will be discussed in this workshop. The nodes of graphs under study are fixed, but their edges are random and established according to the so called edge-probability function. This function may depend on the weights attributed to the pairs of graph nodes (or distances between them) and a statistical parameter. It is the purpose of experimentation to make inference on the statistical parameter and, thus, to learn about it as much as possible. We also distinguish between two different experimentation scenarios: progressive and instructive designs. We adopt a utility-based Bayesian framework to tackle this problem. We prove that the infinitely growing or diminishing node configurations asymptotically represent the worst node arrangements. We also obtain the exact solution to the optimal design problem for proximity (geometric) graphs and numerical solution for graphs with threshold edge-probability functions. We use simulation based optimisation methods, mainly Monte Carlo and Markov Chain Monte Carlo, in order to obtain solution in the general case. We study the optimal design problem for inference based on partial observations of random graphs by employing data augmentation technique. In particular, we consider inference and optimal design problems for finite open clusters from bond percolation on the integer lattices and derive a range of both numerical and analytical results for these graphs. (Our motivation here is that open clusters in bond percolation may be seen as final outbreaks of an SIR epidemic with constant infectious times.) We introduce inner-outer design plots by considering a bounded region of the lattice and deleting some of the lattice nodes within this region and show that the 'mostly populated' designs are not necessarily optimal in the case of incomplete observations under both progressive and instructive design scenarios. Some of the obtained results may generalise to other lattices.