I wonder if there is value to be had in migrating users to increase social graph locality. The probability of (B fr C) is greater than the mean if (A fr B) and

I wonder if there is value to be had in migrating users to increase social graph locality. The probability of (B fr C) is greater than the mean if (A fr B) and (A fr C). That's useful information. Off the top of my head, I wonder how an algorithm like: - I have N shards - pick the top N most-connected users - assign them each to a shard - assign their immediate friends to the same shard - randomly fill in other users would work. Possible refinements: - if the %age of shared friends between two users in the top N is > X, put both users in the same shard + add the N+1th user at a new shard-seed - chase more than one level of immediacy from the shard-seed users to fill the shard - if a shard is full, don't drop to random allocation for 1st- or 2nd- level friends, but instead put them all onto shard+1 The idea here is that for pull or push you win if you need to contact fewer shards. i.e. the queries and updates needn't be per-user but per-shard. i.e. you can query/update for all users on a shard in one sql statement. If you somehow manage to keep all of ashton's friends on 10 shards instead of 100, then that's a big win, surely?