Abstract
In this discussion we present assessments and valuable insights on random graph generating models. Of particular interest, we focus on the exponential random graph models (ERGMs) with sufficient statistics that consists of the number of edges and the number of triangles for each given undirected graph of 8 nodes. These models have so far been mainly applied in studying the statistical properties of social networks. Issues that arise when working with ERGMs have been shown to relate to the geometry of discrete polyhedral convex sets. These issues include model degeneracy, inferential complexity and model misfit. Using the results from applied geometry the parameter space can be shown to have a very complex structure that hinders many optimization algorithms from obtaining local or global solutions to MLE estimates. We propose a whitening transform onto the graph feature space to reduce the correlation of observed features because MLE estimates are linear combinations of the observed features as such any dependency in the observed features will contribute to degeneracy of the estimated model. We show that the geometry of the transformed space has a much smoother surface for the objective function as compared to the original space. Gobal solution searching and convergence of the gradient based optimization algorithm is observed to be very fast in the transfored space. We carry out assessments for model fitting by constructing a likelihood surface in the transform space: this is done by searching for the transformed mean features that match the mode of their distribution. since the transformation does not change the form of the distribution we show that the entropy objective function can characterize both the canonical and mean value parameter spaces of the transformed feature space. From the new feature space, we also highlight a region in which even reasonable models with true parameter values will result in unrealistic observations. We note that although the transformation introduces smoothness in the natural parameter space, there is still a region of feature statistics whose pmfs have modes placed on other regions of the feature space.
Keywords
Graph Isomorphism, Canonical graphs, Equivalence Classes, Similarity Diameter, Exponential Random Graphs, Maximum Entropy, Degeneracy, Maximum Likelihood Surface
Date of this Version
10-14-2010