Diffusion tensor imaging, tractography and the subsequent derivation of network measures are becoming an established approach in the exploration of brain connectivity. However, no gold standard exists in respect to how the brain should be parcellated and therefore a variety of atlas- and random-based parcellation methods are used. The resulting challenge of comparing graphs with differing numbers of nodes and uncertain node correspondences necessitates the use of normalisation schemes to enable meaningful intra- and inter-subject comparisons. This work proposes methods for normalising brain network measures using random graphs. We show that the normalised measures are locally stable over distinct random parcellations of the same subject and, applying it to a neonatal serial diffusion MRI data set, we demonstrate their potential in characterising changes in brain connectivity during early development.