| From its birth, online social network has maintained a rapid growthattracting a large number of users, developers and researchers. Over the pastten years, the scale of social network grow rapidly. With further increase ofusers, the single server cannot satisfy the demand of overall social network.Most social networks start distributing their data on server clusters.The communication between cluster nodes through network, usuallyrequires high network cost and leads to long access time. A large number ofremote accesses will lead to communication network congestion, whichbecomes the bottleneck of whole system. It also delays access time greatly,and degrades user experience. How to store and access user data effectivelywithin limited distributed storage has practical significance.Existing research shows that the majority of social network interactionsoccur between a small number of users, and most users only interact with fewfriends. There is a distinct community structure. Partitioning social networkproperly and reducing cut edges spanning different cluster nodes can reducenetwork traffic effectively. However, graph partition problem is aNP-complete problem. There is no linear time solution to find the optimalsolution.Based on these observations, a number of researchers makeimprovements to the existing graph partition algorithms according to thenetwork structure of social network. After studying the existing social network graph partitioning algorithms, this paper proposes a dynamicpartitioning and replication algorithm based on user interactions, whichdescribes community structure of social network by user relations andcomments. It partitions and replicates user data periodically, in order toimprove local access ratio and reduce network communication load. Throughexperiment on a real-world dataset, this paper proves that compared withrandom partitioning and replication, this algorithm could improve localaccess ratio greatly, and finally reduce access latency. |
PDF Full Text Request