  For a given graph, $G$, let $A$ be the adjacency matrix, $D$ is the diagonal
matrix of degrees, $L' = D - A$ is the combinatorial Laplacian, and $L =
D^{-1/2}L'D^{-1/2}$ is the normalized Laplacian. Recently, the eigenvectors
corresponding to the smallest eigenvalues of $L$ and $L'$ have been of great
interest because of their application to community detection, which is a
nebulously defined problem that essentially seeks to find a vertex set $S$ such
that there are few edges incident with exactly one vertex of $S$. The
connection between community detection and the second smallest eigenvalue (and
the corresponding eigenvector) is well-known. The $k$ smallest eigenvalues have
been used heuristically to find multiple communities in the same graph, and a
justification with theoretical rigor for the use of $k \geq 3$ eigenpairs has
only been found very recently.
  The largest eigenpair of $L$ has been used more classically to solve the
MAX-CUT problem, which seeks to find a vertex set $S$ that maximizes the number
of edges incident with exactly one vertex of $S$. Very recently Trevisan
presented a connection between the largest eigenvalue of $L$ and a recursive
approach to the MAX-CUT problem that seeks to find a "bipartite community" at
each stage. This is related to Kleinberg's HITS algorithm that finds the
largest eigenvalue of $A^TA$. We will provide a justification with theoretical
rigor for looking at the $k$ largest eigenvalues of $L$ to find multiple
bipartite communities in the same graph, and then provide a heuristic algorithm
to find strong bipartite communities that is based on the intuition developed
by the theoretical methods. Finally, we will present the results of applying
our algorithm to various data-mining problems.
