?

Log in

No account? Create an account
6 degrees of separation - brad's life — LiveJournal [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

6 degrees of separation [Jan. 24th, 2004|09:16 pm]
Brad Fitzpatrick
[Tags|, ]

I implemented 6 degrees of separation tonight for LiveJournal. It took all of about an hour.

It looks like I started working on it 3 years ago once because when I went to type:

$ emacs dev/6d.pl

I expected to get a new file, but there was already something there! And I knew it was old code because it used the ancient LJ APIs (which no longer worked). An ls -l dev/6d.pl showed a date in Dec 2000! Crazy.

Anyway, memcache made it easy, and I've known how I'd implement it for the past 3 years apparently.... just never got back around to it.

Don't expect it on the live site anytime soon, but it'll probably get posted to lj_dev/lj_nifty for testing in a bit here.

Screenshot!
lj@mayor:~$ time dev/6d.pl brad elims | tail -2
returning via friend-of-friend intersection with friendof-friendof
PATH: (2)brad, (1635)revjim, (438547)babycola, (714565)dorsai, (1095875)elims,

real 0m1.201s
user 0m0.540s
sys 0m0.060s

Note: That's without prefetching certain memcache objects in big requests so there are a lot of unnecessary round-trips in there still. The time will come down. I'm also not caching any subpaths yet.

Also consider it takes 0.6 seconds just to invoke Perl loading the LJ libraries. So not bad.
LinkReply

Comments:
[User Picture]From: krow
2004-01-24 09:32 pm (UTC)
Did you notice how Google's Friendster used some of my terms from Slash's friends system?

Notice how they also implemented 6 degrees in a manner to avoid the patten on it (aka they have fans like Slashdot and don't requires mutual agreement).
(Reply) (Thread)
[User Picture]From: brad
2004-01-24 09:37 pm (UTC)
Yeah, I saw a lot of borrowing of ideas in Orkut (Slashdot/LiveJournal/Friendster), but that's the way it should work.

Refresh my memory on the patent: it was about using email/confirmations to create a undirected friend graph automatically after users initiate directed edges on their own, right?

It's not about showing 6 degrees with mutual friend paths, is it?

Does this violate the patent?
http://www.petekrawczyk.com/lj_connect/

It has a "Mutual friends only" checkbox.
(Reply) (Parent) (Thread)
[User Picture]From: krow
2004-01-24 09:52 pm (UTC)
Using email to confirm mutual relationships is the key to the patent (the fact that with LJ relationships are not confirmed keeps you clear of the patent). The lj_connect avoids it since it is just using data to generate its graphs.

The patent is very, very narrow.

Toss in a bit more support for your match making software and you have all the pieces :)
(Reply) (Parent) (Thread)
From: evan
2004-01-25 10:48 am (UTC)
might be worth contacting that fellow and stealing as much of his ideas as possible. all of my interactions with him lead me to believe he's clued.


it'd be neat if you could cache these calculated paths somehow and use them to build up a map of the network, or estimates of the diameter. (maybe just cache their length and their creation time?) that researcher who was trying to find the diameter of lj had to basically run dijkstra's algorithm for every user and he said it took weeks of cpu time.
only do it reactively user requests would bias the results towards shorter links, though.
(Reply) (Parent) (Thread)