  We present a method based on simulated annealing to obtain a nested split
graph that approximates a real complex graph. This is used to compute a number
of graph indices using very efficient algorithms that we develop, leveraging
the geometrical properties of nested split graphs. Practical results are given
for six graphs from such diverse areas as social networks, communication
networks, word associations, and molecular chemistry. We present a critical
analysis of the appropriate perturbation schemes that search the whole space of
nested split graphs and the distance functions that gauge the dissimilarity
between two graphs.
