Come posso dimostrare i “Sei gradi di separazione” concetto di programmazione?

Question

Ho un database di 20 milioni di utenti e le connessioni tra le persone. Come posso dimostrare il concetto di "Sei gradi di separazione" concept nel modo più efficiente in programmazione?

link per l'articolo su sei gradi di separazione

Answer 1

Hai voglia di misurare la diametro del grafico. Questo è esattamente la metrica per scoprire la separazione tra i nodi più-lontano-collegati in un grafico.

Un sacco di algoritmi su Google, grafico Boost anche.

Answer 2

Probabilmente si può adattare il grafico in memoria (nella rappresentazione che ogni vertice conosce un elenco dei suoi vicini).

Poi, da ogni vertice n , è possibile eseguire una ricerca in ampiezza (con una coda) alla profondità di 6 e contare il numero di vertici visitati. Se non tutti i vertici sono visitati, è stato smentito il teorema. In altro caso, continuare con vertice successivo n .

Questa è O (N * (N + #edges)) = N * (N + N * 100) = 100N ^ 2, se l'utente dispone di 100 connessioni in media, che non è l'ideale per N = 20 milioni. Mi chiedo se le librerie citate possono calcolare il diametro in meglio la complessità di tempo (algoritmo generale è O (N ^ 3)).

I calcoli per i singoli vertici sono indipendenti, in modo che potessero essere condotti in parallelo.

Un po 'euristica: iniziare con i vertici che hanno il più basso grado (migliore possibilità di confutare il teorema)

.

Answer 3

Credo che il modo più efficace (caso peggiore) è quasi N ^ 3. Costruire una matrice di adiacenza, e poi quella matrice ^ 2, 3 ^, ^ 4, 5 ^ e 6 ^. Cercare eventuali voci nel grafico che sono 0 per matrice attraverso matrice ^ 6.

Euristicamente si può provare a individuare sottografi (grandi ciuffi di persone che sono collegati solo ad altri grumi da un numero relativamente piccolo di nodi "ponte"), ma non c'è assolutamente alcuna garanzia che avrete qualsiasi.

Answer 4

Bene una risposta migliore è già stato dato, ma la parte superiore della mia testa mi sarebbe andato con la Floyd-Warshall tutte le coppie algoritmo percorso più breve, che è O (n ^ 3). Non sono sicuro della complessità dell'algoritmo di diametro grafico, ma "suona" come questo sarebbe anche O (n ^ 3). Mi piacerebbe un chiarimento su questo se qualcuno sa.

Una nota a parte, non si ha realmente dispone di un tale database? Spaventoso.