  Among the several topological properties of complex networks, the shortest
path represents a particularly important characteristic because of its
potential impact not only on other topological properties, but mainly for its
influence on several dynamical processes taking place on the network. In
addition, several practical situations, such as transit in cities, can benefit
by modifying a network so as to reduce the respective shortest paths. In the
present work, we addressed the problem of trying to reduce the average shortest
path of several theoretical and real-world complex networks by adding a given
number of links according to different strategies. More specifically, we
considered: placing new links between nodes with relatively low and high
degrees; to enhance the degree regularity of the network; preferential
attachment according to the degree; linking nodes with relatively low and high
betweenness centrality; and linking nodes with relatively low/low, low/high,
and high/high accessibilities. Several interesting results have been obtained,
including the identification of the accessibility-based strategies as providing
the largest reduction of the average shortest path length. Another interesting
finding is that, for several types of networks, the degree-based methods tend
to provide improvements comparable to those obtained by using the much more
computationally expensive betweenness centrality measurement.
