Wednesday, December 18, 2013

Graph Partitioning - Dividing a Social Network

If you have a social network where all the people can't fit on one server, a natural question that comes up is how to split up users across machines. There are two main factors to consider:

  1. For each user, what fraction of their friends stay on the same server. 
  2. Are people evenly distributed between servers. 
It's easy to see how these two factors can be in conflict. Trivially all users could be put on just one server, perfectly satisfying the first constraint while soundly failing the second. On the other hand, if we just assigned people randomly to 10 servers, then on average 90% of friendships would span servers. If everyone is friends with everyone else, we can do no better than this 90%. However, in most social networks people tend to form little well connected clusters, allowing for far better partitions.

Read more here

Leave a Reply

All Tech News IN © 2011 & Main Blogger .