I would like to create an online social network like friendster. The
core of this is will be storing the relations between people querying
those relations to say e.g. "X is four degrees of separation from Y".
Are there any scripts that do this, preferably in PHP. If not, how
should this be approached?

Try this to start: http://slashster.sourceforge.net/