Functional impairment of spatially distributed brain regions in Parkinson's disease (PD) suggests changes in integrative and segregative network characteristics, for which novel analysis methods are available. To assess underlying structural network differences between PD patients and controls, we employed MRI T1 gray matter segmentation and diffusion MRI tractography to construct connectivity matrices to compare patients and controls with data originating from two different centers. In the Dutch dataset (Data-NL), 14 PD patients, and 15 healthy controls were analyzed, while 19 patients and 18 controls were included in the Canadian dataset (Data-CA). All subjects underwent T1 and diffusion-weighted MRI. Patients were assessed with Part 3 of the Unified Parkinson's Disease Rating Scale (UPDRS). T1 images were segmented using FreeSurfer, while tractography was performed using ExploreDTI. The regions of interest from the FreeSurfer segmentation were combined with the white matter streamline sets resulting from the tractography, to construct connectivity matrices. From these matrices, both global and local efficiencies were calculated, which were compared between the PD and control groups and related to the UPDRS motor scores. The connectivity matrices showed consistent patterns among the four groups, without significant differences between PD patients and control subjects, either in Data-NL or in Data-CA. In Data-NL, however, global and local efficiencies correlated negatively with UPDRS scores at both the whole-brain and the nodal levels [false discovery rate (FDR) 0.05]. At the nodal level, particularly, the posterior parietal cortex showed a negative correlation between UPDRS and local efficiency, while global efficiency correlated negatively with the UPDRS in the sensorimotor cortex. The spatial patterns of negative correlations between UPDRS and parameters for network efficiency seen in Data-NL suggest subtle structural differences in PD that were below sensitivity thresholds in Data-CA. These correlations are in line with previously described functional differences. The methodological approaches to detect such differences are discussed.