Relations between discrete quantities such as people, genes, or streets can be described by networks, which consist of nodes that are connected by edges. Network analysis aims to identify important nodes in a network and to uncover structural properties of a network. A network is said to be bipartite if its nodes can be subdivided into two nonempty sets such that there are no edges between nodes in the same set. It is a difficult task to determine the closest bipartite network to a given network. This paper describes how a given network can be approximated by a bipartite one by solving a sequence of fairly simple optimization problems. The algorithm also produces a node permutation which makes the possible bipartite nature of the initial adjacency matrix evident, and identifies the two sets of nodes. We finally show how the same procedure can be used to detect the presence of a large anti-community in a network and to identify it.

A spectral method for bipartizing a network and detecting a large anti-community / Concas, A.; Noschese, S.; Reichel, L.; Rodriguez, G.. - In: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS. - ISSN 0377-0427. - 373:(2020). [10.1016/j.cam.2019.06.022]

A spectral method for bipartizing a network and detecting a large anti-community

Abstract

Relations between discrete quantities such as people, genes, or streets can be described by networks, which consist of nodes that are connected by edges. Network analysis aims to identify important nodes in a network and to uncover structural properties of a network. A network is said to be bipartite if its nodes can be subdivided into two nonempty sets such that there are no edges between nodes in the same set. It is a difficult task to determine the closest bipartite network to a given network. This paper describes how a given network can be approximated by a bipartite one by solving a sequence of fairly simple optimization problems. The algorithm also produces a node permutation which makes the possible bipartite nature of the initial adjacency matrix evident, and identifies the two sets of nodes. We finally show how the same procedure can be used to detect the presence of a large anti-community in a network and to identify it.
Scheda breve Scheda completa
2020
Anti-community; bipartization; network analysis; network approximation
01 Pubblicazione su rivista::01a Articolo in rivista
A spectral method for bipartizing a network and detecting a large anti-community / Concas, A.; Noschese, S.; Reichel, L.; Rodriguez, G.. - In: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS. - ISSN 0377-0427. - 373:(2020). [10.1016/j.cam.2019.06.022]
File allegati a questo prodotto
File
Concas_A spectral method_2020.pdf

solo gestori archivio

Note: Concas_Spectral-method_2020
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Dimensione 1.63 MB
Concas_Spectral-method_post_2020.pdf

accesso aperto

Note: Concas_Spectral-method_2020
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Creative commons
Dimensione 4.75 MB