The goal of this paper is to use graph theory network measures derived from non-invasive electroencephalography (EEG) to develop neural decoders that can differentiate Parkinson's disease (PD) patients from healthy controls (HC). EEG signals from 27 patients and 27 demographically matched controls from New Mexico were analyzed by estimating their functional networks. Data recorded from the patients during ON and OFF levodopa sessions were included in the analysis for comparison. We used betweenness centrality of estimated functional networks to classify the HC and PD groups. The classifiers were evaluated using leave-one-out cross-validation. We observed that the PD patients (on and off medication) could be distinguished from healthy controls with 89% accuracy - approximately 4% higher than the state-of-the-art on the same dataset. This work shows that brain network analysis using extracranial resting-state EEG can discover patterns of interactions indicative of PD. This approach can also be extended to other neurological disorders.