I'd be curious to see if Facebook and the rest use similar strategies to reduce the intra-datacenter processing and bandwidth, and if the savings achieved are worth anything significant.
Yeah, I'd even be interested in knowing if Facebook breaks down their server costs to that level of detail, e.g., the operational cost of Algorithm A versus Algorithm B.
Since capital expenditures seems to be a big part of their costs they might just be that detailed.
What does that greedy algorithm work on, given that Facebook doesn't allow you to store a copy of the friend graph? At the point of notification, all you know is a list of user IDs that have your application, and possibly how many friends each one has.
Well, first, you can bend the rules. How does Facebook know whether you're storing the graph or not? They won't unless you violate the TOS in some other, more overt way.
Second, Facebook's rules say you can't store it for more than 24 hours. The current copy of the graph is available via API calls -- just call getFriends for each user with a valid session.
Third, if your app is big enough you can approximating it by seeing who sends notifications to whom, who clicks on newsfeed items, etc.
Fourth, although I used Facebook as an example, this applies to any social network with a notification mechanism. I just used Facebook because it's easier to understand -- they limit the number of notifications at the API level.
one reason facebook is so viral is that it largely implements this naturally by its decomposition. that is, randomly choose seeds within a dense section of the graph (an island, or in facebook lingo, a network). it will quickly spread to the whole island, and you can grow virally island by island. this is a decent approximation under certain assumptions to an optimal centrality metric.
