This paper presented a novel complex network with one-way ANOVA F-test feature selection to diagnose early-stage Parkinson’s disease (PD) on quantitative susceptibility mapping (QSM). Experimental results on QSM images of 30 early-stage PD patients and 27 healthy controls (HC) proved that the F-test feature selection scheme was effective and achieved good classification results. The accuracy, AUC, sensitivity and specificity of our method were 0.96, 0.97, 0.99 and 0.95, respectively, which were improved by 15%, 4%, 29% and 2%, respectively by comparison with the commonly used region of interest (ROI) based method. Meanwhile, according to the feature importance, the potential brain regions affected by PD were arranged orderly. The affected regions were distributed as follows: 61% of them are located in right hemisphere and 39% in the left hemisphere. Particularly, frontal lobe, parietal lobe, temporal lobe and occipital lobe accounted for 24%, 20%, 5% and 14%, respectively, and striatum and the dorsal thalamus accounted for 16%. It concludes that the complex network with one-way ANOVA F-test feature selection can greatly improve the diagnostic performance of early-stage PD based on QSM, as well as provide a new way to study the effect of PD on brain in the future.