Pattern detection in bipartite networks: a review of terminology, applications and methods
arXiv:2310.01284 · doi:10.1371/journal.pcsy.0000010
Abstract
Two dimensional matrices with binary (0/1) entries are a common data structure in many research fields. Examples include ecology, economics, mathematics, physics, psychometrics and others. Because the columns and rows of these matrices represent distinct entities, they can equivalently be expressed as a pair of bipartite networks that are linked by projection. A variety of diversity statistics and network metrics can then be used to quantify patterns in these matrices and networks. But what should these patterns be compared to? In all of these disciplines, researchers have recognized the necessity of comparing an empirical matrix to a benchmark set of "null" matrices created by randomizing certain elements of the original data. This common need has nevertheless promoted the independent development of methodologies by researchers who come from different backgrounds and use different terminology. Here, we provide a multidisciplinary review of randomization techniques for matrices representing binary, bipartite networks. We aim to translate the concepts from different technical domains into a common language that is accessible to a broad scientific audience. Specifically, after briefly reviewing examples of binary matrix structures across different fields, we introduce the major approaches and common strategies for randomizing these matrices. We then explore the details of and performance of specific techniques, and discuss their limitations and computational challenges. In particular, we focus on the conceptual importance and implementation of structural constraints on the randomization, such as preserving row or columns sums of the original matrix in each of the randomized matrices. Our review serves both as a guide for empiricists in different disciplines, as well as a reference point for researchers working on theoretical and methodological developments in matrix randomization methods.
References in corpus (39)
- The Building Blocks of Economic Complexity
- Specificity and stability in topology of protein networks
- The Product Space Conditions the Development of Nations
- Why social networks are different from other types of networks
- Modularity and community detection in bipartite networks
- The Statistical Physics of Real-World Networks
- Pattern Detection in Complex Networks: Correlation Profile of the Internet
- Bipartite Graphs as Models of Complex Networks
- The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
- Analytical maximum-likelihood method to detect patterns in real networks
- The clustering coefficient and community structure of bipartite networks
- A network analysis of countries' export flows: firm grounds for the building blocks of the economy
- Randomizing bipartite networks: the case of the World Trade Web
- Uncovering collective listening habits and music genres in bipartite networks
- Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
- Inferring monopartite projections of bipartite networks: an entropy-based approach
- Common neighbours and the local-community-paradigm for link prediction in bipartite networks
- Breaking of ensemble equivalence in networks
- Ranking species in mutualistic networks
- Unbiased sampling of network ensembles
- Breaking the spell of nestedness
- Constrained Markovian dynamics of random graphs
- Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
- Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks
- Brexit and bots: characterizing the behaviour of automated accounts on Twitter during the UK election
- Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
- Transitivity and degree assortativity explained: The bipartite structure of social networks
- Ensemble nonequivalence in random graphs with modular structure
- The ambiguity of nestedness under soft and hard constraints
- Strong ensemble nonequivalence in systems with local constraints
- Fluctuating ecological networks: a synthesis of maximum-entropy approaches for pattern detection and process inference
- Topological properties and organizing principles of semantic networks
- Structural measures of similarity and complementarity in complex networks
- Associative nature of event participation dynamics: a network theory approach
- Functional structure in production networks
- A unifying framework for fast randomization of ecological networks with fixed (node) degrees
- Entropy-based randomisation of rating networks
- From Ecology to Finance (and Back?): Recent Advancements in the Analysis of Bipartite Networks
- Inferring comparative advantage via entropy maximization