A Diffusion Model with Constant Source and Sinks for Social Graph Partitioning

Abstract

Social services are more and more popular with the development of web and mobile internet. Behind social services, graph model is the key data structure representing the relationship among social entities. Partitioning social graphs according to graph connectivity is an important technique for the competency of social services including parallel computing, scalability, and analytics. This paper proposes a novel diffusion based approach for partitioning social graphs. A brand-new Random Walks model with Constant Source and Sink nodes (RWCSS) is devised to analogize a dynamic balanced diffusion procedure on graphs. The stationary state of RWCSS provides the closeness measurement between nodes which can serve as an effective global estimation for partitioning. Through incorporating the RWCSS model into the Bubble Framework, an efficient graph partitioning algorithm (Bubble-RWCSS) is implemented in a way gradually improving the partitioning quality with global consideration in each iteration. The evaluation on public well-known social graphs demonstrates the promising performance of the proposed method.