Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition

作者：Gozzard, Andrew; Ward, Max; Datta, Amitava^*

来源：Information Sciences, 2018, 422: 282-289.

DOI：10.1016/j.ins.2017.09.020

The average path length in a network is an important parameter for measuring the end to-end delay for message delivery. The delay between an arbitrary pair of nodes is smaller if the average path length is low. It is possible to reduce the average path length of a network by adding one or more additional links between pairs of nodes. However, a naive algorithm is often very expensive for determining which additional link can reduce the average path length in a network the most. In this paper, we present two efficient algorithms to minimize the average network path length by link addition. Our algorithms can process significantly larger networks compared to the naive algorithm. We present simple implementations of our algorithms, as well as performance studies.

• 出版日期2018-1