Authors: Paul, Debdas
Stevanović, Dragan 
Title: Eigenvector-based identification of bipartite subgraphs
Journal: Discrete Applied Mathematics
Volume: 269
First page: 146
Last page: 158
Issue Date: 30-Sep-2019
Rank: M22
ISSN: 0166-218X
DOI: 10.1016/j.dam.2019.03.028
We report our experiments on 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 these methods to a ‘local switching’ algorithm based on the proof of the Erdös’ 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, while yielding comparable results to the local switching algorithm, are still outperformed by it. 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, also yields comparable results to the local switching algorithm.
Keywords: Bipartite subgraphs | Complex networks | Eigenvectors
Publisher: Elsevier

Show full item record


checked on Jun 15, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.