Although alterations in resting-state functional connectivity between brain regions have previously been reported in Parkinson's disease, the spatial organization of these changes remains largely unknown. Here, we longitudinally studied brain network topology in Parkinson's disease in relation to clinical measures of disease progression, using magnetoencephalography and concepts from graph theory. We characterized whole-brain functional networks by means of a standard graph analysis approach, measuring clustering coefficient and shortest path length, as well as the construction of a minimum spanning tree, a novel approach that allows a unique and unbiased characterization of brain networks. We observed that brain networks in early stage untreated patients displayed lower local clustering with preserved path length in the delta frequency band in comparison to controls. Longitudinal analysis over a 4-year period in a larger group of patients showed a progressive decrease in local clustering in multiple frequency bands together with a decrease in path length in the alpha2 frequency band. In addition, minimum spanning tree analysis revealed a decentralized and less integrated network configuration in early stage, untreated Parkinson's disease that also progressed over time. Moreover, the longitudinal changes in network topology identified with both techniques were associated with deteriorating motor function and cognitive performance. Our results indicate that impaired local efficiency and network decentralization are very early features of Parkinson's disease that continue to progress over time, together with reductions in global efficiency. As these network changes appear to reflect clinically relevant phenomena, they hold promise as markers of disease progression. © 2013 The Author.