- You must login in order to post into this group.
Decentralized Graph Partitioning for Social Networks and Classification Systems
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.
• 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