The concept of fitness landscapes originated from evolutionary biology and is relevant for numerous disciplines. In metaheuristics for combinatorial optimization, fitness landscapes are frequently used to study the structure of problems. A novel approach is to analyze fitness landscapes by local optima networks'' (LONs). A LON compresses the features of fitness landscapes in a complex network. The nodes are the local optima. The edges model the potential transitions between the local optima basins. Edges are directed and weighted by transition probabilities. Studies towards a deeper insight and exploitation of LONs are rare. The contribution of this thesis is to demonstrate how local optima networks can be used to study the structure and the search difficulty of combinatorial optimization problems for metaheuristics. For our experiments, we mainly used the Kauffman NK model of fitness landscapes. The thesis consists of four papers. In the first and second paper, we show that the PageRank centrality of the global optimum in LONs is a reliable predictor of search difficulty (R^2 > 90%) for local search based metaheuristics. This is possible because PageRank is a variant of Eigenvector centrality. A LON approximates the stochastic process of an algorithm in the fitness landscape. The LON graph's matrix of edge weights is equivalent to the transition matrix of a finite-state Markov chain. The Eigenvector of the transition matrix reflects the stationary distribution of a random walk across the Markov chain. Hence, the scalar value of the global optimum approximates the probability to visit this node during search.In the third paper, we applied the Markov cluster algorithm for community detection to LONs. This reveals a structure of multiple clusters and supplements the big valley hypothesis, which states that good solutions are often contained in a single, giant cluster. The existence of multiple clusters is related to search difficulty: the size of the cluster containing the global optimum is strongly correlated to the success rate of iterated local search. This offers an explanation for failures of this metaheuristic: the perturbation operator is too weak to escape from one cluster to another. Fourth, a method is introduced to represent a landscape by a coarse-grained barrier tree. Barrier trees (disconnectivity graphs) have so far been used to study the barriers which an algorithm needs to pass in order to escape from one basin to another. We present a method based on the flooding algorithm to reveal the barriers that exist between clusters of local optima. The method is useful to obtain a coarse-grained picture of a fitness landscape. Experimental results indicate that the existence of barriers between clusters is related to search difficulty for iterated local search.