Module identification in bipartite and directed networks

Landscape structure influences modularity patterns in farm food webs: consequences for pest control

Landscape management affects species interactions within a community, leading to alterations in the structure of networks. Modules are link-dense regions of the network where species interact more closely within the module than between modules of the network. Insufficient network resolution has meant that modules have proved difficult to identify, even though they appear important in the propagation of disturbance impacts. We applied a standardized approach across 20 farms to obtain well-resolved food webs to characterize network structure and explore how modularity changes in response to management (organic and conventional). All networks showed significantly higher modularity than random networks. Farm management had no effect on the number of modules per farm or module richness, but there was a significant loss of links between modules on conventional farms, which may affect the long-term stability of these networks. We found a significant association between modules and major habitat groups. If modules form as a result of interactions between species that utilize similar habitats, then ecosystem services to the crop components of the landscape, such as pest control by parasitoids originating in the non-crop vegetation, are less likely to occur on these farms.

Origin of compartmentalization in food webs

The response of an ecosystem to perturbations is mediated by both antagonistic and facilitative interactions between species. It is thought that a community's resilience depends crucially on the food web--the network of trophic interactions--and on the food web's degree of compartmentalization. Despite its ecological importance, compartmentalization and the mechanisms that give rise to it remain poorly understood. Here we investigate several definitions of compartments, propose ways to understand the ecological meaning of these definitions, and quantify the degree of compartmentalization of empirical food webs. We find that the compartmentalization observed in empirical food webs can be accounted for solely by the niche organization of species and their diets. By uncovering connections between compartmentalization and species' diet contiguity, our findings help us understand which perturbations can result in fragmentation of the food web and which can lead to catastrophic effects. Additionally, we show that the composition of compartments can be used to address the long-standing question of what determines the ecological niche of a species.

Expression QTL modules as functional components underlying higher-order phenotypes

Systems genetics studies often involve the mapping of numerous regulatory relations between genetic loci and expression traits. These regulatory relations form a bipartite network consisting of genetic loci and expression phenotypes. Modular network organizations may arise from the pleiotropic and polygenic regulation of gene expression. Here we analyzed the expression QTL (eQTL) networks derived from expression genetic data of yeast and mouse liver and found 65 and 98 modules respectively. Computer simulation result showed that such modules rarely occurred in randomized networks with the same number of nodes and edges and same degree distribution. We also found significant within-module functional coherence. The analysis of genetic overlaps and the evidences from biomedical literature have linked some eQTL modules to physiological phenotypes. Functional coherence within the eQTL modules and genetic overlaps between the modules and physiological phenotypes suggests that eQTL modules may act as functional units underlying the higher-order phenotypes.

The nested structure of cancer symptoms. Implications for analyzing co-occurrence and managing symptoms

OBJECTIVE

Although many cancer patients experience multiple concurrent symptoms, most studies have either focused on the analysis of single symptoms, or have used methods such as factor analysis that make a priori assumptions about how the data is structured. This article addresses both limitations by first visually exploring the data to identify patterns in the co-occurrence of multiple symptoms, and then using those insights to select and develop quantitative measures to analyze and validate the results.

METHODS

We used networks to visualize how 665 cancer patients reported 18 symptoms, and then quantitatively analyzed the observed patterns using degree of symptom overlap between patients, degree of symptom clustering using network modularity, clustering of symptoms based on agglomerative hierarchical clustering, and degree of nestedness of the symptoms based on the most frequently co-occurring symptoms for different sizes of symptom sets. These results were validated by assessing the statistical significance of the quantitative measures through comparison with random networks of the same size and distribution.

RESULTS

The cancer symptoms tended to co-occur in a nested structure, where there was a small set of symptoms that co-occurred in many patients, and progressively larger sets of symptoms that co-occurred among a few patients.

CONCLUSIONS

