Busca eficiente em redes sociais

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

RESUMO

Redes sociais são utilizadas para a interação entre as pessoas. Uma das principais operações de uma rede social é a busca por um usuário. Enquanto máquinas de busca utilizam sinais baseados em sua estrutura de enlaces (links), como Pagerank e autoridade, para melhorar a qualidade de seus resultados, em uma rede social, esses sinais não são apropriados. Nesse caso, um sinal alternativo para melhorar a busca por uma pessoa são os relacionamentos de amizade definidos na rede social. Para ilustrar, se João procura por Maria, uma boa função de ordenação daria maior peso para as Marias mais próximas do círculo de relacionamento de João. Entretanto, se o grafo de relacionamentos é grande, a computação eficiente dessas distâncias deixa de ser um problema trivial. Diante desse problema, propomos um algoritmo baseado em sementes que aproxima as distâncias de maneira eficiente, e pode oferecer ganhos nos tempos de execução no Orkut de até três ordens de grandeza com relação à solução força bruta, mantendo precisões acima de 70%. Reduzindo o ganho nos tempos de execução para duas ordens de grandeza, a precisão dos resultados ultrapassa 90%. Esses resultados mostram que é possível obter excelentes ganhos de desempenho na computação de distâncias de relacionamento em redes sociais - um sinal crucial para a busca dentro de margens de erro aceitáveis, o que viabiliza a utilização desse importante sinal em redes sociais de grande porte.

ASSUNTO(S)

world wide web (sistema de recuperação da informação). sistemas de recuperação da informação teses. computação teses.

Documentos Relacionados