Selecting Shortcuts for a Smaller World

The small world phenomenon is a desirable property of social networks, since it guarantees short paths between the nodes of the social graph and thus efficient informa-tion spread on the network. It is thus in the benefit of both network users and network owners to enforce and maintain this property. In this work, we study the prob-lem of finding a subset of k edges from a set of candidate edges whose addition to a network leads to the great-est reduction in its average shortest path length. We formulate the problem as a combinatorial optimization problem, and show that it is NP-hard and that known approximation techniques are not applicable. We de-scribe an efficient method for computing the exact effect of a single edge insertion on the average shortest path length, as well as several heuristics for efficiently esti-mating this effect. We perform experiments on real data to study the performance of our algorithms in practice.