Generating Conditional Realizations of Graphs and Fields Using Markov Chain Monte Carlo

Markov chain Monte Carlo (MCMC) have long been used to generate conditional realizations of graphs and fields. In this talk, I will address a couple of problems, of practical relevance, being pursued in Sandia.

In the first half of my talk, I will address the problem of generating independent graphical/network realizations conditional on a prescribed joint degree distribution. This is of relevance when one has to generated “sanitized” proxies of real networks which cannot be distributed, for experimentation and modeling, due to security or privacy concerns. Correlated realizations can be generated by driving an edge-swapping scheme with an MCMC method. We devise a model that indicates that thinning the Markov chain by $kE$, where $E$ = the number of edges in the graph and $k \sim 10-30$ can generate graphs that are, for practical purposes, independent. Tests with real graphs are used to verify the model.

In the second half, I will address the generation of permeability fields, conditional on sparse measurements of permeability and fluid flow dynamics. We are provided with a porous binary medium, with a low permeability matrix with spatially distributed, fine, high permeability inclusions. We aim to estimate the spatial distribution and inclusion size with a grid that is too coarse to resolve the inclusions. We link the resolved and unresolved scales using a subgrid model based on truncated Gaussian models. The spatial distribution and size of inclusions are estimated using MCMC. Posterior predictive tests are used to check the inferred field.

Speaker Bio: Jaideep Ray is a Principal Member of the Technical Staff at Sandia National Laboratories, CA. He received his PhD in Mechanical and Aerospace Engineering in 1999, from Rutgers, The State University of New Jersey. He has been involved in developing methods for Bayesian inverse problems, high-order numerical schemes for reactive flow simulations on block-structured adaptively refined meshes, and component-based software architectures for scientific computing. His publications and current research interests can be found at http://csmr.ca.sandia.gov/~jairay .

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3668; at least 24 hours in advance.