Comparison between combinatorial and spectral approaches in identifying the largest bipartite subgraphs of a graph
Date:
Abstract
In this work, we compare the performances between a combinatorial approach by Erdös [1] and approaches based on the non-zero entries of eigenvectors corresponding to the extremal eigenvalues of four different matrices: adjacency, Laplacian, normalized Laplacian and signless Laplacian matrix, in identifying the largest bipartite subgraphs of a simple connected graph. We employ these approaches to one scale-free and three random graph models, which cover a wide range of real-world networks. It is observed that the normalized Laplacian and the adjacency matrix based approaches yield slightly better but comparable results to that of the combinatorial approach. Using these two matrices, we subsequently formulate a new index, analogous to the edge bipartivity index of Estrada and Rodríguez-Velázquez [2]. Our results indicate that the application of this new index not only significantly outperforms combinatorial approach but also performs better than the edge bipartivity index in identifying the largest bipartite subgraphs.
Keywords: Bipartite subgraphs, Edge bipartivity, Combinatorial approach for bi- partition, Spectral approach for bipartition.
References:
[1] P. Erdös, “On some extremal problems in graph theory”, Israel Journal of Mathematics 3 (2) (1965) 113–116.
[2] E. Estrada, J. A. Rodríguez-Velázquez, “Spectral measures of bipartivity in complex networks”, Physical Review E 72 (4) (2005) 046105.