Multi-level spectral graph partitioning method
Küçük Resim Yok
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Iop Publishing Ltd
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
In this article, a new method for multi-level and balanced division of non-directional graphs (MSGP) is introduced. Using the eigenvectors of the Laplacian matrix of graphs, the method has a spectral approach which has superiority over local methods (Kernighan-Lin and Fiduccia-Mattheyses) with a global division ability. Bisection, which is a spectral method, can divide the graph by using the Fiedler vector, while the recursive version of this method can divide into multiple levels. However, the spectral methods have two disadvantages: (1) high processing costs; (2) dividing the sub-graphs independently. With a better understanding of the eigenvectors of the whole graph, and by discovering the confidential information owned, MSGP can divide the graphs into balanced and multi-leveled without recursive processing. Inspired by Haar wavelets, it uses the eigenvectors with a binary heap tree. The comparison results in seven existing methods (some are community detection algorithms) on regular and irregular graphs which clearly demonstrate that MSGP works about 14,4 times faster than the others to produce a proper partitioning result.
Açıklama
Anahtar Kelimeler
random graphs, networks, clustering techniques, heuristics algorithms
Kaynak
Journal of Statistical Mechanics-Theory and Experiment
WoS Q Değeri
Q1
Scopus Q Değeri
Q2
