In this study we examined changes in the large-scale structure of resting-state brain networks in patients with Alzheimer's disease compared with non-demented controls, using concepts from graph theory. Magneto-encephalograms (MEG) were recorded in 18 Alzheimer's disease patients and 18 non-demented control subjects in a no-task, eyes-closed condition. For the main frequency bands, synchronization between all pairs of MEG channels was assessed using a phase lag index (PLI, a synchronization measure insensitive to volume conduction). PLI-weighted connectivity networks were calculated, and characterized by a mean clustering coefficient and path length. Alzheimer's disease patients showed a decrease of mean PLI in the lower alpha and beta band. In the lower alpha band, the clustering coefficient and path length were both decreased in Alzheimer's disease patients. Network changes in the lower alpha band were better explained by a 'Targeted Attack' model than by a 'Random Failure' model. Thus, Alzheimer's disease patients display a loss of resting-state functional connectivity in lower alpha and beta bands even when a measure insensitive to volume conduction effects is used. Moreover, the large-scale structure of lower alpha band functional networks in Alzheimer's disease is more random. The modelling results suggest that highly connected neural network 'hubs' may be especially at risk in Alzheimer's disease.