Algoritmos de amostragem por rejeição dinâmica aplicados a busca descentralizada em redes de mundo pequeno com topologia fractal

Página do item simplificado
bibo.pageEnd100
dc.contributor.advisor1Belich Junior, Humberto
dc.contributor.advisor1IDhttps://orcid.org/0000-0002-8795-1735
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/3879935393431243
dc.contributor.authorAmaral, Leonardo Aguiar do
dc.contributor.authorIDhttps://orcid.org/0000-0001-8951-4304
dc.contributor.authorLatteshttp://lattes.cnpq.br/3747190706760201
dc.contributor.referee1Soares, Thales Costa
dc.contributor.referee1IDhttps://orcid.org/0000-0001-8734-6642
dc.contributor.referee1Latteshttp://lattes.cnpq.br/4676057702132305
dc.contributor.referee2Canal Neto, Antônio
dc.contributor.referee2IDhttps://orcid.org/0000-0002-8556-618X
dc.contributor.referee2Latteshttp://lattes.cnpq.br/9283775492064031
dc.contributor.referee3Spalenza, Wesley
dc.contributor.referee3IDhttps://orcid.org/0000-0001-9644-3938
dc.contributor.referee3Latteshttp://lattes.cnpq.br/2687428810786056
dc.contributor.referee4Mota, Vinicius Candido
dc.contributor.referee4IDhttps://orcid.org/0000000183680803
dc.contributor.referee4Latteshttp://lattes.cnpq.br/4038237972209273
dc.contributor.referee5Favarato, Cássio Cecato
dc.contributor.referee5IDhttps://orcid.org/0000-0002-7599-595X
dc.contributor.referee5Latteshttp://lattes.cnpq.br/0364649580177297
dc.date.accessioned2024-05-30T00:50:24Z
dc.date.available2024-05-30T00:50:24Z
dc.date.issued2021-11-23
dc.description.abstractIn 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.
dc.description.resumoNesta pesquisa estudamos a navegação de Kleinberg em redes de mundo pequeno através do algoritmo de amostragem por rejeição dinâmica, proposto por Mathieu e Comte. Ao contrário das técnicas convencionais, esta abordagem dispensa a utilização de condições de contorno periódicas que deformam a rede e a converte em toroide. Ao invés disso, utiliza-se máscaras de aceitação sobrepostas a rede quadrada estudada com o intuito de oferecer um critério de aceitação adicional para aquisição de links de longo alcance, sem contudo, violar os preceitos fundamentais que regem a distribuição estatística dessas conexões, resultando numa queda drástica da complexidade do algoritmo. O objetivo deste trabalho é estender a abordagem de Mathieu e Comte a redes com topologia fractal (Quadrado de Sierpinski), isso é feito através do desenvolvimento de uma rotina computacional auxiliar (fractal_search) que torna a geometria fractal detectável às máscaras de aceitação. Esta é uma etapa de grande relevância para a totalidade do processo no que diz respeito a complexidade do algoritmo, uma vez que o conhecimento acumulado em literatura na última década indica que a emergência de roteamento em redes fractais exige que estas possuam tamanhos extremamente elevados. Nossa rotina foi projetada para operar de forma recursiva e harmônica com a autossimilaridade fractal, o que lhe garante desempenho compatível com as tarefas que irá desempenhar durante a simulação. A abordagem adotada na condução desse trabalho se mostrou consistente com as previsões e resultados já consolidados e publicados em periódicos especializados na área de ciência de rede, tais como: a existência de um expoente de clusterização que minimiza o tempo de entrega, quando este assume valores idênticos ao da dimensão da rede analisada (αmin = df ), além do surgimento da proporcionalidade do tempo de entrega em relação ao logaritmo do comprimento da rede (T ∼ ln2L). Também ficou demonstrado que o número de realizações (R), utilizado para compor o espaço amostral das análises estatísticas da simulação, e o comprimento da rede (L), possuem interdependência e causam impacto expressivo no tempo de processamento. Finalmente, realizamos um teste de desempenho tomando como parâmetro comparativo o tempo de execução, em que ficou demonstrada a superioridade do método proposto em comparação aos métodos tradicionais.
dc.description.sponsorshipFundação Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
dc.formatText
dc.identifier.urihttp://repositorio.ufes.br/handle/10/15360
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseDoutorado em Física
dc.publisher.departmentCentro de Ciências Exatas
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Física
dc.rightsopen access
dc.subjectFractal
dc.subjectamostragem por rejeição dinâmica
dc.subjectsmall-world
dc.subjectnavegação em redes
dc.subjectnetwork science
dc.subject.br-rjbnsubject.br-rjbn
dc.subject.cnpqFísica
dc.titleAlgoritmos de amostragem por rejeição dinâmica aplicados a busca descentralizada em redes de mundo pequeno com topologia fractal
dc.title.alternativeDynamic rejection sampling algorithms applied to decentralized search in small-world networks with fractal topology
dc.typedoctoralThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
LeonardoAguiardoAmaral-2021-tese.pdf
Tamanho:
5.04 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Doutorado em Física