A disturbance in the interactions between distributed cortical regions may underlie the cognitive and perceptual dysfunction associated with schizophrenia. In this article, nonlinear measures of cortical interactions and graph-theoretical metrics of network topography are combined to investigate this schizophrenia "disconnection hypothesis." This is achieved by analyzing the spatiotemporal structure of resting state scalp EEG data previously acquired from 40 young subjects with a recent first episode of schizophrenia and 40 healthy matched controls. In each subject, a method of mapping the topography of nonlinear interactions between cortical regions was applied to a widely distributed array of these data. The resulting nonlinear correlation matrices were converted to weighted graphs. The path length (a measure of large-scale network integration), clustering coefficient (a measure of "cliquishness"), and hub structure of these graphs were used as metrics of the underlying brain network activity. The graphs of both groups exhibited high levels of local clustering combined with comparatively short path lengths--features consistent with a "small-world" topology--as well as the presence of strong, central hubs. The graphs in the schizophrenia group displayed lower clustering and shorter path lengths in comparison to the healthy group. Whilst still "small-world," these effects are consistent with a subtle randomization in the underlying network architecture--likely associated with a greater number of links connecting disparate clusters. This randomization may underlie the cognitive disturbances characteristic of schizophrenia.