English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Eigenvector-based identification of bipartite subgraphs.

Paul, D., & Stevanovic, D. (2019). Eigenvector-based identification of bipartite subgraphs. Discrete Applied Mathematics, 269, 146-158. doi:10.1016/j.dam.2019.03.028.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0005-2087-E Version Permalink: http://hdl.handle.net/21.11116/0000-0005-2089-C
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Paul, D.1, Author              
Stevanovic, D., Author
Affiliations:
1Research Group of Quantitative and System Biology, MPI for Biophysical Chemistry, Max Planck Society, ou_2466694              

Content

show
hide
Free keywords: Bipartite subgraphs; Eigenvectors; Complex networks
 Abstract: 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 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, 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.

Details

show
hide
Language(s): eng - English
 Dates: 2019-04-172019-09-30
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: Peer
 Identifiers: DOI: 10.1016/j.dam.2019.03.028
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Discrete Applied Mathematics
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 269 Sequence Number: - Start / End Page: 146 - 158 Identifier: -