These results suggest that cancer symptoms co-occur in a nested pattern as opposed to distinct clusters, thereby demonstrating the value of exploratory network analyses to reveal complex relationships between patients and symptoms. The research also extends methods for exploring symptom co-occurrence, including methods for quantifying the degree of symptom overlap and for examining nested co-occurrence in co-occurrence data. Finally, the analysis also suggested implications for the design of systems that assist in symptom assessment and management. The main limitation of the study was that only one dataset was considered, and future studies should attempt to replicate the results in new data.

Combinatorial approach to modularity

Communities are clusters of nodes with a higher than average density of internal connections. Their detection is of great relevance to better understand the structure and hierarchies present in a network. Modularity has become a standard tool in the area of community detection, providing at the same time a way to evaluate partitions and, by maximizing it, a method to find communities. In this work, we study the modularity from a combinatorial point of view. Our analysis (as the modularity definition) relies on the use of the configurational model, a technique that given a graph produces a series of randomized copies keeping the degree sequence invariant. We develop an approach that enumerates the null model partitions and can be used to calculate the probability distribution function of the modularity. Our theory allows for a deep inquiry of several interesting features characterizing modularity such as its resolution limit and the statistics of the partitions that maximize it. Additionally, the study of the probability of extremes of the modularity in the random graph partitions opens the way for a definition of the statistical significance of network partitions.

Edge direction and the structure of networks

Directed networks are ubiquitous and are necessary to represent complex systems with asymmetric interactions--from food webs to the World Wide Web. Despite the importance of edge direction for detecting local and community structure, it has been disregarded in studying a basic type of global diversity in networks: the tendency of nodes with similar numbers of edges to connect. This tendency, called assortativity, affects crucial structural and dynamic properties of real-world networks, such as error tolerance or epidemic spreading. Here we demonstrate that edge direction has profound effects on assortativity. We define a set of four directed assortativity measures and assign statistical significance by comparison to randomized networks. We apply these measures to three network classes--online/social networks, food webs, and word-adjacency networks. Our measures (i) reveal patterns common to each class, (ii) separate networks that have been previously classified together, and (iii) expose limitations of several existing theoretical models. We reject the standard classification of directed networks as purely assortative or disassortative. Many display a class-specific mixture, likely reflecting functional or historical constraints, contingencies, and forces guiding the system's evolution.

An Efficient Algorithm for Optimizing Bipartite Modularity in Bipartite Networks

Modularity evaluates the quality of a division of network nodes into communities, and modularity optimization is the most widely used class of methods for detecting communities in networks. In bipartite networks, there are correspondingly bipartite modularity and bipartite modularity optimization. LPAb, a very fast label propagation algorithm based on bipartite modularity optimization, tends to become stuck in poor local maxima, yielding suboptimal community divisions with low bipartite modularity. We therefore propose LPAb+, a hybrid algorithm combining modified LPAb, or LPAb’, and MSG, a multistep greedy agglomerative algorithm, with the objective of using MSG to drive LPAb out of local maxima. We use four commonly used real-world bipartite networks to demonstrate LPAb+ capability in detecting community divisions with remarkably higher bipartite modularity than LPAb. We show how LPAb+ outperforms other bipartite modularity optimization algorithms, without compromising speed.

When metabolism meets topology: Reconciling metabolite and reaction networks

The search for a systems-level picture of metabolism as a web of molecular interactions provides a paradigmatic example of how the methods used to characterize a system can bias the interpretation of its functional meaning. Metabolic maps have been analyzed using novel techniques from network theory, revealing some non-trivial, functionally relevant properties. These include a small-world structure and hierarchical modularity. However, as discussed here, some of these properties might actually result from an inappropriate way of defining network interactions. Starting from the so-called bipartite organization of metabolism, where the two meaningful subsets (reactions and metabolites) are considered, most current works use only one of the subsets by means of so-called graph projections. Unfortunately, projected graphs often ignore relevant biological and chemical constraints, thus leading to statistical artifacts. Some of these drawbacks and alternative approaches need to be properly addressed.

