Spectral techniques for measuring bipartivity and producing partitions

Aleidan, Azhar and Knight, Philip A (2023) Spectral techniques for measuring bipartivity and producing partitions. Journal of Complex Networks, 11 (4). cnad026. ISSN 2051-1329 (https://doi.org/10.1093/comnet/cnad026)

[thumbnail of Aleidan-Knight-JCN-2023-Spectral-techniques-for-measuring-bipartivity]
Preview
 Text. Filename: Aleidan-Knight-JCN-2023-Spectral-techniques-for-measuring-bipartivity.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

Complex networks can often exhibit a high degree of bipartivity. There are many well-known ways for testing this, and in this article, we give a systematic analysis of characterizations based on the spectra of the adjacency matrix and various graph Laplacians. We show that measures based on these characterizations can be drastically different results and leads us to distinguish between local and global loss of bipartivity. We test several methods for finding approximate bipartitions based on analysing eigenvectors and show that several alternatives seem to work well (and can work better than more complex methods) when augmented with local improvement.

ORCID iDs

Aleidan, Azhar and Knight, Philip A ORCID logoORCID: https://orcid.org/0000-0001-9511-5692;
  • Item type:Article
    ID code:86380
    Dates:
    Date
    Event
    31 August 2023
    Published
    11 July 2023
    Published Online
    26 June 2023
    Accepted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:03 Aug 2023 11:28
    Last modified:11 Nov 2024 14:01
    URI:https://strathprints.strath.ac.uk/id/eprint/86380
CORE (COnnecting REpositories)