Link Prediction Based Minimum Cost and Balanced Partition of Large Online Social Networks
Romas James Hada, Miao Jin, Ying Xie, Linh Le · 2019
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.