Finding communities in directed networks

To identify communities in directed networks, we propose a generalized form of modularity in directed networks by presenting the quantity LinkRank, which can be considered as the PageRank of links. This generalization is consistent with the original modularity in undirected networks and the modularity optimization methods developed for undirected networks can be directly applied to directed networks by optimizing our modified modularity. Also, a model network, which can be used as a benchmark network in further community studies, is proposed to verify our method. Our method is supposed to find communities effectively in citation- or reference-based directed networks.

Networks of spatial genetic variation across species

Spatial patterns of genetic variation provide information central to many ecological, evolutionary, and conservation questions. This spatial variability has traditionally been analyzed through summary statistics between pairs of populations, therefore missing the simultaneous influence of all populations. More recently, a network approach has been advocated to overcome these limitations. This network approach has been applied to a few cases limited to a single species at a time. The question remains whether similar patterns of spatial genetic variation and similar functional roles for specific patches are obtained for different species. Here we study the networks of genetic variation of four Mediterranean woody plant species inhabiting the same habitat patches in a highly fragmented forest mosaic in Southern Spain. Three of the four species show a similar pattern of genetic variation with well-defined modules or groups of patches holding genetically similar populations. These modules can be thought of as the long-sought-after, evolutionarily significant units or management units. The importance of each patch for the cohesion of the entire network, though, is quite different across species. This variation creates a tremendous challenge for the prioritization of patches to conserve the genetic variation of multispecies assemblages.

Multiresolution community detection for megascale networks by information-based replica correlations

