Structural network analysis is an intricate problem. In fact, the majority of techniques that have been developed so far are only applicable to investigate deterministic network models. This gives rise to develop novel graph-theoretical methods for applying them to more complex graphs and especially to statistically inferred networks. In this regard, we review methods for analyzing complex networks structurally putting the special emphasis on network partitioning and quantifying network complexity. Both areas are of general importance in structural graph theory as well as useful for exploring biological networks.