Grafos no Orkut
Author: Jonas Abreu21 Jan
Essa é mais uma feature que o Google possui que está acelerando o processo de calvicie em mim.
Todo mundo conhece o orkut. Aquele sistema bobo, sem muita utilidade concreta mas que faz um sucesso absurdo (Inclusive, existe uma comunidade do VidaGeek.net lá).
O que muitos não notam é um pequeno detalhe que aparece quando você está no perfil de outra pessoa. O Orkut mostra pra você o caminho mais curto entre você e essa outra pessoa (atravéz de amigos).
O que que isso tem de assustador? É apenas uma busca em um grafo… Com milhões de vértices. Faça um programa simples que faz uma busca em um grafo com milhões de vértices e você vai entender do que estou falando. Demora muito mais do que uma requisição no Orkut pode demorar.
Ou seja, tudo isso está pré-calculado. Quando você acessa o perfil de outra pessoa, o algoritmo já rodou e ele simplesmente recupera a informação e devolve para você.
O jeito mais simples de fazer isso? Um Floyd-Warshall modificado (para não levar o peso das arestas em consideração), com complexidade O(n^3) rodado quando algum usuário se cadastra no Orkut ou sai dele.
Isso não funciona. Com a quantidade de usuários que o orkut tem, ele teria saido do ar há muito tempo se fosse desse jeito. Uma estratégia lazy (rodar apenas de tempos em tempos) também não ajuda muito, pois ocupa muito espaço em disco (quando o orkut foi criado, ele manteve vários milhares de usuário apenas com um computador comum como servidor).
O que é mais possível, então? Uma boa Heurística. Hoje mesmo eu notei que têm alguns profiles que eu entro e não aparece a sequência de usuários. Portanto, o que deve ser feito é estabelecer um limite na profundidade da busca, baseado nos seus amigos e nas comunidades em que você participa. Isso reduz de milhões de usuários para milhares de usuários. Mesmo assim ainda acho que é um esforço computacional muito grande e provavelmente deve ser rodado de forma lazy (especialmente se você lembrar que já está sendo usada uma heurística e nem sempre vai aparecer o caminho).
Posts Relacionados:
Acompanhe-nos por
RSS, por Email ou via Twitter.
Veja como ter um desconto no Dreamhost: um excelente servidor web.
Email This Post
10 Responses for "Grafos no Orkut"
[...] « TRUE & TRUE == FALSE ? Grafos no Orkut [...]
Uma vez li, não me lembro onde, que algumas quantidades como “número de amigos” são pré-calculadas, e que houve algum erro nos primórdios do orkut que não foi percebido. Elas continuam erradas pois não é possível calcular tudo novamente. Estranho é que “número de amigos” varia cada vez que você entra no orkut, pelo menos para mim.
Olá,
Você já pensou em fazer uma busca em largura bidirecional?
A busca começa com duas sementes, uma no que se diz origem e outra no que se diz “destino”. Se houver um caminho, então haverá um encontro. O pior caso é quando não há caminho, mas ainda sim há algumas medidas que poderiam ser tomadas.
Observe que o fato de ser bidirecional reduz muitissimo a complexidade do algoritmo. Pense nisso…
Olá Rodrigo,
você poderia me explicar como que a complexidade fica reduzida usando esse algoritmo? No pior caso, você continua com um algoritmo linear (vai ter que varrer todos os nós para encontrar o caminho mais curto).
Até!
A complexidade de uma busca em largura pode ser analisada em função do branch factor $b$ (seria uma média do grau de cada nó. Na verdade não é exatamente isto, pois podem haver ciclos, mas seria quantos nós são “abertos” na média a partir de um outro nó durante a buca), e $d$ a profundidade.
Então a complexidade seria O(b^d). OK?
Agora uma busca em largura bidirecional seria 2*(b^(d/2)). Pois seria como duas buscas que se aprofundam metade.
Tem complexidade muiiiito melhor.
Acabei achando uma referência para vc.
Inclusive, heurísticas também podem ser usadas para a expansão da busca.
http://en.wikipedia.org/wiki/Bidirectional_search
Sobre o que vc falou de pior caso:
Você concorda comigo que se na busca a profundidade até então expandida dos dois lados for maior que ceil(d/2) e não houve um encontro (uma busca nao visitou um no visitado pela outra busca) então quer dizer que este não existe caminho entre os nós?
Assim, o pior caso é 2*(b^(d/2)), acho…. hehehe
O que vc acha?
Abração.
Rodrigo
Jonas, desculpe enviar tudo picado.
Acabei pensando em mais uma coisa.
Provavelmente poderia ainda colocar um limite no $d$ ou seja, não mostrar caminhos se a distancia for maior que 4 por exemplo.
Suponha que em média uma pessoa tenha 100 amigos.
Assim, no pior caso, teriamos 2*100^2 visitas, 2000 nós visitados. Isso é muito rápido!
Rodrigo
hehhe… não sei fazer contas, rs.
Seria 20000 visitas.
Ainda é razoável, mas temo que não seria viável fazer isto com tantas pessoas acessando. Mas ainda teriam as heurísticas.
Jonas, teria como vc unificar esses meus comentários picados?
Tive outras idéias, desculpe se estou poluindo seu post…
Suponha que queiramos saber se existe um caminho de distância no maximo D amigo1 -> outro -> Você)
Suponha que exista as seguintes estruturas
L[<=1](pessoa) é uma lista ordenada (pelo id) de amigos de amigos de “pessoa” mais os seus proprios amigos.
Ou seja, todo mundo que está a uma distancia D <= 1.
Toda vez que Eu adiciono um amigo, então L[<=1](Eu) é atualizado. |L[<=1](pessoa)| é em média b²
Seja U o conjunto de amigos de “Eu”
Seja V o conjunto de amigos de “Você”
a) Se e somente se existe intersecção entre L[<=1](Eu) e L[<=1](Voce), existe um caminho de distância 3!
Idéia 1:
Um algoritmo de merge em L[<=1](Eu) e L[<=1](Voce) é em média b²+b², ou seja O(b²)
Mas nem é necessário calcular todo merge.
Assim, no pior caso, temos um algoritmo mal escrito em O(b²) de encontrar o caminho com D<=3.
Idéia 2:
Agora, suponha que vc tivesse 2 hashes:
H[<=1]_Eu(y) que é true se e somente se y está em L[<=1](Eu)
H[<=1]_Voce(z) que é true se e somente se z está em L[<=1](Voce)
Então Para cada u em U, Se H[<=1]_Voce(u) é true, então há um caminho com distância menor igual a 3.
Caso não satisfeito nenhuma dessas b condições, não há caminho.
Nesse caso, teriamos um algoritmo O(b) supondo hashes perfeitos.
Gasta bastante espaço, acho. Mas em termos de tempo, é muito bom, né?
Daria inclusive para manter atualizado diretamente os hashes ao invés das listas.
O ponto chave seria uma forma de atualizar eficientemente os hashes. Feito isso,
daria para generalizar inclusive para H[<=K]_Voce(u), ou seja, generalizando a distancia máxima do caminho.
Com K=1 sabemos se há caminho com distância máxima D <= 3
Em geral, dado K, sabemos se há caminho com distância máxima D amigo -> outro -> você), com D<=3:
Atualizo hash em O(b) toda vez que adiciono um amigo e encontro o caminho em O(b) quando necessário!
Creio que b é muito difícil ser maior que 1000.
O que vc acha?
Leave a reply