I seem to remember Max Levchin talking about this exact problem at Startup School. He was talking about how Friendster shot themselves in the foot by calculatin

I seem to remember Max Levchin talking about this exact problem at Startup School. He was talking about how Friendster shot themselves in the foot by calculating all the hops between you and whomever's profile you were viewing, slowing page load significantly. He pointed out that Myspace provided similar user experience by simply slapping "Is in your extended network" on all pages.