The recent application of graph theory to brain networks promises to shed light on complex diseases such as Parkinson’s disease. This study aimed to investigate functional changes in sensorimotor and cognitive networks in parkinsonian patients, with a focus on inter- and intra-connectivity organization in the disease-associated nodal and hub regions using the graph theoretical analyses. Resting-state functional MRI data of a total of 65 participants, including 23 healthy controls and 42 patients, were investigated in 120 nodes for local efficiency, betweenness centrality, and degree. Hub regions were identified in the healthy control and patient groups. We found nodal and hub changes in patients compared with healthy controls, including the right pre-supplementary motor area, left anterior insula, bilateral mid-insula, bilateral dorsolateral prefrontal cortex, and right caudate nucleus. In general, nodal regions within the sensorimotor network (i.e. right pre-supplementary motor area and right mid-insula) displayed weakened connectivity, with the former node associated with more severe bradykinesia, and impaired integration with default mode network regions. The left mid-insula also lost its hub properties in patients. Within the executive networks, the left anterior insular cortex lost its hub properties in patients, while a new hub region was identified in the right caudate nucleus, paralleled by an increased level of inter- and intra-connectivity in the bilateral dorsolateral prefrontal cortex possibly representing compensatory mechanisms. These findings highlight the diffuse changes in nodal organization and regional hub disruption accounting for the distributed abnormalities across brain networks and the clinical manifestations of Parkinson’s disease.