SOCIOPART:Hopping Based Partitions

Online social networking has become a phenomenon in the last few years. The growing usage of social networks has put the vendors under a lot of pressure to efficiently pro-cess the users queries. In social networks like orkut, most of the queries access the immediate neighbors of the current node and neighbors of its neighbors. Existing graph parti-tioning approaches focus on reducing the number of inter server links, neglecting the query patterns. Our algorithm focuses on partitioning the graph so as to minimize the num-ber of servers to be accessed in order to process a query. Our results show that the proposed algorithm gives useful par-titioning of social networks, thereby reducing inter server accesses. 1