Fatemeh Rahimian gives a seminar on her Best Paper awarded research.

Fatemeh Rahimian will give a talk on her recent paper "JA-BE-JA: A Distributed Algorithm for Balanced Graph Partitioning" which got the best paper award in SASO 2013. She will also give an overview of her latest research activity on distributed community detection for solving cross-document coreference resolution problems.


Balanced graph partitioning is a well known NPcomplete 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 today’s Cloud infrastructure. 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. In this paper, we propose 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. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by JA-BE-JA is comparable to state-of-the-art centralized algorithms such as METIS. In particular, on large social networks JA-BEJA outperforms METIS, which makes JA-BE-JA—a bottomup, self-organizing algorithm—a highly competitive practical solution for graph partitioning.

Awarded paper: JA-BE-JA: A Distributed Algorithm for Balanced Graph Partitioning

Wednesday, December 4, 2013, 10:00 to 12:00
SICS, room Knuth
Isafjordsgatan 22