Desenvolvimento de um Algoritmo de Busca por Vértices Específicos em Redes

  • Pedro Freitas
  • Victor Cardoso
  • Giulio Iacobelli
  • Daniel Figueiredo

Resumo


Muitas redes reais não estão disponíveis de forma imediata mas podem ser coletadas através de um processo de mineração. Entretanto, em alguns cenários estamos interessados em descobrir apenas vértices que possuem determinadas características, sendo irrelevantes os demais vértices. Para esse problema, algoritmos de busca clássicos (ex. busca em largura) se mostram ineficientes. Neste trabalho utilizamos a homofilia - inerente em muitas redes reais - para propor um modelo matemático que determina a probabilidade de um vértice não explorado possuir a característica. O modelo utiliza as características dos vértices vizinhos já explorados e parâmetros globais da rede. As probabilidades atribuídas pelo modelo guiam um algoritmo de busca informada, que a cada passo faz uma escolha gulosa. Avaliamos o algoritmo em três redes reais, comparando diferentes variações do modelo e outros algoritmos de busca. Os resultados indicam que nenhum dos métodos testados é consistentemente mais eficiente que os demais.

Publicado
06/07/2017
FREITAS, Pedro; CARDOSO, Victor; IACOBELLI, Giulio; FIGUEIREDO, Daniel. Desenvolvimento de um Algoritmo de Busca por Vértices Específicos em Redes. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 16. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6167. DOI: https://doi.org/10.5753/wperformance.2017.3362.