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

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:373

Article; Proceedings Paper

Concas, A.¹  Noschese, S.²  Reichel, L.³  Rodriguez, G.¹ 

[1] Univ Cagliari, Dept Math & Comp Sci, Viale Merello 92, I-09123 Cagliari, Italy

[2] Sapienza Univ Rome, Dept Math Guido Castelnuovo, Ple A Moro 2, I-00185 Rome, Italy

[3] Kent State Univ, Dept Math Sci, Kent, OH 44242 USA

关键词: Network analysis;    Network approximation;    Bipartization;    Anti-community;   

DOI  :  10.1016/j.cam.2019.06.022

来源: Elsevier

【 摘 要 】

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. (C) 2019 Elsevier B.V. All rights reserved.

【 授权许可】

Free