Parkinson's disease (PD) is the most common neurological disorder, after Alzheimer's disease, and is characterized by a long prodromal stage lasting up to 20 years. As age is a prominent factor risk for the disease, next years will see a continuous increment of PD patients, making urgent the development of efficient strategies for early diagnosis and treatments. We propose here a novel approach based on complex networks for accurate early diagnoses using magnetic resonance imaging (MRI) data; our approach also allows us to investigate which are the brain regions mostly affected by the disease. First of all, we define a network model of brain regions and associate to each region proper connectivity measures. Thus, each brain is represented through a feature vector encoding the local relationships brain regions interweave. Then, Random Forests are used for feature selection and learning a compact representation. Finally, we use a Support Vector Machine to combine complex network features with clinical scores typical of PD prodromal phase and provide a diagnostic index. We evaluated the classification performance on the Parkinson's Progression Markers Initiative (PPMI) database, including a mixed cohort of 169 normal controls (NC) and 374 PD patients. Our model compares favorably with existing state-of-the-art MRI approaches. Besides, as a difference with previous approaches, our methodology ranks the brain regions according to disease effects without any a priori assumption.