Improved community detection in weighted bipartite networks
Royal Society Open SciencePublished 1 January 2016Open access
Stephen J. Beckett
Citations527
SJR quartileQ1
SJR score0.80
SNIP1.12
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two new algorithms, LPAwb+ and DIRTLPAwb+, are introduced for maximizing weighted modularity in bipartite networks and robustly identify partitions with high modularity scores.
Abstract
Real-world complex networks are composed of non-random quantitative interactions. Identifying communities of nodes that tend to interact more with each other than the network as a whole is a key research focus across multiple disciplines, yet many community detection algorithms only use information about the presence or absence of interactions between nodes. Weighted modularity is a potential method for evaluating the quality of community partitions in quantitative networks. In this framework, the optimal community partition of a network can be found by searching for the partition that maximizes modularity. Attempting to find the partition that maximizes modularity is a computationally hard problem requiring the use of algorithms. QuanBiMo is an algorithm that has been proposed to maximize weighted modularity in bipartite networks. This paper introduces two new algorithms, LPAwb+ and DIRTLPAwb+, for maximizing weighted modularity in bipartite networks. LPAwb+ and DIRTLPAwb+ robustly identify partitions with high modularity scores. DIRTLPAwb+ consistently matched or outperformed QuanBiMo, while the speed of LPAwb+ makes it an attractive choice for detecting the modularity of larger networks. Searching for modules using weighted data (rather than binary data) provides a different and potentially insightful method for evaluating network partitions.
Keywords
PsychologyPhysics and Astronomy
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
Physics ReportsCommunity detection in graphs
11,324 Citations2009Santo Fortunato
A thorough exposition of community structure, or clustering, is attempted, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists.
Networks: An Introduction
7,048 Citations2010Mark Newman
MQUP eBooksConjectures and Refutations
3,388 Citations2020Karl R. Popper
This chapter presents a list of the scientific publications written by Jacques Monod from 1931 to 1976, which include books, monographs, chapters, and chapters of monographs.
Journal of Statistical Mechanics Theory and ExperimentComparing community structure identification
2,877 Citations2005León Danon, Albert Dı́az-Guilera +2 more
It is found that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes.
Proceedings of the National Academy of SciencesThe modularity of pollination networks
2,629 Citations2007Jens M. Olesen, Jordi Bascompte +2 more
If these key species go extinct, modules and networks may break apart and initiate cascades of extinction, Thus, species serving as hubs and connectors should receive high conservation priorities.
Physical Review EAnalysis of weighted networks
2,451 Citations2004M. E. J. Newman
It is pointed out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighting graphs to weighted ones as well.
NatureHierarchical structure and the prediction of missing links in networks
2,198 Citations2008Aaron Clauset, Cristopher Moore +1 more
This work presents a general technique for inferring hierarchical structure from network data and shows that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks.
Introducing the bipartite Package: Analysing Ecological Networks
1,493 Citations2008Carsten F. Dormann, Bernd Gruber +1 more
The new R-package bipartite, introduced here, provides functions to viualise webs and calculate a series of indices commonly used to describe pattern in ecological webs, focusing on webs consisting of only two trophic levels, e.g. pollination webs or predator-prey-webs.
Proceedings of the National Academy of SciencesRandom graph models of social networks
1,363 Citations2002M. E. J. Newman, Duncan J. Watts +1 more
It is found that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Physical Review EPerformance of modularity maximization in practical contexts
950 Citations2010Benjamin H. Good, Yves-Alexandre de Montjoye +1 more
It is shown that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum, implying that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts.
Physical Review EModularity and community detection in bipartite networks
751 Citations2007Michael Barber
The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartites networks.
Royal Society Open ScienceImproved community detection in weighted bipartite networks
527 Citations2016Stephen J. Beckett
Two new algorithms, LPAwb+ and DIRTLPAwb+, are introduced for maximizing weighted modularity in bipartite networks and robustly identify partitions with high modularity scores.
Methods in Ecology and EvolutionA method for detecting modules in quantitative bipartite networks
517 Citations2013Carsten F. Dormann, Rouven Strauss
The algorithm introduced here must be seen as a considerable improvement over the current standard of algorithms for binary networks due to its higher sensitivity and likely to lead to be useful for detecting modules in the typically noisy data of ecological networks.
EcologyFlowering Ecology of Some Spring Woodland Herbs
471 Citations1978Douglas W. Schemske, Mary F. Willson +5 more
It is suggested that flowering in early spring is a high-risk option in terms of insect- mediated sexual reproduction and constraints on flowering phenology are discussed, including the predictability of suitable conditions.
Ecology LettersThe structure of a plant‐pollinator food web
462 Citations1999Jane Memmott
The aim of this paper is to illustrate how contemporary methods of web construction and analysis can be applied to plant-pollinator communities.
Physical Review EModule identification in bipartite and directed networks
409 Citations2007Roger Guimerà, Marta Sales‐Pardo +1 more
This work reports on an approach especially suited for module detection in bipartite networks, and defines a set of random networks that enable it to validate the approach.
Diversity and DistributionsInvasion of pollination networks on oceanic islands: importance of invader complexes and endemic super generalists
365 Citations2002Jens M. Olesen, Louise I. Eskildsen +1 more
This study suggested that endemic super‐generalist species, i.e. pollinators or plant species with a very wide pollination niche, include new invaders in their set of food plants or pollinators and thereby improve establishment success of the invaders.
NatureStrong contributors to network persistence are the most vulnerable to extinction
351 Citations2011Serguei Saavedra, Daniel B. Stouffer +2 more
A suite of structural and dynamic methods are applied to an ensemble of flowering plant/insect pollinator networks to introduce a new paradox into the study of the persistence of cooperative networks, and potentially address questions about the impact of invasive species in ecological systems and new competitors in economic systems.
Ecological MonographsPollination Ecology of the Spring Wildflower Community of a Temperate Deciduous Forest
296 Citations1986Alexander F. Motten
Although inadequate pollination seems likely in the community, supplemental hand-pollination significantly improved fecundity in just 3 of the 12 species I examined, and it is the prevalence of such traits, rather than floral specialization or character displacement, that distinguishes the forest spring wildflower community from other communities with potentially inadequate pollinator service.
The American NaturalistEcological Specialization and Susceptibility to Disturbance: Conjectures and Refutations
295 Citations2002Diego P. Vázquez, Daniel Simberloff
It is found that plant‐pollinator interactions tend to be asymmetric in this system; there was no relationship between the degree of specialization of a given species and the degreeof specialization of its interaction partners, and asymmetry of interactions did not explain the variability in species’ responses to disturbance.
Functional EcologySpecialization on traits as basis for the niche‐breadth of flower visitors and as structuring mechanism of ecological networks
280 Citations2012Robert R. Junker, Nico Blüthgen +5 more
The data suggested a hierarchical sequence of flower traits influencing the flower visitors' behaviour and thus network structure: flowering phenology was found to have the strongest effect, followed by flower height, nectar-tube depth and floral reflectance.
Physical Review EAnalysis of community structure in networks of correlated data
266 Citations2009Sergio Gómez, Pablo Jensen +1 more
A reformulation of modularity that allows the analysis of the community structure in networks of correlated data and preserves the probabilistic semantics of the original definition even when the network is directed, weighted, signed, and has self-loops.
Annals of BotanyThe Pollination Ecology of an Assemblage of Grassland Asclepiads in South Africa
225 Citations2003Jeff Ollerton
Nestedness analysis of the data set showed that there was predictability and structure to the pattern of plant-pollinator interactions, with generalist insects visiting specialized plants and vice versa, and the research has shown that there is still much to be learned about plant- pollinator interactions in areas of high plant diversity such as South Africa.
EcographyThe structure of a high latitude plant‐flower visitor system: the dominance of flies
218 Citations1999Heidi Elberling, Jens M. Olesen
It is get that the proportion of dipteran species of the total pollinator fauna increases with latitude but that the proportions of species of Diptera, Hymenoptera and Lepidoptera do not vary significantly among high latitude systems.
The ISME JournalMulti-scale structure and geographic drivers of cross-infection within marine bacteria and phages
201 Citations2012César O. Flores, Sergi Valverde +1 more
This paper evaluates the largest known phage-bacteria interaction data set, representing the interaction of 215 phage types with 286 host types sampled from geographically separated sites in the Atlantic Ocean, and finds that this interaction network is highly modular.
Australian Journal of EcologyPollination biology in the Snowy Mountains of Australia: Comparisons with montane Colorado, USA
177 Citations1988David W. Inouye, Graham H. Pyke
There appear to be significant differences between the plant-pollinator community of alpine Australia and other alpine areas where bumblebees are common pollinators, including shorter proboscis and corolla tube lengths, and perhaps an increased diversity and significance of flies as pollinators.
Ecology LettersChanges in interaction biodiversity induced by an introduced ungulate
143 Citations2003Diego P. Vázquez, Daniel Simberloff
There is strong evidence that an introduced species is able to affect the network of interactions among coexisting species and the presence of cattle has significantly modified the structure of the plant–pollinator interaction network.
Canadian Journal of BotanyThe reproductive biology of boreal forest herbs. I. Breeding systems and pollination
133 Citations1987Spencer C. H. Barrett, Kaius Helenurm
Detailed observations and experimental studies of the reproductive biology of 12 boreal forest herbs were conducted over a 3-year period (1978–1980) in spruce–fir forests of central New Brunswick to determine the breeding systems of herbs.
Journal of Animal EcologyPollination networks of oil‐flowers: a tiny world within the smallest of all worlds
111 Citations2009Elisângela L. S. Bezerra, Isabel Cristina Machado +1 more
The findings reinforce the hypothesis that each ecological service is in fact a mosaic of different subservices with a hierarchical structure ('webs within webs') and therefore, the Malpighiaceae have a robust pollination service in the Neotropics.
Journal of BiogeographyIdentifying compartments in presence–absence matrices and bipartite networks: insights into modularity measures
110 Citations2012Élisa Thébault
Different modularity indices are compared to investigate which is the most appropriate for studying presence–absence matrices and similar types of networks, such as bipartite networks.
SOAR (Shinshu University)Insect-flower Relationship in the Primary Beech Forest of Ashu, Kyoto : An Overview of the Flowering Phenology and the Seasonal Pattern of Insect Visits
103 Citations1990Makoto Katô, Takehiko Kakutani +2 more
In 1984-1987 insect visitors to flowers were monthly or bimonthly surveyed on 91 plant species or 37 families in the primary beech forest of Ashu, Kyoto, Japan, and flower preference was compared amohg insect orders and among families.
Methods in Ecology and EvolutionBiMat: a MATLAB package to facilitate the analysis of bipartite networks
72 Citations2015César O. Flores, Timothée Poisot +2 more
BiMat calculates the degree to which a bipartite network is modular and/or nested, the statistical significance of these patterns, and enables visualization of latent structures in the network.
The Canadian Field-NaturalistObservations on the Pollination Biology of Plants on Melville Island, N.W.T., Canada
49 Citations1967Theodore Mosquin, J. E. H. Martin
Journal of Advanced Computational Intelligence and Intelligent InformaticsAn Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks
41 Citations2010Xin Liu, Tsuyoshi Murata
The Canadian Field-NaturalistInsect pollinators of the Mer Bleue peat bog of Ottawa
38 Citations1976Ernest Small
Optimization LettersA locally optimal hierarchical divisive heuristic for bipartite modularity maximization
20 Citations2013Alberto Costa, Pierre Hansen
A hierarchical divisive heuristic for approximate modularity maximization in bipartite graphs is proposed and the subproblem of bipartitioning a cluster is solved exactly; hence the heuristic is locally optimal.
Interactions among Introduced Ungulates, Plants, and Pollinators: A Field Study in the Temperate Forest of the Southern Andes
18 Citations2002Diego P. Vázquez
This study suggests that introduced ungulates can in some circumstances affect plant-pollinator interactions significantly, and in most cases plant- Pollinator mutualisms appear resilient to the effects of introduced unGulates, and the direct effects of introducing ungulate on plants and pollinators are in general stronger than the indirect effect through mutualistic partners.
Optimization LettersMaximizing Barber’s bipartite modularity is also hard
18 Citations2014Atsushi Miyauchi, Noriyoshi Sukegawa
This study proves that maximizing bipartite modularity is also NP-hard, and shows the NP-completeness of its decision version by constructing a reduction from a classical partitioning problem.
F1000ResearchAn a posteriori measure of network modularity
11 Citations2013Timothée Poisot
This article proposes a measure of modularity, which is simply defined as the ratio of interactions established between members of the same modules vs. members of different modules, and applies it to a large dataset of 290 ecological networks representing host–parasite and predator–prey interactions.
F1000ResearchAn a posteriori measure of network modularity
11 Citations2013Timothée Poisot
A posteriori measure of modularity, which represents the ratio of interactions between members of the same modules vs. members of different modules, is proposed and applied to a large dataset of 290 ecological networks to show that it gives new insights about their modularity.
F1000ResearchAn a posteriori measure of network modularity
7 Citations2013Timothée Poisot
A posteriori measure of modularity, which represents the ratio of interactions between members of the same modules vs. members of different modules, is proposed and applied to a large dataset of 290 ecological networks to show that it gives new insights about their modularity.
Zenodo (CERN European Organization for Nuclear Research)weighted-modularity-LPAwbPLUS: Improved community detection in weighted bipartite networks
1 Citations2015Beckett Stephen