March 7th, 2003

Serious (long), Serious

LJ "n-Degrees of Separation"?

Sorry if this isn't the right place to ask this...I couldn't think of anywhere better.

Has anybody ever done a "degrees of separation" analysis for LiveJournal? That is, analyze the graph of userids connected by friendship to determine what is the largest number of hops that separates any two given users. More specifically, for all pairs of users, determine the maximum length of the shortest path connecting the two users. (Obviously there may be some islands of unconnected users, but I'm sure there is a single very large connected set which dwarfs all others.)

I could, of course, determine this on my own by writing a program that crawls the graph via HTTP, fetching the userinfo pages and parsing the HTML to get what I need. But that would be way more load on the servers than if somebody could run a program directly against the database.

Another related thing that would be neat: a web interface that lets you enter two userids and shows the shortest path between them.

I have no real reason to want to do this, just an academic curiosity. If somebody has already done this, point me to it. If anybody out there in LJ-admin land would be willing to run a program I write to do it against the database, just say the word! (Of course, you'd get full source code so you could make sure I wasn't doing anything nasty, and you could give it read-only access to the database for safety. And if you don't want to chew your CPU cycles, an export of the friends table is all I need, and I can then run it on my machine.)