About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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.