Um Algoritmo de Busca por Vértices com Características Específicas em Redes
Autores
|
6456 |
2922,753
|
|
|
6457 |
2922,753
|
Informações:
Publicações do PESC
Neste trabalho, utilizamos o conceito de homofilia intrínseco a muitas redes para propor um modelo matemático que determina a probabilidade de um vértice não explorado possuir uma determinada característica em uma rede desconhecida a priori. O modelo utiliza as características dos vértices vizinhos 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 quatro redes reais buscando diferentes características por meio de variações do nosso modelo e comparando com outros algoritmos de busca informados e desinformados. Os resultados empíricos indicam que nenhum método considerado é consistentemente mais eficiente que os demais.
In this work, we use the homophily of the networks to propose a mathematical model that determines the probability of an unexplored vertex to have the feature. This model uses the features of the neighbor vertices already explored and global parameters of the network. The probabilities assigned by the model are used to guide an informed search, which at each step makes a greedy choice. We evaluated the algorithm in four networks looking for different features using variations of the model and comparing with others informed and uninformed search algorithms. The empirical results show that none of considered methods is consistently more eficient than the others.