Community detection, as well as the identification of other structures like core periphery and disassortative patterns, is an important topic in network analysis. While most methods seek to find the best partition of the network according to some criteria, there is a body of results that suggest that a single network can have many good but distinct partitions. In this paper we introduce the density of states as a tool for studying the space of all possible network partitions. We demonstrate how to use the well known Wang-Landau method to compute a network's density of states. We show that, even using modularity to measure quality, the density of states can still rule out spurious structure in random networks and overcome resolution limits. We demonstrate how these methods can be used to find `building blocks', groups of nodes which are consistently found together in detected communities. This suggests an approach to partitioning based on exploration of the network's structure landscape rather than optimisation.