Optimal Networks

Abstract

Variational approaches have been largely disregarded in complex network studies although they frequently provide an alternative and possibly more meaningful point of view. This important class of network models is obtained by looking for graphs that optimize a given quantity, functional of the graph. The simplest case is, for example, the minimum spanning tree (MST) that minimizes the total length for a given set of points. Most existing spatial networks in the real-world do not seem to result from a global optimization, but rather from the progressive addition of nodes and segments resulting from a local optimization (see next chapters). By modeling (spatial) networks as resulting from a global optimization, one overlooks the usually limited time horizon of planners and the self-organization underlying their formation. The interest of these optimal networks lies then rather in the fact that they constitute interesting benchmark to compare actual networks with. The comparison with the MST, for example, indicates how far we are from the minimum cost possible, and is, therefore, a very important example and was largely studied. In particular, there is an extensive mathematical literature on this graph and we will try to discuss here the most important results on this case. We will also discuss other optimal trees that generalize the MST to the case where a more complex quantity than the total length is minimized.