  We consider 15 properties of labeled random graphs that are of interest in
the graph-theoretical and the graph mining literature, such as clustering
coefficients, centrality measures, spectral radius, degree assortativity,
treedepth, treewidth, etc. We analyze relationships and correlations between
these properties. Whereas for graphs on a small number of vertices we can
exactly compute the average values and range for each property of interest,
this becomes infeasible for larger graphs. We show that graphs generated by the
\ErdosRenyi graph generator with $p = 1/2$ model well the underlying space of
all labeled graphs with a fixed number of vertices. The later observation
allows us to analyze properties and correlations between these properties for
larger graphs. We then use linear and non-linear models to predict a given
property based on the others and for each property, we find the most predictive
subset. We experimentally show that pairs and triples of properties have high
predictive power, making it possible to estimate computationally expensive to
compute properties with ones for which there are efficient algorithms.
