Algoritmo di tracciamento delle relazioni di amicizia

Question

Sto pensando a un'applicazione che proverebbe a provare il Sei gradi di separazione " teoria con un insieme di utenti che fanno parte di un social network.

Avrei questi elementi:

1. Un paio di utenti per i quali mi piacerebbe dimostrare la teoria dei sei gradi
2. Per ogni utente, conosco l'elenco di amici nel social network

Qual è l'algoritmo migliore per vedere se i due utenti sono connessi, con quale grado e mostrare gli eventuali passaggi nella connessione?

Answer 1

Trovare il grado di separazione tra due persone in un social network è solo un caso speciale di trovare il percorso più breve tra due punti in un grafico. L'approccio più comune è L'algoritmo di Dijkstra , ma vedi anche una discussione più lunga < href = "http://en.wikipedia.org/wiki/Shortest_path_problem" rel = "nofollow noreferrer"> Problema del percorso più breve .

Inoltre, eseguendo un algoritmo del percorso più breve di tutte le coppie, è possibile scoprire il numero minimo, massimo e medio di gradi di separazione per l'intera rete.

Answer 2

Alcuni materiali di base aggiuntivi:

Per risolvere questo problema in generale, dovresti evitare il web scraping e altre tecniche ad hoc specifiche di un social network. Invece, probabilmente vorrai esaminare XHTML Friends Network (XFN) che è un modo per usare la rel = " " attributo di un collegamento ipertestuale per indicare la relazione tra la destinazione di tale collegamento ipertestuale e l'utente. Esiste anche uno standard concorrenziale chiamato FOAF che utilizza RDF .

Questi microformati sono in circolazione da un po 'di tempo, ma il supporto per loro è cresciuto molto di recente. StackOverflow utilizza " me " nel link sulla pagina del tuo profilo. I blog di WordPress forniscono un modo semplice nell'interfaccia di modifica per il blogroll di aggiungere questi tag. Molti siti social li usano nei collegamenti tra amici per indicare relazioni.

Per questo motivo, Google si è interessato a questo e sta iniziando a estrarre questi dati. Hanno un API del grafico sociale che può estrarre i dati XFN e FOAF per fare esattamente alcuni dei le cose che vuoi fare. Ti suggerisco di iniziare da lì. La cosa bella dell'API di Google è che dal momento che stanno eseguendo il mining su tutto il Web, puoi ampliare la tua ricerca oltre lo specifico social network che avevi in ??mente.