Social networking has been one of the fastest growing information technologies as evidenced by the popularity of online social network (OSN) sites. These highly active OSNs generate an enormous volume of data as well as work load every day. A cost-effective solution is horizontal scaling where an OSN is partitioned and deployed on a set of low-cost servers. The goal of the paper is to achieve an optimal partitioning by minimizing the overall cost (sum of the inter-server write traffic cost and moving cost) while maintaining a load balance across servers. Given the NP-hardness of the problem, we introduce a deep learning based model for incremental online learning and dynamic link prediction. We then propose a Dynamic Link Prediction based online algorithm named FLOAT that incorporates the predicted future link information into the online user assignment. Relying upon future and current link based node relocation/swap gain estimations (Adjusted Server Change Benefit (ASCB) and Adjusted Server Exchange Benefit (ASXB), FLOAT strategically assigns user nodes across servers. The simulation results confirm that a projected benefit based on the knowledge of future links help reduce the overall cost significantly compared with existing algorithms, at the same time, maintaining a low inter-server write traffic cost.

With the remarkable proliferation of intelligent mobile devices and fast growing broadband wireless technology, social networking is undergoing explosive growth in recent years as more and more users access social networks via mobile platforms. It is often expensive or even impossible to deploy a large online social network (OSN) on a single server. A cost-effective approach is horizontal scaling, where the OSN is partitioned and deployed on a set of low-cost servers. In this research, we study the problem of minimum-cost balanced partitioning of OSNs. Our goal is to achieve the best partitioning by minimizing the total inter-server traffic cost and at the same time balancing the load among servers. Given its NP-hardness, we propose new techniques and explore efficient heuristics to address the problem, especially for extremely large OSNs with an enormous volume of social nodes, social connections, and social data. Our key contributions include a localized approach with O(δ2) complexity to explicitly calculate the projected gain in inter-server traffic cost (named Server Change Benefit (SCB)). Built upon this technique, we devise two algorithms that offer online and offline solutions to achieving minimum-cost balanced partitioning of OSNs. The online algorithm is fast and highly efficient to process newly arrival individual nodes. The offline algorithm uses the current online result as a starting point. It further reduces inter-server traffic cost by applying relocation and swapping. It employs a merging process to group the nodes according to the social structure and swap the groups with similar size to further reduce the total inter-server traffic cost. We implement both algorithms and evaluate them based on a variety of real-world OSN datasets from Facebook, Arxiv, Gnutella, Amazon, and Twitter. The simulations demonstrate that the proposed algorithms can significantly reduce the execution time by an average of three folds and at the same time yield supreme performance (i.e., inter-server traffic cost) in comparison with existing solutions.