Local and global effects on navigation in small-world networks and explosive percolation

Abstract

A significant number of real networks have well-defined local and nonlocal features. We investigate the influence of these features in the navigation through small-world networks and in explosive percolation. First, we investigate the navigation problem in lattices with long-range connections and subject to a cost constraint. Our network is built from a regular d-dimensional lattice to be improved by adding long-range connections (shortcuts) with probability $P_{ij} sim r_{ij}^{-alpha}, where $r_{ij}$ is the Manhattan distance between nodes $i$ and $j$, and a is $alpha$ variable exponent. We find optimal transport in the system for $alpha = d+1$. Remarkably, this condition remains optimal, regardless of the strategy used for navigation being based on local or global knowledge of the network structure. Second, we present a cluster growth process that provides a clear connection between equilibrium statistical mechanics and the nonlocal explosive percolation process. We show that the following two ingredients are sufficient for obtaining an abrupt transition in the fraction of the system occupied by the largest cluster: (i) the size of all growing clusters should be kept approximately the same, and (ii) the inclusion of merging bonds (i.e., bonds connecting nodes in different clusters) should dominate with respect to the redundant bonds (i.e., bonds connecting nodes in the same cluster). Finally, we introduce a generalization of the product rule for explosive percolation that reveals the effect of nonlocality on the critical behavior of the percolation process. Precisely, pairs of unoccupied bonds are chosen according to a probability that decays as a power law of their Manhattan distance, and only that bond connecting clusters whose product of their sizes is the smallest becomes occupied. Our results for d-dimensional lattices at criticality shows that the power law exponent of the product rule has a significant influence on the finite-size scaling exponents for the spanning cluster, the conducting backbone, and the cutting bonds of the system. For all these types of clusters, we observe a clear transition from ordinary to (nonlocal) explosive percolation.