Friendster

January 12, 2004 8:13 PM

On friendster, why can I click on some of my friends' friends, but not others? If I am a verified friendster-friend of someone, shouldn't I be able to peruse all their friends' profiles, not just a seemingly-random subset?
posted by mfbridges to computers & internet (14 comments total)

i could be nuts, but i swear that i've seen it change for no apparent reason. maybe it couldn't verify your link to them at that time? friendster is moody like that.
posted by Hackworth at 9:14 PM on January 12, 2004

Don't they have some sort of technical support that you could contact?
posted by The God Complex at 9:19 PM on January 12, 2004

I have been getting lots of slow database connections and nonresponsive links of late. My guess is that their server is getting cranky with Friendster's popularity, but who knows.
posted by PrinceValium at 9:32 PM on January 12, 2004

I believe it has to do with how many links away in the friend chain they are from you. There is a specified number (I think it's 4 or 5) that is the maximum you are allowed to see. The underlying assumption is that they are too far removed from you to contact. (for CS nerds, the underlying technological limitation has to do with the standard traveling salesman problem; for each level of friends you are allowed to view, the processing power to discover connections increases exponentially).

So if you are on someone's friend page who is already 4 links away from you (assuming that's the limit), you won't be able to click on anyone who is not connected to you by any closer means. Any of their other friends who are connected to you through another party in four or fewer steps will be viewable to you.

Also, sometimes the friendster server is overloaded, and it appears to adjust this levels-limit downwards temporarily to cope with bandwidth, which could explain your variable results. Occasionally, it is so bad that you can only browse your direct friends.

not that I am one of those weirdos who hangs out on friendster, or anything
posted by toothless joe at 10:08 PM on January 12, 2004

I think you're a little confused w/r/t the traveling salesman problem. In this case, if I have 3 friends (purely hypothetical) named X, Y, and Z and I want to see all of the friends of X, then a single query retrieving all the friends of X should suffice. Thus, each iteration deeper I go into the web of friends can be done in O(1) time with a single query*.

The TSP deals with the cheapest way to 'travel' to each of a set of N nodes, and I don't really think it would apply to this.


*Assuming, for all intents and purposes that a db query runs in constant time.
posted by pemulis at 10:34 PM on January 12, 2004

pemulis: You are spot on in your comments, but you aren't considering the special computations that happen at the fringes of the friend levels. You actually do have to calculate the shortest route* in some situations.

To extend your example, assume that there is a viewing limit of 3 levels, which means I can view my friends, my friends' friends, and my friends' friends' friends, but anyone else is off limits because they are too distant. Then assume part of the friends network looks like this:

A < -> B, C, D
B < -> E
E < -> F
F < -> G

