Connectivity in a gene-gene network declines with age, typically within gene clusters. We explored the effect of short-term (3 months) graded calorie restriction (CR) (up to 40 %) on network structure of aging-associated genes in the murine hypothalamus by using conditional mutual information. The networks showed a topological rearrangement when exposed to graded CR with a higher relative within cluster connectivity at 40CR. We observed changes in gene centrality concordant with changes in CR level, with Ppargc1a, and Ppt1 having increased centrality and Etfdh, Traf3 and Abcc1 decreased centrality as CR increased. This change in gene centrality in a graded manner with CR, occurred in the absence of parallel changes in gene expression levels. This study emphasizes the importance of augmenting traditional differential gene expression analyses to better understand structural changes in the transcriptome. Overall our results suggested that CR induced changes in centrality of biological relevant genes that play an important role in preventing the age-associated loss of network integrity irrespective of their gene expression levels.