Likelihood-based inference for exponential-family random graph models via linear programming

The problem of determining whether a given point, or set of points, lies within the convex hull of another set of points in d dimensions arises naturally in the context of certain exponential family models in statistics. This article discusses the general convex hull problem and its application to the particular problem of modelling network data using an exponential-family random graph model (ERGM). While the convex hull question may be solved via a simple linear program, this approach is not well known in the statistical literature. The article also details several sub-stantial improvements to the convex hull-testing algorithm currently imple-mented in the widely used ergm package for network modeling. It provides direct numerical comparisons of two linear programming packages for R that can be called by ergm and offers several illustrative examples.