Dynamic rejection sampling algorithms applied to decentralized search in small-world networks with fractal topology.

Name: Leonardo Aguiar do Amaral
Type: PhD thesis
Publication date: 23/11/2021

Namesort descending Role
Humberto Belich Junior Advisor *

Examining board:

Namesort descending Role
Antônio Canal Neto Internal Examiner *
Cássio Cecato Favarato External Examiner *
Humberto Belich Junior Advisor *
Thales Costa Soares External Examiner *
Vinícius Cândido Mota Internal Examiner *
Wesley Spalenza External Examiner *

Summary: 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 dropin 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, wich 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 aclustering 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.

Access to document

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910