Year: 2025
Author: Wei Zhu
Numerical Mathematics: Theory, Methods and Applications, Vol. 18 (2025), Iss. 1 : pp. 199–225
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/nmtma.OA-2024-0051
Numerical Mathematics: Theory, Methods and Applications, Vol. 18 (2025), Iss. 1 : pp. 199–225
Published online: 2025-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 27
Keywords: Cheeger cuts 1-Laplacian of graphs alternating direction method of multipliers.