Ho un database di 20 milioni di utenti e connessioni tra queste persone. Come posso dimostrare il concetto di "Sei gradi di separazione" nel modo più efficiente nella programmazione?Come posso dimostrare il concetto di "Sei gradi di separazione" a livello di programmazione?
link to the article about Six degrees of separation
si desidera solo per misurare la diameter of the graph. Questo è esattamente la metrica per scoprire la separazione tra i nodi più-lontano-collegati in un grafico.
Un sacco di algoritmi su Google, Boost graph.
Probabilmente è possibile adattare il grafico in memoria (nella rappresentazione che ciascun vertice conosce un elenco dei suoi vicini).
Quindi, da ciascun vertice n, è possibile eseguire una ricerca in larghezza (utilizzando una coda) alla profondità di 6 e contare il numero di vertici visitati. Se non tutti i vertici sono visitati, hai smentito il teorema. In altri casi, continuare con il vertice successivo n.
Questo è O (N * (N + #edges)) = N * (N + N * 100) = 100N^2, se l'utente ha 100 connessioni in media, che non è l'ideale per N = 20 milioni. Mi chiedo se le librerie citate possano calcolare il diametro in una migliore complessità temporale (l'algoritmo generale è O (N^3)).
I calcoli per i singoli vertici sono indipendenti, quindi potrebbero essere eseguiti in parallelo.
Un po 'euristico: iniziare con i vertici che hanno il grado più basso (migliore possibilità di confutare il teorema).
Penso che questo sia considerevolmente peggiore di O (n^2). anche supponendo che ogni nodo sia connesso solo a 3 altri nodi, una traccia di stack di profondità 6 sarebbe 3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5. Crescita esponenziale – patros
Per ogni vertice si visita al massimo un vertice una volta sola, quindi la corsa per un vertice prende O (N). –
Ah, vero, questo è un limite. Penso che questo sia ancora O (N^3), allora non è vero? Trovare un percorso dal vertice A al vertice B è O (N), e devi fare questo O (N^2) volte. – patros
Penso che il modo più efficiente (il caso peggiore) sia quasi N^3. Costruisci una matrice di adiacenza e poi prendi quella matrice^2,^3,^4,^5 e^6. Cerca eventuali voci nel grafico che sono 0 per matrice attraverso la matrice^6.
euristicamente si può provare a individuare sottografi (grandi gruppi di persone che sono solo collegati ad altri gruppi da un numero relativamente piccolo di nodi "bridge") ma non è assolutamente garantito che ne avrete.
Non è possibile creare una matrice di adiacenza di dimensioni 20x20 milioni in memoria. Inoltre, la moltiplicazione sarebbe O (N^3), dove N è 20 milioni. –
È approssimativamente n^2.8 con l'algoritmo di strassen, poiché sono matrici quadrate. inoltre non è necessario conservare l'intero matix in memoria, ma solo le parti che si stanno moltiplicando attivamente. Pagina il resto su disco. – patros
Richiede molto disco però ... 400 TB per un approccio ingenuo. Un sacco di spazio per la compressione però. – patros
Ben una risposta migliore è già stata data, ma in cima alla mia testa sarei andato con l'algoritmo del percorso più breve delle coppie pari a Floyd-Warshall, che è O (n^3). Non sono sicuro della complessità dell'algoritmo del diametro del grafico, ma "suoni" come questo sarebbe anche O (n^3). Vorrei chiarimenti su questo se qualcuno lo sa.
Su una nota a margine, hai davvero un tale database? Spaventoso.
È sei gradi al massimo o in media? La maggior parte dell'analisi attuale che ho letto utilizza la media non il massimo. –
La concezione comune di "sei gradi di separazione" è che è un massimo. Certo, non è affatto vero nella realtà. È semplicemente più impressionante dirlo in questo modo e difficile trovare dei controesempi. –