computing social networks

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.

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”