2014/10/22 by Jérôme Kunegis
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Adjacency list #Adjacency matrix #Algebraic graph theory #Algebraic number #Bioinformatics and Genomic Networks #Bipartite graph #Categorical variable #Combinatorics #Complex Network Analysis Techniques #Computer science #Graph #Graph theory #Graph theory and applications #Mathematics #Node (physics) #Theoretical computer science #cs.DM #cs.SI
paper · pdf · doi:10.1080/15427951.2014.958250
37 pages; fixed references
openalex publication_date 2014/10/22 · arxiv created 2015/01/15 · arxiv updated 2015/01/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
**Abstract** In this article, we extend several algebraic graph analysis methods to bipartite networks. In various areas of science, engineering, and commerce, many types of information can be represented as networks, and thus, the discipline of network analysis plays an important role in these domains. A powerful and widespread class of network analysis methods is based on algebraic graph theory, i.e., representing graphs as square adjacency matrices. However, many networks are of a very specific form that clashes with that representation: they are bipartite. That is, they consist of two node types, with each edge connecting a node of one type with a node of the other type. Examples of bipartite networks (also called two-mode networks_) are persons and the social groups they belong to, musical artists and the musical genres they play, and text documents and the words they contain. In fact, any type of feature that can be represented by a categorical variable can be interpreted as a bipartite network. Although bipartite networks are widespread, most literature in the area of network analysis focuses on unipartite networks, i.e., those networks with only a single type of node. The purpose of this article is to extend a selection of important algebraic network analysis methods to bipartite networks, showing that many methods from algebraic graph theory can be applied to bipartite networks, with only minor modifications. We show methods for clustering, visualization, and link prediction. Additionally, we introduce new algebraic methods for measuring the bipartivity in near-bipartite graphs.