{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T20:51:16Z","timestamp":1740171076654,"version":"3.37.3"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T00:00:00Z","timestamp":1689033600000},"content-version":"vor","delay-in-days":18,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,23]]},"abstract":"Abstract<\/jats:title>\n 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.<\/jats:p>","DOI":"10.1093\/comnet\/cnad026","type":"journal-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:22:42Z","timestamp":1689121362000},"source":"Crossref","is-referenced-by-count":0,"title":["Spectral techniques for measuring bipartivity and producing partitions"],"prefix":"10.1093","volume":"11","author":[{"given":"Azhar","family":"Aleidan","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Strathclyde , Richmond Street, Glasgow G1 1XH, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9511-5692","authenticated-orcid":false,"given":"Philip A","family":"Knight","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Strathclyde , Richmond Street, Glasgow G1 1XH, UK"}]}],"member":"286","published-online":{"date-parts":[[2023,7,11]]},"reference":[{"key":"2024021718411348200_cnad026-B1","doi-asserted-by":"crossref","first-page":"046105","DOI":"10.1103\/PhysRevE.72.046105","article-title":"Spectral measures of bipartivity in complex networks","volume":"72","author":"Estrada","year":"2005","journal-title":"Phys. Rev. E"},{"key":"2024021718411348200_cnad026-B2","doi-asserted-by":"crossref","first-page":"056107","DOI":"10.1103\/PhysRevE.68.056107","article-title":"Network bipartivity","volume":"68","author":"Holme","year":"2003","journal-title":"Phys. Rev. E"},{"key":"2024021718411348200_cnad026-B3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1080\/15427951.2014.958250","article-title":"Exploiting the structure of bipartite graphs for algebraic and spectral graph theory applications","volume":"11","author":"Kunegis","year":"2015","journal-title":"Internet Math"},{"key":"2024021718411348200_cnad026-B4","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1016\/j.dam.2006.12.003","article-title":"Computing the bipartite edge frustration of fullerene graphs","volume":"155","author":"Do\u0161li\u0107","year":"2007","journal-title":"Discrete Appl. Math"},{"key":"2024021718411348200_cnad026-B5","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.physd.2015.10.020","article-title":"Network bipartivity and the transportation efficiency of European passenger airlines","volume":"323","author":"Estrada","year":"2016","journal-title":"Physica D"},{"key":"2024021718411348200_cnad026-B6","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","article-title":"On modularity clustering","volume":"20","author":"Brandes","year":"2007","journal-title":"IEEE Trans. Knowledge Data En"},{"key":"2024021718411348200_cnad026-B7","doi-asserted-by":"crossref","first-page":"3018","DOI":"10.1016\/j.laa.2010.01.005","article-title":"On conjectures involving second largest signless Laplacian eigenvalue of graphs","volume":"432","author":"Das","year":"2010","journal-title":"Linear Algebra Appl"},{"key":"2024021718411348200_cnad026-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2298\/AADM110205006K","article-title":"Bipartite subgraphs and the signless Laplacian matrix","volume":"5","author":"Kirkland","year":"2011","journal-title":"Appl. Anal. Discrete Math"},{"volume-title":"A First Course in Network Theory","year":"2015","author":"Estrada","key":"2024021718411348200_cnad026-B9"},{"key":"2024021718411348200_cnad026-B10","doi-asserted-by":"crossref","first-page":"112306","DOI":"10.1016\/j.cam.2019.06.022","article-title":"A spectral method for bipartizing a network and detecting a large anti-community","volume":"373","author":"Concas","year":"2020","journal-title":"J. Comput. Appl. Math"},{"key":"2024021718411348200_cnad026-B11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921681","volume-title":"Graph Spectra for Complex Networks","author":"Van Mieghem","year":"2010"},{"volume-title":"The Structure of Complex Networks: Theory and Applications","year":"2012","author":"Estrada","key":"2024021718411348200_cnad026-B12"},{"key":"2024021718411348200_cnad026-B13","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2024021718411348200_cnad026-B14","doi-asserted-by":"crossref","first-page":"2012","DOI":"10.1093\/bioinformatics\/btl338","article-title":"A lock-and-key model for protein\u2013protein interactions","volume":"22","author":"Morrison","year":"2006","journal-title":"Bioinformatics"},{"key":"2024021718411348200_cnad026-B15","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/j.dam.2019.03.028","article-title":"Eigenvector-based identification of bipartite subgraphs","volume":"269","author":"Paul","year":"2019","journal-title":"Discrete Appl. Math"},{"key":"2024021718411348200_cnad026-B16","doi-asserted-by":"crossref","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","article-title":"A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory","volume":"25","author":"Fiedler","year":"1975","journal-title":"Czech. Math. J"},{"key":"2024021718411348200_cnad026-B17","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.3934\/math.2021070","article-title":"Network bipartitioning in the anti-communicability Euclidean space","volume":"6","author":"G\u00f3mez-Garde\u00f1es","year":"2021","journal-title":"AIMS Math"},{"key":"2024021718411348200_cnad026-B18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","article-title":"An efficient heuristic procedure for partitioning graphs","volume":"49","author":"Kernighan","year":"1970","journal-title":"Bell Sys. Techn. J"},{"key":"2024021718411348200_cnad026-B19","first-page":"742","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","author":"Pr\u00fcfer","year":"1918","journal-title":"Arch. Math. Phys"},{"key":"2024021718411348200_cnad026-B20","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1046\/j.1461-0248.1998.00039.x","article-title":"Disturbance, resource supply, and food-web architecture in streams","volume":"1","author":"Thompson","year":"1998","journal-title":"Ecol. Lett"},{"first-page":"1929","year":"1989","author":"Brglez","key":"2024021718411348200_cnad026-B21"},{"volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","year":"1993","author":"Knuth","key":"2024021718411348200_cnad026-B22"},{"year":"2023","author":"Aleidan","key":"2024021718411348200_cnad026-B23"},{"key":"2024021718411348200_cnad026-B24","doi-asserted-by":"crossref","first-page":"9564","DOI":"10.1073\/pnas.0610537104","article-title":"Mixture models and exploratory analysis in networks","volume":"104","author":"Newman","year":"2007","journal-title":"Proc. Natl. Acad. Sci., USA"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/4\/cnad026\/56697687\/cnad026.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/4\/cnad026\/56697687\/cnad026.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T18:41:27Z","timestamp":1708195287000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnad026\/7222898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,23]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,6,23]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnad026","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2023,8,1]]},"published":{"date-parts":[[2023,6,23]]}}}