Man-made or naturally-formed networks typically exhibit a high degree of structural regularity. In this paper, we introduce the problem of structured network prediction: given a set of n entities and a desired distribution for connectivity, return a likely set of edges connecting the entities together in a network having the specified degree distribution. Prediction is useful for initializing a network, augmenting an existing network, and for filtering existing networks, when the structure of the network is known. In order to capture the inter-dependencies amongst pairwise predictions to learn parameters of our model, we build upon recent structured output models. Novel in our approach is the use of partially labeled training examples, and a network structure sensitive loss function. We present encouraging results of the model predicting equivalence graphs and links in a social network.