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

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.