There are many theoretical results available for random walks performed on regular lattices such as Z^d. But actually it has been suggested recently that more complex networks are relevant to the real world. Particularly, the small-world model which was proposed by Watts and Strogatz exhibits strong clustering with very small average shortest paths between two nodes. It is believed that these properties are also exhibited by many naturally-occurring complex networks. Such models have been applied to the analysis of various biological, engineering and social networks including information flow on the Internet. In this talk I shall analyse the mixing times of random walks on a general class of random graphs which include these special networks to see how the topological structure of the graphs influences the rate of convergence of ergodic averages.