  We report our experiments in identifying large bipartite subgraphs of simple
connected graphs which are based on the sign pattern of eigenvectors belonging
to the extremal eigenvalues of different graph matrices: adjacency, signless
Laplacian, Laplacian, and normalized Laplacian matrix. We compare the
performance of these methods to a local switching algorithm based on the Erdos
bound that each graph contains a bipartite subgraph with at least half of its
edges. Experiments with one scale-free and three random graph models, which
cover a wide range of real-world networks, show that the methods based on the
eigenvectors of the normalized Laplacian and the adjacency matrix yield
slightly better, but comparable results to the local switching algorithm. We
also formulate two edge bipartivity indices based on the former eigenvectors,
and observe that the method of iterative removal of edges with maximum
bipartivity index until one obtains a bipartite subgraph, yields comparable
results to the local switching algorithm, and significantly better results than
an analogous method that employs the edge bipartivity index of Estrada and
Gomez-Gardenes.
