Small changes to the structure of graphs imply a huge impact on their connectivity. While in a purely theoretical approach, a topological change affects just formal properties, graph data structures associated with well-defined semantics (for example, a social graph) can significantly alter the reality they are representing (such as social processes in a social graph).

In this paper, the characteristic path length (average distance between pairs of vertices) is minimized by applying a graph augmentation technique: a small set of nonexisting edges is added to the original structure in order to define shortcuts. Even though contextual properties (for example, influence of people, relevance of content) play an important role in the propagation of the information in practice, shorter paths are a guarantee of improved performance.

This work is definitely a solid contribution, including a clear introduction to the problem, an appreciated section on motivating applications, and a validation/evaluation of the model with synthetic data. As a very minor remark, I would have liked a deeper discussion on the effects of augmentation techniques in social graphs, also including negative ones.