The Local Optima Networks represent combinatorial landscapes as graphs, where nodes are local optima and edges are transitions between optima. It brings a new set of metrics to characterize them. Here we investigate the behavior of random walks on such oriented and weighted networks using NK landscapes and QAP instances as examples. We show that random walks are useful to characterize the structure of the corresponding LONs and give interesting information about the relationships between search difficulty and LON structure.