Como posso provar o conceito de “seis graus de separação” programaticamente?

Question

Eu tenho um banco de dados de 20 milhões de usuários e conexões entre essas pessoas. Como posso provar o conceito de conceito de "seis graus de separação" da maneira mais eficiente na programação?

Link para o artigo cerca de seis graus de separação

Answer 1

Você só quer medir o diâmetro do gráfico.Esta é exatamente a métrica para descobrir a separação entre os nós mais conectados a distância em um gráfico.

Muitos algoritmos no Google, Boost Gráfico também.

Answer 2

Você provavelmente pode ajustar o gráfico na memória (na representação de que cada vértice conhece uma lista de seus vizinhos).

Então, de cada vértice n, você pode executar uma pesquisa pela primeira vez (usando uma fila) até a profundidade de 6 e a contagem do número de vértices visitados. Se nem todos os vértices forem visitados, você refutou o teorema. Em outro caso, continue com o próximo vértice n.

Isso é o (n*(n + #edges)) = n*(n + n*100) = 100n^2, se o usuário tiver 100 conexões em média, o que não é ideal para n = 20 milhões. Gostaria de saber se as bibliotecas mencionadas podem calcular o diâmetro na melhor complexidade do tempo (o algoritmo geral é O (n^3)).

Os cálculos para vértices individuais são independentes, para que possam ser feitos em paralelo.

Um pouco heurístico: comece com vértices com o menor grau (melhor chance de refutar o teorema).

Answer 3

Eu acho que a maneira mais eficiente (o pior caso) é quase n^3. Construa uma matriz de adjacência e depois pegue essa matriz ^2, ^3, ^4, ^5 e ^6. Procure quaisquer entradas no gráfico que sejam 0 para matriz através da matriz^6.

De heuristicamente, você pode tentar destacar subgrafos (grandes pedaços de pessoas que estão conectadas apenas a outros aglomerados por um número relativamente pequeno de nós de "ponte"), mas não há absolutamente nenhuma garantia de que você terá.

Answer 4

Bem, uma resposta melhor já foi dada, mas no topo da minha cabeça eu teria ido com o Floyd-Warshall todos os pares mais curtos do algoritmo do caminho, que é O (n^3). Não tenho certeza da complexidade do algoritmo de diâmetro do gráfico, mas "parece" como isso também seria O (n^3). Eu gostaria de esclarecimentos sobre isso, se alguém souber.

Em uma nota lateral, você realmente tem esse banco de dados? Apavorante.