relações de amizade rastreamento algoritmo

Question

Estou pensando em um aplicativo que iria tentar provar a " Seis graus de separação " teoria com um conjunto de usuários que fazem parte de uma rede social.

eu teria esses elementos:

1. Um par de usuários para o qual eu gostaria de provar a teoria dos seis graus
2. Para cada usuário, eu sei que a lista de amigos na rede social

Qual é o melhor algoritmo para ver se os dois usuários estão conectados, com que grau e mostrar os eventuais passos na conexão?

Answer 1

Encontrar o grau de separação entre duas pessoas em uma rede social é apenas um caso especial de encontrar o caminho mais curto entre dois pontos em um gráfico. A abordagem mais comum é de Dijkstra algoritmo , mas ver também uma discussão mais longa do Shortest problema do caminho .

Além disso, executando um pares de All menor algoritmo de caminho, você pode descobrir o mínimo, máximo e média do número de graus de separação para toda a rede.

Answer 2

Alguns material de apoio adicional:

Para resolver este problema, geralmente, você quer evitar raspagem web e outras técnicas ad-hoc que são específicos para uma rede social. Em vez disso, você provavelmente vai querer olhar para XHTML Friends Network (XFN) que é uma maneira de usar o rel = "" atributo de um hyperlink para indicar a relação entre o alvo desse hiperlink e você. Há também um padrão de competência chamado FOAF que usos RDF .

microformatos foram em torno de um tempo, mas o suporte para eles tem crescido muito recentemente. StackOverflow usa "me" no link em sua página de perfil. blogs WordPress fornecer uma maneira fácil na interface de edição para o blogroll para adicionar essas tags. Muitos sites sociais usá-los em ligações entre amigos para indicar relacionamentos.

Devido a isso, o Google ficou interessado nisso, e está começando a mina de dados. Eles têm um Social Graph API que pode mina de ambos os dados XFN e FOAF para fazer exatamente alguns dos as coisas que você quer fazer. Sugiro que comece lá. A coisa agradável sobre a API do Google é porque eles são a mineração essa em toda a web, você pode alargar a sua pesquisa para além da rede social específico que você tinha em mente.