Defining the structural and functional connectivity of the human brain (the human "connectome") is a basic challenge in neuroscience. Recently, techniques for noninvasively characterizing structural connectivity networks in the adult brain have been developed using diffusion and high-resolution anatomic MRI. The purpose of this study was to establish a framework for assessing structural connectivity in the newborn brain at any stage of development and to show how network properties can be derived in a clinical cohort of six-month old infants sustaining perinatal hypoxic ischemic encephalopathy (HIE). Two different anatomically unconstrained parcellation schemes were proposed and the resulting network metrics were correlated with neurological outcome at 6 months. Elimination and correction of unreliable data, automated parcellation of the cortical surface, and assembling the large-scale baby connectome allowed an unbiased study of the network properties of the newborn brain using graph theoretic analysis. In the application to infants with HIE, a trend to declining brain network integration and segregation was observed with increasing neuromotor deficit scores.