Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications

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 \emph{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.

arXiv comment37 pages; fixed references

References in corpus (15)

• Emergence of scaling in random networks
• Cooperative Game Theory Approaches for Network Partitioning
• Empirical Analysis of Predictive Algorithms for Collaborative Filtering
• The large-scale organization of metabolic networks
• Link Prediction in Complex Networks: A Survey
• The Web of Human Sexual Contacts
• The Slashdot Zoo: Mining a Social Network with Negative Edges
• Spectral Measures of Bipartivity in Complex Networks
• On network bipartivity
• Recommender System for Online Dating Service
• Empirical analysis of web-based user-object bipartite networks
• Complex network study of Brazilian soccer players
• Bipartite Producer-Consumer Networks and the Size Distribution of Firms
• Applications of Structural Balance in Signed Social Networks
• Collaborative filtering based on multi-channel diffusion

Cited by in corpus (6)

• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Functional structure in production networks
• On the Ubiquity of Web Tracking: Insights from a Billion-Page Web Crawl
• Pure Spectral Graph Embeddings: Reinterpreting Graph Convolution for Top-N Recommendation
• Centrosymmetric Stochastic Matrices
• Balance in Signed Bipartite Networks