Mitochondrial dysfunction is linked to pathogenesis of Parkinson's disease (PD). However, individual mitochondria-based analyses do not show a uniform feature in PD patients. Since mitochondria interact with each other, we hypothesize that PD-related features might exist in topological patterns of mitochondria interaction networks (MINs). Here we show that MINs formed nonclassical scale-free supernetworks in colonic ganglia both from healthy controls and PD patients; however, altered network topological patterns were observed in PD patients. These patterns were highly correlated with PD clinical scores and a machine-learning approach based on the MIN features alone accurately distinguished between patients and controls with an area-under-curve value of 0.989. The MINs of midbrain dopaminergic neurons (mDANs) derived from several genetic PD patients also displayed specific changes. CRISPR/CAS9-based genome correction of alpha-synuclein point mutations reversed the changes in MINs of mDANs. Our organelle-interaction network analysis opens another critical dimension for a deeper characterization of various complex diseases with mitochondrial dysregulation.