Multi-level spectral graph partitioning method

Basit Öğe Kaydı
dc.authoridTalu, Muhammed Fatih/0000-0003-1166-8404
dc.authorwosidTalu, Muhammed Fatih/W-2834-2017
dc.contributor.authorTalu, Muhammed Fatih
dc.date.accessioned2024-08-04T20:44:05Z
dc.date.available2024-08-04T20:44:05Z
dc.date.issued2017
dc.departmentİnönü Üniversitesien_US
dc.description.abstractIn 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.en_US
dc.description.sponsorshipScientific and Technological Research Council of Turkey (TUBITAK) [215E075]en_US
dc.description.sponsorshipThis work was supported by the Scientific and Technological Research Council of Turkey (TUBITAK-grant no: 215E075).en_US
dc.identifier.doi10.1088/1742-5468/aa85ba
dc.identifier.issn1742-5468
dc.identifier.scopus2-s2.0-85032280754en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.urihttps://doi.org/10.1088/1742-5468/aa85ba
dc.identifier.urihttps://hdl.handle.net/11616/98008
dc.identifier.wosWOS:000411925200002en_US
dc.identifier.wosqualityQ1en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherIop Publishing Ltden_US
dc.relation.ispartofJournal of Statistical Mechanics-Theory and Experimenten_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectrandom graphsen_US
dc.subjectnetworksen_US
dc.subjectclustering techniquesen_US
dc.subjectheuristics algorithmsen_US
dc.titleMulti-level spectral graph partitioning methoden_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu