Google this site (~ 2000 pages):

Home
RSS Feed RSS Feed

« Previous: deadly knockers | Next: object-centered sociality, AI and tagwebs »


just researched the question how the shortest path(s) between two persons in social networks is being calculated. i always have asked myself how this is done as it’s clear to everyone with basic database know-how that presenting such paths in realtime, as services such as friendster, orkut or openBC do, is quite a challenge. now i needed it for a project, so i googled the question.

dijkstra (14k image)

the formula they use is dijkstra’s algorithm. it doesn’t just find the shortest path between two nodes, it finds the path between a node and every other node in the network. therefore computing a path is just as much effort as computing them all. as it’s quite hard to do that in real time, so i guess the solution is to pre-compute them and make them available before requested by a user.

related documents: see my del.icio.us tags “social networks”


 

« Previous: deadly knockers | Next: object-centered sociality, AI and tagwebs »

No Comments

Sorry, the comment form is closed at this time.

corner