Efficient Algorithms for Complex Networks
There are currently serious efforts devoted to algorithms taking into account usual properties of complex networks, either in their design (use these properties to be efficient) or in their analysis (show that, if the input graph has these properties, then the algorithm has low complexity).
Since most complex networks met in practice are sparse, let me first say that any complexity expressed in terms of the number of edges (instead of the squared number of vertices) is of interest in this context. But I do understand that you actually have more advanced complex network properties and complexity analysis in mind.
My 2006 paper about triangle counting and listing provides a good illustration, I think. There, I used the fact that most complex networks met in practice have very heterogeneous degrees. I proposed a very simple algorithm makes a distinction between low- and high-degree vertices, and proved its algorithmic complexity as a function of the graph degree distribution.
Many such examples exist in the literature. For instance, the arboricity and core value have been used to enumerate $k$-cliques. However I am not aware on any survey devoted to them.