Now, person A can view person B (his friend), person E (his friend's friend), and person F (his friend's friend's friend) because they are all within the three levels of connections.

If he is looking at person F's profile, he will see the existence of person G, but he will not be able to view that person's profile because the connection has too many links. (A < -> B < -> E < -> F < -> G).

But that is assuming that he is not connected to person G through a different chain. If C < -> G, then he could connect through A < -> C < -> G, and thus be allowed to view person G's profile.

Or he could be connected by someone else entirely, for instance A < -> C < -> H < -> G.

So what that means in real terms is that in order to search for a connection to a person who is just outside of the realm of one friend chain, the system could potentially have to search each of the users friends, and each of their friends, etc.

Calculations really blow up when you get into searches. If friendster let you have 10 levels of friends and you searched for all members who had some characteristic (for instance age range), it would have to go 10 levels deep looking for people. None of this would be a problem if anyone could view anyone else on friendster that they wanted, but there are rules imposed on how far away on the friend chain one can view.

* Technically you are not looking for the shortest route, but any route shorter than a specified cutoff. I believe that doesn't change the order of the problem, but I must admit it's been a while since I looked at any of this. Also, the friendster software appears to list all links between people, so an exhaustive search is required if that is the case.
posted by toothless joe at 11:23 PM on January 12, 2004

Fantastic explanation joe.

So effectively what we would have is an undirected graph with the weights of node N being the minimum number of links needed to traverse to get from the source to N.

And if, each time we visit a node, a db query is needed to find its links, the computing cost needed could get *very* expensive.

You're right about this being a shortest paths problem as well, with complexity being O(|V| * |E|) where V is the number of vertices (friends) and E is the number of edges (connections between friends).

This was fun.
posted by pemulis at 11:44 PM on January 12, 2004

So, mfbridges, to answer your question... No.
posted by pemulis at 11:45 PM on January 12, 2004

Hooray for comp sci. Thanks guys! I understand the computational limitations of finding fourth-degree friends. But this is happening to second-degree friends, i.e. the friends of my immediate friends. Half of them I can click on, and half of them I can't. Do these same kinds of computational problems apply to people so closely linked?
posted by mfbridges at 8:57 AM on January 13, 2004

I'm afraid I still don't understand.

I dont see why a computation has to be done at all when i visit a node.

When I first login to friendster it tells me i have X people in my network (say, 100,000)

I'm assuming that this is the hard part. The people in my network can be discovered by doing a search of my tree - my friends, my friends friends etc. Now you just have the problem of duplication - discovering someone far away that had a previous, closer, connection.

Anyways, once this structure is built, it seems to me that bringing up any profile just means doing a search on this table, finding the instance of that user and popping up the relationship. So the only db query required is a simple lookup.

likewise, searching profiles in my network is also no big deal - a search on a 100,00 row table.

what am i missing?
posted by vacapinta at 9:03 AM on January 13, 2004

This theory talk is all well and good, but it seems to be a more practical problem. I have friends-of-friends (two degrees away) whose profile I can't see. Unless it's a logic error that can't find the 1-1-1 connection and thinks it's further out...
posted by mkultra at 9:37 AM on January 13, 2004

Hmmm....joe, I think you are saying that friendster won't let me click on friend G while looking at friend F's profile because friend F is already 3 degrees away, and even if there is another connection it is too computationally complex to search for that connection. But if I am viewing friend C's profile I should be able to click on G because friend C is only 2 degrees away. This doesn't appear to be the actual behavior of friendster.

First, friendster does show multiple routes to a friend when viewing a profile, so it appears that it does do that computationally intensive search. Also, this wouldn't explain second-degree friends being un-clickable. Also, I generally find that if I can't click on someone from one person's profile, I also cannot click on them from another person's profile.

Since the link calculation is computationally expensive, maybe friendster does their processing offline and caches the results (vacapinta, it seems you are suggesting this is what they do). So, when I can't click on someone it might be because the route calculation hasn't been done yet (it knows that I am connected to the other person, but it doesn't know all the routes, so it doesn't let me look yet). And when the calculation finally is gotten around to, you are able to click on those friends (this would explain the phenomenon pointed out by hackworth). This seems kind of silly...not letting me look because it doesn't know all the routes yet. Ah well, too much time has yet been wasted.
posted by mfbridges at 9:49 AM on January 13, 2004

vacapinta: When I first login to friendster it tells me i have X people in my network (say, 100,000)

I don't think that number is actually calculated real-time in the friendster implementation. I would imagine that it calculates the total number in each person's network on a regular basis (weekly, perhaps?) and then uses this static value every time you log in. There are other ways to approximate it, but I am pretty sure that friendster doesn't count all of the friends of friends every time you log in.

likewise, searching profiles in my network is also no big deal - a search on a 100,00 row table.

That would be true if friendster didn't have to present all of your individual connections to a person when you view their profile. The network is constantly evolving, so you are not really searching a 100,000 row table, but a set of connections between them that is mutable.

mkultra: This theory talk is all well and good, but it seems to be a more practical problem. I have friends-of-friends (two degrees away) whose profile I can't see.

I've seen this too, and my guess is that the friendster server has temporarily limited the friend levels to 1. Thus you can only browse your direct friends. You'll notice at the same time you can't load up the 'gallery' (really just a user search) function when this state is occuring. Either they shut it off because the server is overloaded, they are having problems with it, or they are updating the static estimates for individuals.

This is generally at peak times of usage, and I've found that if you try again a few hours later it will typically work. Sometimes it vacillates while I'm using the service; (ie a person appears clickable, but when I click on them it says that a connection is not available). This is, incidentally, one of the main reasons that people are abandoning friendster for myspace.com.

mfbridges: Since the link calculation is computationally expensive, maybe friendster does their processing offline and caches the results

That's what I believe the problem is. Friendster appears to have a rough idea how many people are in your network, but if its connection engine is presently shut down for whatever reason, it will not allow you to browse this network because it needs to know all the specific connections (which is, of course, the whole point of the service).
posted by toothless joe at 10:24 AM on January 13, 2004

I've seen this too, and my guess is that the friendster server has temporarily limited the friend levels to 1.

Only some of the second-degree friends are unable to be clicked upon. There are some second-degree friends that are browsable, yet others remain obscured.
posted by mfbridges at 11:40 AM on January 13, 2004