Deciphering the global organization of clustering in real complex networks.
ABSTRACT: We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.
Project description:BACKGROUND: Brain structure and dynamics are interdependent through processes such as activity-dependent neuroplasticity. In this study, we aim to theoretically examine this interdependence in a model of spontaneous cortical activity. To this end, we simulate spontaneous brain dynamics on structural connectivity networks, using coupled nonlinear maps. On slow time scales structural connectivity is gradually adjusted towards the resulting functional patterns via an unsupervised, activity-dependent rewiring rule. The present model has been previously shown to generate cortical-like, modular small-world structural topology from initially random connectivity. We provide further biophysical justification for this model and quantitatively characterize the relationship between structure, function and dynamics that accompanies the ensuing self-organization. RESULTS: We show that coupled chaotic dynamics generate ordered and modular functional patterns, even on a random underlying structural connectivity. Consequently, structural connectivity becomes more modular as it rewires towards these functional patterns. Functional networks reflect the underlying structural networks on slow time scales, but significantly less so on faster time scales. In spite of ordered functional topology, structural networks remain robustly interconnected--and therefore small-world--due to the presence of central, inter-modular hub nodes. The noisy dynamics of these hubs enable them to persist despite ongoing rewiring and despite their comparative absence in functional networks. CONCLUSION: Our results outline a theoretical mechanism by which brain dynamics may facilitate neuroanatomical self-organization. We find time scale dependent differences between structural and functional networks. These differences are likely to arise from the distinct dynamics of central structural nodes.
Project description:Network science has been extensively developed to characterize the structural properties of complex systems, including brain networks inferred from neuroimaging data. As a result of the inference process, networks estimated from experimentally obtained biological data represent one instance of a larger number of realizations with similar intrinsic topology. A modelling approach is therefore needed to support statistical inference on the bottom-up local connectivity mechanisms influencing the formation of the estimated brain networks. Here, we adopted a statistical model based on exponential random graph models (ERGMs) to reproduce brain networks, or connectomes, estimated by spectral coherence between high-density electroencephalographic (EEG) signals. ERGMs are made up by different local graph metrics, whereas the parameters weight the respective contribution in explaining the observed network. We validated this approach in a dataset of N = 108 healthy subjects during eyes-open (EO) and eyes-closed (EC) resting-state conditions. Results showed that the tendency to form triangles and stars, reflecting clustering and node centrality, better explained the global properties of the EEG connectomes than other combinations of graph metrics. In particular, the synthetic networks generated by this model configuration replicated the characteristic differences found in real brain networks, with EO eliciting significantly higher segregation in the alpha frequency band (8-13 Hz) than EC. Furthermore, the fitted ERGM parameter values provided complementary information showing that clustering connections are significantly more represented from EC to EO in the alpha range, but also in the beta band (14-29 Hz), which is known to play a crucial role in cortical processing of visual input and externally oriented attention. Taken together, these findings support the current view of the functional segregation and integration of the brain in terms of modules and hubs, and provide a statistical approach to extract new information on the (re)organizational mechanisms in healthy and diseased brains.
Project description:Biological networks play an increasingly important role in the exploration of functional modularity and cellular organization at a systemic level. Quite often the first tools used to analyze these networks are clustering algorithms. We concentrate here on the specific task of predicting protein complexes (PC) in large protein-protein interaction networks (PPIN). Currently, many state-of-the-art algorithms work well for networks of small or moderate size. However, their performance on much larger networks, which are becoming increasingly common in modern proteome-wise studies, needs to be re-assessed.We present a new fast algorithm for clustering large sparse networks: Core&Peel, which runs essentially in time and storage O(a(G)m+n) for a network G of n nodes and m arcs, where a(G) is the arboricity of G (which is roughly proportional to the maximum average degree of any induced subgraph in G). We evaluated Core&Peel on five PPI networks of large size and one of medium size from both yeast and homo sapiens, comparing its performance against those of ten state-of-the-art methods. We demonstrate that Core&Peel consistently outperforms the ten competitors in its ability to identify known protein complexes and in the functional coherence of its predictions. Our method is remarkably robust, being quite insensible to the injection of random interactions. Core&Peel is also empirically efficient attaining the second best running time over large networks among the tested algorithms.Our algorithm Core&Peel pushes forward the state-of the-art in PPIN clustering providing an algorithmic solution with polynomial running time that attains experimentally demonstrable good output quality and speed on challenging large real networks.
Project description:The formation of the complex network architecture of neural systems is subject to multiple structural and functional constraints. Two obvious but apparently contradictory constraints are low wiring cost and high processing efficiency, characterized by short overall wiring length and a small average number of processing steps, respectively. Growing evidence shows that neural networks are results from a trade-off between physical cost and functional value of the topology. However, the relationship between these competing constraints and complex topology is not well understood quantitatively. We explored this relationship systematically by reconstructing two known neural networks, Macaque cortical connectivity and C. elegans neuronal connections, from combinatory optimization of wiring cost and processing efficiency constraints, using a control parameter ?, and comparing the reconstructed networks to the real networks. We found that in both neural systems, the reconstructed networks derived from the two constraints can reveal some important relations between the spatial layout of nodes and the topological connectivity, and match several properties of the real networks. The reconstructed and real networks had a similar modular organization in a broad range of ?, resulting from spatial clustering of network nodes. Hubs emerged due to the competition of the two constraints, and their positions were close to, and partly coincided, with the real hubs in a range of ? values. The degree of nodes was correlated with the density of nodes in their spatial neighborhood in both reconstructed and real networks. Generally, the rebuilt network matched a significant portion of real links, especially short-distant ones. These findings provide clear evidence to support the hypothesis of trade-off between multiple constraints on brain networks. The two constraints of wiring cost and processing efficiency, however, cannot explain all salient features in the real networks. The discrepancy suggests that there are further relevant factors that are not yet captured here.
Project description:BACKGROUND: In recent years, an extensive characterization of network structures has been made in an effort to elucidate design principles of metabolic networks, providing valuable insights into the functional organization and the evolutionary history of organisms. However, previous analyses have not discussed the effects of environmental factors (i.e., exogenous forces) in shaping network structures. In this work, we investigate the effect of temperature, which is one of the environmental factors that may have contributed to shaping structures of metabolic networks. RESULTS: For this, we investigate the correlations between several structural properties characterized by graph metrics like the edge density, the degree exponent, the clustering coefficient, and the subgraph concentration in the metabolic networks of 113 prokaryotes and optimal growth temperature. As a result, we find that these structural properties are correlated with the optimal growth temperature. With increasing temperature, the edge density, the clustering coefficient and the subgraph concentration decrease and the degree exponent becomes large. CONCLUSION: This result implies that the metabolic networks transit with temperature as follows. The density of chemical reactions becomes low, the connectivity of the networks becomes homogeneous such as random networks and both the network modularity, based on the graph-theoretic clustering coefficient, and the frequency of recurring subgraphs decay. In short, metabolic networks undergo a change from heterogeneous and high-modular structures to homogeneous and low-modular structures, such as random networks, with temperature. This finding may suggest that the temperature plays an important role in the design principles of metabolic networks.
Project description:Functional magnetic resonance imaging (fMRI) is one of the most useful methods to generate functional connectivity networks of the brain. However, conventional network generation methods ignore dynamic changes of functional connectivity between brain regions. Previous studies proposed constructing high-order functional connectivity networks that consider the time-varying characteristics of functional connectivity, and a clustering method was performed to decrease computational cost. However, random selection of the initial clustering centers and the number of clusters negatively affected classification accuracy, and the network lost neurological interpretability. Here we propose a novel method that introduces the minimum spanning tree method to high-order functional connectivity networks. As an unbiased method, the minimum spanning tree simplifies high-order network structure while preserving its core framework. The dynamic characteristics of time series are not lost with this approach, and the neurological interpretation of the network is guaranteed. Simultaneously, we propose a multi-parameter optimization framework that involves extracting discriminative features from the minimum spanning tree high-order functional connectivity networks. Compared with the conventional methods, our resting-state fMRI classification method based on minimum spanning tree high-order functional connectivity networks greatly improved the diagnostic accuracy for Alzheimer's disease.
Project description:Graph theory is a useful tool for deciphering structural and functional networks of the brain on various spatial and temporal scales. The clustering coefficient quantifies the abundance of connected triangles in a network and is a major descriptive statistics of networks. For example, it finds an application in the assessment of small-worldness of brain networks, which is affected by attentional and cognitive conditions, age, psychiatric disorders and so forth. However, it remains unclear how the clustering coefficient should be measured in a correlation-based network, which is among major representations of brain networks. In the present article, we propose clustering coefficients tailored to correlation matrices. The key idea is to use three-way partial correlation or partial mutual information to measure the strength of the association between the two neighboring nodes of a focal node relative to the amount of pseudo-correlation expected from indirect paths between the nodes. Our method avoids the difficulties of previous applications of clustering coefficient (and other) measures in defining correlational networks, i.e., thresholding on the correlation value, discarding of negative correlation values, the pseudo-correlation problem and full partial correlation matrices whose estimation is computationally difficult. For proof of concept, we apply the proposed clustering coefficient measures to functional magnetic resonance imaging data obtained from healthy participants of various ages and compare them with conventional clustering coefficients. We show that the clustering coefficients decline with the age. The proposed clustering coefficients are more strongly correlated with age than the conventional ones are. We also show that the local variants of the proposed clustering coefficients (i.e., abundance of triangles around a focal node) are useful in characterizing individual nodes. In contrast, the conventional local clustering coefficients were strongly correlated with and therefore may be confounded by the node's connectivity. The proposed methods are expected to help us to understand clustering and lack thereof in correlational brain networks, such as those derived from functional time series and across-participant correlation in neuroanatomical properties.
Project description:BACKGROUND: Previous studies have shown modular structures in PPI (protein-protein interaction) networks. More recently, many genome and metagenome investigations have focused on identifying modules in PPI networks. However, most of the existing methods are insufficient when applied to networks with overlapping modular structures. In our study, we describe a novel overlapping module identification method (OMIM) to address this problem. RESULTS: Our method is an agglomerative clustering method merging modules according to their contributions to modularity. Nodes that have positive effects on more than two modules are defined as overlapping parts. As well, we designed de-noising steps based on a clustering coefficient and hub finding steps based on nodal weight. CONCLUSIONS: The low computational complexity and few control parameters prove that our method is suitable for large scale PPI network analysis. First, we verified OMIM on a small artificial word association network which was able to provide us with a comprehensive evaluation. Then experiments on real PPI networks from the MIPS Saccharomyces Cerevisiae dataset were carried out. The results show that OMIM outperforms several other popular methods in identifying high quality modular structures.
Project description:The accessibility of a huge amount of protein-protein interaction (PPI) data has allowed to do research on biological networks that reveal the structure of a protein complex, pathways and its cellular organization. A key demand in computational biology is to recognize the modular structure of such biological networks. The detection of protein complexes from the PPI network, is one of the most challenging and significant problems in the post-genomic era. In Bioinformatics, the frequently employed approach for clustering the networks is Markov Clustering (MCL). Many of the researches for protein complex detection were done on the static PPI network, which suffers from a few drawbacks. To resolve this problem, this paper proposes an approach to detect the dynamic protein complexes through Markov Clustering based on Elephant Herd Optimization Approach (DMCL-EHO). Initially, the proposed method divides the PPI network into a set of dynamic subnetworks under various time points by combining the gene expression data and secondly, it employs the clustering analysis on every subnetwork using the MCL along with Elephant Herd Optimization approach. The experimental analysis was employed on different PPI network datasets and the proposed method surpasses various existing approaches in terms of accuracy measures. This paper identifies the common protein complexes that are expressively enriched in gold-standard datasets and also the pathway annotations of the detected protein complexes using the KEGG database.
Project description:Scaffolds and patterned substrates are among the most successful strategies to dictate the connectivity between neurons in culture. Here, we used numerical simulations to investigate the capacity of physical obstacles placed on a flat substrate to shape structural connectivity, and in turn collective dynamics and effective connectivity, in biologically-realistic neuronal networks. We considered ?-sized obstacles placed in mm-sized networks. Three main obstacle shapes were explored, namely crosses, circles and triangles of isosceles profile. They occupied either a small area fraction of the substrate or populated it entirely in a periodic manner. From the point of view of structure, all obstacles promoted short length-scale connections, shifted the in- and out-degree distributions toward lower values, and increased the modularity of the networks. The capacity of obstacles to shape distinct structural traits depended on their density and the ratio between axonal length and substrate diameter. For high densities, different features were triggered depending on obstacle shape, with crosses trapping axons in their vicinity and triangles funneling axons along the reverse direction of their tip. From the point of view of dynamics, obstacles reduced the capacity of networks to spontaneously activate, with triangles in turn strongly dictating the direction of activity propagation. Effective connectivity networks, inferred using transfer entropy, exhibited distinct modular traits, indicating that the presence of obstacles facilitated the formation of local effective microcircuits. Our study illustrates the potential of physical constraints to shape structural blueprints and remodel collective activity, and may guide investigations aimed at mimicking organizational traits of biological neuronal circuits.