Kleinberg’s Navigation in Fractal Small-World Networks by Dynamic Rejection Sampling

We study Kleinberg’s navigation in small-world networks with fractal geometry (Sierpinski Carpet) using the dynamic rejection sampling algorithm adapted for this purpose. It is a methodology that dispenses with the application of periodic boundary conditions and consequently does not deform the toroid network. Instead, the technique relies on acceptance masks overlaid on the square network to regulate the distribution of long-range links. As a result, the complexity of the algorithm is drastically reduced. In this research, we propose an adaptation of the acceptance masks, originally conceived for two-dimensional (2D) Euclidean networks, in order to make them capable of recognizing fractal geometry. This is done by implementing an auxiliary routine (fractal_search) capable of identifying the fractal topology. After an extensive validation process, we concluded that the adaptation attempt was successful and that it performed considerably better than traditional methods (torus) in all parameters analyzed.