Source-linked AI summary
Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
Carsten F. Dormann, Rouven Strauss
TL;DR
Quantitative bipartite networks are informative ecological representations but lack suitable module-detection algorithms. The paper presents QuaBiMo, which computes modularity using link strengths in bipartite networks and identifies nested modules. The approach identified meaningful ecological modules in a preliminary frugivore-network analysis.
Problem
Existing module-detection algorithms do not accommodate quantitative bipartite networks, despite their use in ecological research.
Method
QuaBiMo extends hierarchical random graphs to compute modularity and detect nested modules in weighted bipartite networks.
Results
QuaBiMo identified meaningful ecological modules in a preliminary analysis of frugivore networks.
Takeaways & Limitations
Using link strengths makes the approach more sensitive and informative for weighted bipartite ecological networks.
Takeaways & Limitations
The reported classification accuracy suggests that larger modules might improve if more optimization steps were allowed before termination.
Abstract
from arXiv · showhide
Ecological networks are often composed of different sub-communities (often referred to as modules). Identifying such modules has the potential to develop a better understanding of the assembly of ecological communities and to investigate functional overlap or specialisation. The most informative form of networks are quantitative or weighted networks. Here we introduce an algorithm to identify modules in quantitative bipartite (or two-mode) networks. It is based on the hierarchical random graphs concept of Clauset et al. (2008 Nature 453: 98-101) and is extended to include quantitative information and adapted to work with bipartite graphs. We define the algorithm, which we call QuaBiMo, sketch its performance on simulated data and illustrate its potential usefulness with a case study.
Introduction
Ecological networks contain sub-communities, but existing module-detection algorithms do not accommodate quantitative bipartite networks. The paper introduces QuaBiMo to identify modules and nested modules in such networks.
- Existing approach: Module algorithms rearrange memberships and quantify modularity until a maximal degree of sorting is achieved.This greedy search is described as computationally intensive.
- Motivation: Weighted bipartite networks quantify interaction strengths between two groups whose members do not interact within groups.Pollinator–flower, host–parasitoid, and seed-dispersal networks are examples.
- Research gap: Existing module-detection algorithms primarily target unweighted one-mode networks or unweighted bipartite networks.Software often uses one-mode networks or projections of bipartite networks.
- Why the gap matters: The lack of an algorithm for quantitative bipartite networks is problematic because these networks inform conservation and macroecological research.Weighted networks also provide more information and may reduce erroneous conclusions compared with unweighted representations.
- Contribution: QuaBiMo identifies modules and modules within modules in weighted bipartite networks.The method builds on Clauset et al.’s algorithm for unweighted one-mode networks and extends it to quantitative bipartite graphs.
2 Modularity algorithms
Existing modularity methods largely target unweighted or one-mode networks, while weighted bipartite networks require an approach that preserves quantitative interactions and bipartite structure. QuaBiMo extends hierarchical random graphs to identify nested modules in such networks.
- Existing approaches and QuaBiMo: Correspondence analysis is simple and fast but may fail to identify modules even when they are perfectly separated; QuaBiMo can identify them in principle.Perfectly separated modules are called compartments and appear as clearly separated species groups.
- Existing approaches and QuaBiMo: Existing bipartite methods include projection into two one-mode networks, which prevents identification of combined modules.The Guimerà et al. approach identifies modules separately at the two network levels.
- QuaBiMo algorithm: QuaBiMo builds on hierarchical random graphs, representing species as dendrogram leaves and evaluating random branch swaps to optimize modularity.Simulated annealing sometimes accepts a worse graph to avoid local maxima, while dendrogram nodes encode module membership.
- QuaBiMo algorithm: The algorithm becomes quantitative by weighting branches with observed interaction numbers and bipartite by restricting interactions to the two non-overlapping network levels.Together, these modifications support module detection in weighted bipartite networks using a hierarchical representation of species link weights.
- Goal function: QuaBiMo defines modules as dendrogram subsets and labels a vertex as a module when observed within-module interaction weight exceeds its expected value.The expected matrix is based on marginal totals, and total modularity Q sums contributions across vertices and modules.
- Goal function: The modularity score Q ranges from 0, indicating no more within-module links than expected by chance, to 1, with higher values supporting a modular division.The algorithm assumes modules are connected subgraphs, each vertex belongs to exactly one module, and within-module edge weights exceed outside-module weights.
3 Evaluation of the algorithm
The QuaBiMo evaluation used simulated bipartite networks varying size, filling, modularisation, and noise. Performance depended on network size, noise, module number, and information type, with weighted data improving modularity detection over binary data but noise degrading accuracy.
- Simulation design: The simulations varied network size, module number, filling, and seven noise levels to evaluate QuaBiMo under controlled conditions.Networks measured 30 × 50 or 100 × 400, contained 3 or 10 modules, and used low or high filling.
- Simulation design: Simulated modules were generated as filled blocks, assigned skewed negative-binomial interaction weights, and then contaminated by moving interactions outside modules.Higher module filling generally improves performance, while noise makes modules less distinct.
- Limits: Theoretical and computational limits arise when between-module interactions approach within-module interactions, while larger networks may require more search steps.The study did not evaluate substantially larger networks, although the authors state there is no technical reason the algorithm should not work given sufficient computation.
- Modularity and accuracy: Modularity Q depended strongly on network size, added noise, and module number.The evaluation assessed congruence with the original module assignments using confusion-matrix measures including sensitivity, specificity, and accuracy.
- Modularity and accuracy: Weighted network data substantially improved modularity over binary data, particularly for large networks.The authors therefore focused subsequent analyses on weighted networks.
- Modularity and accuracy: Larger and noisier networks were more difficult to modularise, and increasing noise reduced overall accuracy, sensitivity, and specificity.The effect of noise on accuracy was more pronounced in large networks.
4 Identifying modules - an example session
The example session applies QuaBiMo to a quantitative pollination network, exposing computational settings, outputs, and interpretive limits.
- Inputs and settings: QuaBiMo’s main function accepts bipartite network data, a stopping-step setting, and an option for nested modules.The number of steps should be adapted to network size, while nested-module computation is controlled by “deep”.
- Computation and output: Q levels off soon after the default one million steps, but this setting was not extensively tested on larger networks.The resulting object stores module composition and solution likelihood, with Q equal to that likelihood.
- Example network: The example analyzes a 25 × 79, well-sampled pollination network from Memmott (1999).This network is used as a typical analysis example.
- Nested modules: Nested modules require lower-step recursive computation and can produce a different highest-level module structure.The non-recursive algorithm still determines the reported modularity value Q.
- Interpretation: Ecological interpretation of detected modules requires expert knowledge, so modularity is primarily an exploratory tool for noisy network data.The algorithm helps users objectively detect patterns, but the ecological causes of modules are not automatically established.
5 Modularity Q as a network index
This section presents modularity Q as an index related to specialization and uses species-level connectivity measures to characterize network roles.
- Q and specialization: Across 22 quantitative pollination networks, modularity Q was highly positively correlated with complementary specialization H′.The paper links this relationship to modules arising when species do not interact with some others.
- Caveats: The index Q depends on network size, species number, and link number, so absolute values require contextual interpretation.This dependence motivates comparison with null models rather than relying only on an unstandardized Q value.
- Null-model assessment: Observed modularity was 7 standard deviations above random networks with the same marginal totals.The null models preserve plant and pollinator abundance distributions; values above approximately 2 are considered significantly modular.
- Species roles: The c metric measures between-module connectivity and z measures within-module degree, both computed from link counts rather than interaction weights.Species exceeding c = 0.625 and z = 2.5 are classified as hubs under the cited thresholds.
- Species roles: Only Syritta pipiens exceeded both hub thresholds, while Leontodon hispidus nearly did and linked all modules except one.Syritta linked modules three, five, and six; Leontodon was a common plant visited by many pollinators.
- Species roles: Using null-model critical values would reclassify three additional pollinators as hub species.The pollinator thresholds were c = 0.67 ± 0.039 and z = 1.45 ± 0.220, while plant thresholds were c = 0.72 ± 0.036 and z = 1.78 ± 0.297.
Conclusion
The paper presents QuaBiMo as an algorithm for weighted bipartite networks and reports meaningful ecological modules in preliminary analyses.
- Contribution: QuaBiMo computes modularity Q and detects modules in weighted, bipartite networks.Its hierarchical representation supports module detection in this network class.
- Evidence: A preliminary analysis identified meaningful ecological modules in frugivore networks.This result is reported as an initial application of the approach.
- Implication: Using link strength as quantitative information is expected to make QuaBiMo more sensitive and specific than current binary algorithms.The comparison is stated as an expectation rather than a directly quantified result in the conclusion passage.
- Implication: The algorithm’s open availability is intended to support new insights into interaction-network structure.The conclusion frames accessibility as a way for network ecology to benefit from the method.
50–57. Elsevier, Amsterdam. 361
This section lists references covering ecological networks, modularity, specialization, null models, community detection, and related applications.
- Ecological networks: Several cited studies address modularity, compartmentalization, nestedness, and specialization in ecological interaction networks.The bibliography spans pollination, plant–animal, food-web, host–parasitoid, and mutualistic systems.
- Modularity and community detection: The references include foundational work on modularity and community detection in general and bipartite networks.Examples include Clauset et al., Barber, Guimerà et al., Newman, and Fortunato.
- Network analysis: The references also cover network indices, weighting, scale dependence, and null models for ecological-network analysis.These works provide methodological context for interpreting quantitative network structure.
Appendix A: Formal definition of the identification of mod-472 ule vertices 473
The appendix formalizes module identification by maximizing a weight-based objective over divisions represented by a binary tree. QuaBiMo defines valid modules as bipartite leaf sets and searches tree rearrangements to improve the objective.
- Objective function: The algorithm scores a division C by maximizing the sum of within-module weight differences while minimizing differences outside modules.The edge-weight difference is positive within modules and negative outside them, so the objective rewards within-module structure and penalizes external structure.
- Tree representation: A binary tree D with n leaves represents candidate divisions, with internal vertices arbitrarily connected.The tree structure provides the space in which module arrangements are encoded and optimized.
- Module definition: A module is the leaf set below an internal vertex that has a leaf child, has no ancestor with a leaf child, and contains vertices from both bipartite sets.These conditions identify module vertices and ensure each module spans both vertex classes.
- Vertex contributions: Each internal vertex is labeled by its position relative to a module vertex and assigned a contribution g_v to the total objective.The label r_v distinguishes vertices above, at, or below a module vertex, while L_v and R_v identify the leaf sets of its two child subtrees.
- Optimization procedure: To optimize the objective, the algorithm randomly selects an internal edge, simulates one of two subtree rearrangements, and computes the resulting change in the score.The rearrangements permute alternative subtrees around two internal vertices, and the score change is calculated from their r_v labels.