An efficient heuristics to realize near-optimal small-world networks

Small-world characteristic brings down average path length of a network by adding a few long-links among network node-pairs. In a real-world deployment scenario, probabilistic long-link addition cannot guarantee optimal value of average path length for a network with limited number of long-links. In this paper, we propose a generalized heuristic, Sequential Deterministic Long-link Addition (SDLA) algorithm to incorporate small-world property for moderate sized string topology networks. Our proposed algorithm has O(k × N) time complexity compared to O(N^2(k+2) × log N) for optimal and O(k × N⁴ × log N) for near-optimal long-link addition strategies for k long links when a string topology network of size N is concerned. Our studies show that SDLA algorithm negligibly deviates in various network properties (e.g., average path length, average clustering coefficient, and graph centralities) from the optimal and near-optimal solutions.