Bob the WonderClown (wonderclown) wrote in lj_dev,
Bob the WonderClown

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.)

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded