Decentralized Graph Partitioning for Social Networks and Classification Systems

SeRC researchers have developed a novel decentralized method for partitioning of graphs, with applications in areas such as social networks and classification systems, that was awarded with best paper in the IEEE International Conference on Self-Adaptive and Self-Organizing Systems, 2013.

Balanced graph partitioning is a well-known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems including the optimal storage of large sets of graph-structured data over several hosts: a key problem in data-centers and cloud computing environments. However, in very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. SeRC researchers have developed a fully distributed algorithm, called JA-BE-JA, that uses local search and simulated annealing techniques for graph partitioning. The algorithm is massively parallel: there is no central coordination, each node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known locally. Strict synchronization is not required. These features allow JA-BE-JA to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks.

References: 

• Rahimian, Fatemeh and Payberah, Amir H. and Girdzijauskas, Sarunas and Jelasity, Mark and Haridi, Seif, Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning, IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems (SASO), pgs 51-60, 1949-3673, 2013