Busca eficiente em redes sociais

Abstract

Search-engines use link-based signals, like pagerank ou authority, to improve the quality of the results. However, in other scenarios where these signals are either not appropriate or impossible to calculate, some other form of trust signal must be used. For instance, in the case of social networks, one alternative signal to improve a search for a given person are friends relationships. To illustrate, if John is looking for Maria, a good ranking function would favor the Maria's that are closer to John. However, if the relationships graph is large, computing these distance efficiently is non-trivial. To overcome this, we propose a seeds-based approximation algorithm that can speed up execution times on the Orkut social network by three orders of magnitude with respect to the brute force solution, while keeping the approximation error on the ranking smaller than 30%. By reducing the speedup to two orders of magnitude, we are able to attain approximation errors smaller than 12%. These results show that great speed up can be attained for computing friendship distances in social networks - a crucial signal for search ranking - within acceptable error margins.