We use a Potts model community detection algorithm to accurately and quantitatively evaluate the hierarchical or multiresolution structure of a graph. Our multiresolution algorithm calculates correlations among multiple copies ("replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by strongly correlated replicas. The average normalized mutual information, the variation in information, and other measures, in principle, give a quantitative estimate of the "best" resolutions and indicate the relative strength of the structures in the graph. Because the method is based on information comparisons, it can, in principle, be used with any community detection model that can examine multiple resolutions. Our approach may be extended to other optimization problems. As a local measure, our Potts model avoids the "resolution limit" that affects other popular models. With this model, our community detection algorithm has an accuracy that ranks among the best of currently available methods. Using it, we can examine graphs over 40 x10;{6} nodes and more than 1 x10;{9} edges. We further report that the multiresolution variant of our algorithm can solve systems of at least 200 000 nodes and 10 x 10;{6} edges on a single processor with exceptionally high accuracy. For typical cases, we find a superlinear scaling O(L1.3) for community detection and O(L1.3 log N) for the multiresolution algorithm, where L is the number of edges and N is the number of nodes in the system.

Multi-tissue coexpression networks reveal unexpected subnetworks associated with disease

Tissue-to-tissue coexpression networks between genes in hypothalamus, liver or adipose tissue enable identification of obesity-specific genes.

Background

Obesity is a particularly complex disease that at least partially involves genetic and environmental perturbations to gene-networks connecting the hypothalamus and several metabolic tissues, resulting in an energy imbalance at the systems level.

Results

To provide an inter-tissue view of obesity with respect to molecular states that are associated with physiological states, we developed a framework for constructing tissue-to-tissue coexpression networks between genes in the hypothalamus, liver or adipose tissue. These networks have a scale-free architecture and are strikingly independent of gene-gene coexpression networks that are constructed from more standard analyses of single tissues. This is the first systematic effort to study inter-tissue relationships and highlights genes in the hypothalamus that act as information relays in the control of peripheral tissues in obese mice. The subnetworks identified as specific to tissue-to-tissue interactions are enriched in genes that have obesity-relevant biological functions such as circadian rhythm, energy balance, stress response, or immune response.

Conclusions

Tissue-to-tissue networks enable the identification of disease-specific genes that respond to changes induced by different tissues and they also provide unique details regarding candidate genes for obesity that are identified in genome-wide association studies. Identifying such genes from single tissue analyses would be difficult or impossible.

Food web models: a plea for groups

The concept of a group is ubiquitous in biology. It underlies classifications in evolution and ecology, including those used to describe phylogenetic levels, the habitat and functional roles of organisms in ecosystems. Surprisingly, this concept is not explicitly included in simple models for the structure of food webs, the ecological networks formed by consumer-resource interactions. We present here the simplest possible model based on groups, and show that it performs substantially better than current models at predicting the structure of large food webs. Our group-based model can be applied to different types of biological and non-biological networks, and for the first time merges in the same framework two important notions in network theory: that of compartments (sets of highly interacting nodes) and that of roles (sets of nodes that have similar interaction patterns). This model provides a basis to examine the significance of groups in biological networks and to develop more accurate models for ecological network structure. It is especially relevant at a time when a new generation of empirical data is providing increasingly large food webs.

Biclique communities

We present a method for detecting communities in bipartite networks. Based on an extension of the k -clique community detection algorithm, we demonstrate how modular structure in bipartite networks presents itself as overlapping bicliques. If bipartite information is available, the biclique community detection algorithm retains all of the advantages of the k -clique algorithm, but avoids discarding important structural information when performing a one-mode projection of the network. Further, the biclique community detection algorithm provides a level of flexibility by incorporating independent clique thresholds for each of the nonoverlapping node sets in the bipartite network.

Looking for robust properties in the growth of an academic network: the case of the Uruguayan biological research community

Graph-theoretical methods have recently been used to analyze certain properties of natural and social networks. In this work, we have investigated the early stages in the growth of a Uruguayan academic network, the Biology Area of the Programme for the Development of Basic Science (PEDECIBA). This transparent social network is a territory for the exploration of the reliability of clustering methods that can potentially be used when we are confronted with opaque natural systems that provide us with a limited spectrum of observables (happens in research on the relations between brain, thought and language). From our social net, we constructed two different graph representations based on the relationships among researchers revealed by their co-participation in Master's thesis committees. We studied these networks at different times and found that they achieve connectedness early in their evolution and exhibit the small-world property (i.e. high clustering with short path lengths). The data seem compatible with power law distributions of connectivity, clustering coefficients and betweenness centrality. Evidence of preferential attachment of new nodes and of new links between old nodes was also found in both representations. These results suggest that there are topological properties observed throughout the growth of the network that do not depend on the representations we have chosen but reflect intrinsic properties of the academic collective under study. Researchers in PEDECIBA are classified according to their specialties. We analysed the community structure detected by a standard algorithm in both representations. We found that much of the pre-specified structure is recovered and part of the mismatches can be attributed to convergent interests between scientists from different sub-disciplines. This result shows the potentiality of some clustering methods for the analysis of partially known natural systems.

Community structure in directed networks

We consider the problem of finding communities or modules in directed networks. In the past, the most common approach to this problem has been to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used community finding technique of modularity maximization can be generalized in a principled fashion to incorporate information contained in edge directions. We describe an explicit algorithm based on spectral optimization of the modularity and show that it gives demonstrably better results than previous methods on a variety of test networks, both real and computer generated.

Maps of random walks on complex networks reveal community structure

To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network-including physics, chemistry, molecular biology, and medicine-information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.

Modularity and community detection in bipartite networks

The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. 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 bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.

Extracting the hierarchical organization of complex systems

Extracting understanding from the growing "sea" of biological and socioeconomic data is one of the most pressing scientific challenges facing us. Here, we introduce and validate an unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks. We define an ensemble of hierarchically nested random graphs, which we use to validate the method. We then apply our method to real-world networks, including the air-transportation network, an electronic circuit, an e-mail exchange network, and metabolic networks. Our analysis of model and real networks demonstrates that our method extracts an accurate multiscale representation of a complex system.