Networks are ubiquitous – from social and information systems to biological and technological systems. With pervasive use of the Internet and various advances in technology, networks under study today are not only substantially larger than those in the past, but sometimes exist in a decentralized form. These factors can make analysis of and access to these networks, in their entirety, prohibitive. One approach to addressing these issues is sampling: inference using small subsets of nodes and links from a network. Unlike traditional sampling approaches which focus on inferences related to attributes of nodes, this thesis focuses on the use of sampling to infer non-trivial properties of the network itself – both structural and functional. We introduce a sampling technique, based on concepts from expander graphs, to infer aspects of community structure in the larger network. We draw and demonstrate connections between the expansion properties of samples and the extent to which networks can be efficiently searched. We conduct a study on how best to identify influential individuals while only accessing small portions of a social network. We show that certain sampling biases are, in fact, beneficial for many applications, as they "push" the sampling process towards inclusion of desired properties. Lastly, using a slightly different notion of sampling, we present a maximum likelihood-based approach to inferring social hierarchy.