Best paper award for balanced graph partitioning
Published Oct 16, 2013
In september, Fatemeh Rahimian went to Philadelphia to take part in the 7th IEEE International Conference on Self-Adaptive and Self-Organizing Systems. There, her paper about a distributed algorithm for balanced graph partitioning was chosen for the best paper award.
Tell us about the paper and the subject.
– The paper proposes a distributed algorithm for balanced graph partitioning. Graphs are everywhere nowadays, from social networks to biological information. With the everincreasing size of the graphs, it is inevitable to partition them into several smaller clusters, which can be managed more easily on multiple machines. But finding a good partitioning is an NP-Complete problem. In our paper we propose a heuristic-based algorithm which can efficiently partition big graphs into a given number of clusters of equal size.
Why do you think that you got the best paper award?
– I think for two main reasons: simplicity and clarity. The idea that we used to solve the problem at hand, is very intuitive. We tried to keep it as simple as possible, so that the algorithm can be easily adopted by many realistic applications. Also, we allotted a significant amount of time for writing this paper in a well-structured and readable fashion. I think a very nice teamwork helped us a lot to get to this end and for that I'm very grateful to the co-authors.
What does it mean to you to get this award?
– I think this will give our work more visibility. This is important, because, I strongly believe our algorithm can be effectively utilized in many different domains. And of course more visibility gives it more chance to be put to use, I'd be very happy to see that happening.