Distance Distribution and Reliability of Small-World Networks

We have studied the distribution of distances in small-world network by computer simulations. We found that in a small world network, the longest distance between two vertices is just slightly longer than the average distance, indicating that the efficiency of the network is absolute rather than in average. We also investigated the robustness of a small-world network by randomly cutting some long paths in the network. The results show that the network is reliable against random cutting.