- Journal Home
- Volume 18 - 2025
- Volume 17 - 2024
- Volume 16 - 2023
- Volume 15 - 2022
- Volume 14 - 2021
- Volume 13 - 2020
- Volume 12 - 2019
- Volume 11 - 2018
- Volume 10 - 2017
- Volume 9 - 2016
- Volume 8 - 2015
- Volume 7 - 2014
- Volume 6 - 2013
- Volume 5 - 2012
- Volume 4 - 2011
- Volume 3 - 2010
- Volume 2 - 2009
- Volume 1 - 2008
Numer. Math. Theor. Meth. Appl., 18 (2025), pp. 199-225.
Published online: 2025-04
Cited by
- BibTex
- RIS
- TXT
In this paper, we propose a novel algorithm for finding Cheeger cuts via 1-Laplacian of graphs. In [6], Chang introduced the theory of 1-Laplacian of graphs and built the connection between searching for the Cheeger cut of an undirected and unweighted graph and finding the first nonzero eigenvalue of 1-Laplacian, the latter of which is equivalent to solving a constrained non-convex optimization problem. We develop an alternating direction method of multipliers based algorithm to solve the optimization problem. We also prove that the generated sequence is bounded and it thus has a convergent subsequence. To find the goal optimal solution to the problem, we apply the proposed algorithm using different initial guesses and select the cut with the smallest cut value as the desired cut. Experimental results are presented for typical graphs, including Petersen’s graph and Cockroach graphs, and the well-known Zachary karate club graph.
}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.OA-2024-0051}, url = {http://global-sci.org/intro/article_detail/nmtma/23947.html} }In this paper, we propose a novel algorithm for finding Cheeger cuts via 1-Laplacian of graphs. In [6], Chang introduced the theory of 1-Laplacian of graphs and built the connection between searching for the Cheeger cut of an undirected and unweighted graph and finding the first nonzero eigenvalue of 1-Laplacian, the latter of which is equivalent to solving a constrained non-convex optimization problem. We develop an alternating direction method of multipliers based algorithm to solve the optimization problem. We also prove that the generated sequence is bounded and it thus has a convergent subsequence. To find the goal optimal solution to the problem, we apply the proposed algorithm using different initial guesses and select the cut with the smallest cut value as the desired cut. Experimental results are presented for typical graphs, including Petersen’s graph and Cockroach graphs, and the well-known Zachary karate club graph.