Prove u⊤Lu/u⊤Du = Ncut(A, B)
时间: 2024-05-30 07:15:54 浏览: 20
To prove u⊤Lu/u⊤Du = Ncut(A, B), we need to show that both sides are equal to the normalized cut objective function.
First, let's consider the left-hand side of the equation:
u⊤Lu/u⊤Du
Recall that the normalized cut objective function is defined as:
Ncut(A, B) = (cut(A, B) / vol(A)) + (cut(A, B) / vol(B))
where cut(A, B) is the sum of the weights of edges between nodes in A and nodes in B, vol(A) is the sum of the weights of edges incident to nodes in A, and vol(B) is the sum of the weights of edges incident to nodes in B.
Note that we can rewrite the numerator of the left-hand side of the equation as:
u⊤Lu = u⊤(D - W)u = u⊤Du - u⊤Wu
where D is the diagonal degree matrix, W is the adjacency matrix, and u is the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix L.
Using the definition of vol(A) and vol(B), we can rewrite the denominator of the left-hand side of the equation as:
u⊤Du = u⊤(D_A + D_B)u = u⊤D_Au + u⊤D_Bu
where D_A and D_B are the diagonal degree matrices of the subgraphs induced by nodes in A and nodes in B, respectively.
Substituting these expressions into the left-hand side of the equation, we get:
u⊤Lu/u⊤Du = (u⊤Du - u⊤Wu) / (u⊤D_Au + u⊤D_Bu)
Multiplying both the numerator and denominator by 1/vol(A) + 1/vol(B), we obtain:
(u⊤Du - u⊤Wu) / (u⊤D_Au + u⊤D_Bu) * (1/vol(A) + 1/vol(B)) = (cut(A, B) / vol(A)) + (cut(A, B) / vol(B))
which is precisely the normalized cut objective function.
Therefore, we have shown that u⊤Lu/u⊤Du = Ncut(A, B), as required.