DocumentCode :
3718883
Title :
Balanced Graph Partitioning: Optimizing graph cut based on Label Swapping
Author :
Huajian Zhang
Author_Institution :
College of Internet of Things, Nanjing University of Post and Telecoms, Jiangsu 210003, China
fYear :
2015
Firstpage :
184
Lastpage :
187
Abstract :
Balanced Graph Partitioning is one of the fundamental combinatorial optimization problems. It is still a challenge to effectively achieve a High-quality Balanced Graph Partitioning for super-large graphs. In this paper, we propose a graph partitioning algorithm based on Label Swapping. Normalized Cut is used as optimization target and this algorithm iteratively updates the graph with Label Swapping. Specifically, by using sampling methods, our method can deal with super-large graph and increase the algorithm´s efficiency. To improve the partition´s quality, we further propose a variable neighborhood search(VNS) in our algorithm to escape the local optimum. Our experimental results on real-world datasets have shown that the partition´s intra-cluster density is very good and and our algorithm outperforms METIS in term of minimum cut.
Keywords :
"Partitioning algorithms","Multiprotocol label switching","Economics","Optimization","Clustering algorithms","Approximation algorithms","Benchmark testing"
Publisher :
ieee
Conference_Titel :
Behavioral, Economic and Socio-cultural Computing (BESC), 2015 International Conference on
Type :
conf
DOI :
10.1109/BESC.2015.7365980
Filename :
7365980
Link To Document :
بازگشت