Algoritmos de amostragem por rejeição dinâmica aplicados a busca descentralizada em redes de mundo pequeno com topologia fractal
Nenhuma Miniatura disponível
Data
2021-11-23
Autores
Amaral, Leonardo Aguiar do
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
Resumo
In this research, we study Kleinberg’s navigation in small-world networks using the dynamic rejection sampling algorithm proposed by Mathieu and Comte. Unlike conventional techniques, this approach dispenses with the use of periodic boundary conditions that deform the lattice and convert it into a toroid. Instead, acceptance masks are used superimposed on the studied square network to offer an additional acceptance criterion for the acquisition of long-range links, without violating the fundamental precepts that govern the statistical distribution of these connections, resulting in a drastic drop in the complexity of the algorithm. This work aims to extend Mathieu and Comte’s approach to networks with fractal topology (Sierpinski’s Square), this is done through the development of an auxiliary computational routine (fractal_search) which makes fractal geometry detectable to acceptance masks. This is a step of great relevance for the entire process regarding the complexity of the algorithm since the knowledge accumulated in the literature in the last decade indicates that the emergence of routing in fractal networks requires that they have extremely large sizes. Our routine was designed to operate recursively and harmonically with fractal self-similarity, which guarantees a performance compatible with the tasks it will perform during the simulation. The approach adopted in conducting this work was consistent with the forecasts and results already consolidated and published in journals specialized in the field of network science, such as the existence of a clustering exponent that minimizes the delivery time, when it assumes values identical to the dimension of the analyzed network (αmin = df ), besides the appearance of the proportionality of the delivery time with the logarithm of the network size (T ∼ ln2L). It was also demonstrated that the number of realizations (R), used to compose the sampling space of the statistical analysis of the simulation, and the network size (L), have interdependence and have a significant impact on the processing time. Finally, we performed a performance test using the execution time as a comparative parameter, which demonstrated the superiority of the proposed method compared to traditional methods.
Descrição
Palavras-chave
Fractal , amostragem por rejeição dinâmica , small-world , navegação em redes , network science