Generalised power graph compression reveals dominant relationship patterns in complex networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Ahnert SE
PROVIDER: S-EPMC3964517 | biostudies-other | 2014
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks. We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution, indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein interactions, regulatory networks, or homology networks.
| S-EPMC2424176 | biostudies-literature
Project description:Networks are widely used as a tool for describing diverse real complex systems and have been successfully applied to many fields. The distance between networks is one of the most fundamental concepts for properly classifying real networks, detecting temporal changes in network structures, and effectively predicting their temporal evolution. However, this distance has rarely been discussed in the theory of complex networks. Here, we propose a graph distance between networks based on a Laplacian matrix that reflects the structural and dynamical properties of networked dynamical systems. Our results indicate that the Laplacian-based graph distance effectively quantifies the structural difference between complex networks. We further show that our approach successfully elucidates the temporal properties underlying temporal networks observed in the context of face-to-face human interactions.
| S-EPMC5057156 | biostudies-literature
Project description:Exponential random graph models (ERGMs), also known as p* models, have been utilized extensively in the social science literature to study complex networks and how their global structure depends on underlying structural components. However, the literature on their use in biological networks (especially brain networks) has remained sparse. Descriptive models based on a specific feature of the graph (clustering coefficient, degree distribution, etc.) have dominated connectivity research in neuroscience. Corresponding generative models have been developed to reproduce one of these features. However, the complexity inherent in whole-brain network data necessitates the development and use of tools that allow the systematic exploration of several features simultaneously and how they interact to form the global network architecture. ERGMs provide a statistically principled approach to the assessment of how a set of interacting local brain network features gives rise to the global structure. We illustrate the utility of ERGMs for modeling, analyzing, and simulating complex whole-brain networks with network data from normal subjects. We also provide a foundation for the selection of important local features through the implementation and assessment of three selection approaches: a traditional p-value based backward selection approach, an information criterion approach (AIC), and a graphical goodness of fit (GOF) approach. The graphical GOF approach serves as the best method given the scientific interest in being able to capture and reproduce the structure of fitted brain networks.
| S-EPMC3102079 | biostudies-other
Project description:The ability to control a complex network towards a desired behavior relies on our understanding of the complex nature of these social and technological networks. The existence of numerous control schemes in a network promotes us to wonder: what is the underlying relationship of all possible input nodes? Here we introduce input graph, a simple geometry that reveals the complex relationship between all control schemes and input nodes. We prove that the node adjacent to an input node in the input graph will appear in another control scheme, and the connected nodes in input graph have the same type in control, which they are either all possible input nodes or not. Furthermore, we find that the giant components emerge in the input graphs of many real networks, which provides a clear topological explanation of bifurcation phenomenon emerging in dense networks and promotes us to design an efficient method to alter the node type in control. The findings provide an insight into control principles of complex networks and offer a general mechanism to design a suitable control scheme for different purposes.
| S-EPMC5128914 | biostudies-literature
Project description:MotivationTechnological advancements in high-throughput DNA sequencing have led to an exponential growth of sequencing data being produced and stored as a byproduct of biomedical research. Despite its public availability, a majority of this data remains hard to query for the research community due to a lack of efficient data representation and indexing solutions. One of the available techniques to represent read data is a condensed form as an assembly graph. Such a representation contains all sequence information but does not store contextual information and metadata.ResultsWe present two new approaches for a compressed representation of a graph coloring: a lossless compression scheme based on a novel application of wavelet tries as well as a highly accurate lossy compression based on a set of Bloom filters. Both strategies retain a coloring even when adding to the underlying graph topology. We present construction and merge procedures for both methods and evaluate their performance on a wide range of different datasets. By dropping the requirement of a fully lossless compression and using the topological information of the underlying graph, we can reduce memory requirements by up to three orders of magnitude. Representing individual colors as independently stored modules, our approaches can be efficiently parallelized and provide strategies for dynamic use. These properties allow for an easy upscaling to the problem sizes common to the biomedical domain.Availability and implementationWe provide prototype implementations in C++, summaries of our experiments as well as links to all datasets publicly at https://github.com/ratschlab/graph_annotation.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC6530811 | biostudies-literature
Project description:Recent evidence indicates that the abundance of recurring elementary interaction patterns in complex networks, often called subgraphs or motifs, carry significant information about their function and overall organization. Yet, the underlying reasons for the variable quantity of different subgraph types, their propensity to form clusters, and their relationship with the networks' global organization remain poorly understood. Here we show that a network's large-scale topological organization and its local subgraph structure mutually define and predict each other, as confirmed by direct measurements in five well studied cellular networks. We also demonstrate the inherent existence of two distinct classes of subgraphs, and show that, in contrast to the low-density type II subgraphs, the highly abundant type I subgraphs cannot exist in isolation but must naturally aggregate into subgraph clusters. The identified topological framework may have important implications for our understanding of the origin and function of subgraphs in all complex networks.
| S-EPMC539752 | biostudies-literature
Project description:Complex networks have been shown to exhibit universal properties, with one of the most consistent patterns being the scale-free degree distribution, but are there regularities obeyed by the r-hop neighborhood in real networks? We answer this question by identifying another power-law pattern that describes the relationship between the fractions of node pairs C(r) within r hops and the hop count r. This scale-free distribution is pervasive and describes a large variety of networks, ranging from social and urban to technological and biological networks. In particular, inspired by the definition of the fractal correlation dimension D2 on a point-set, we consider the hop-count r to be the underlying distance metric between two vertices of the network, and we examine the scaling of C(r) with r. We find that this relationship follows a power-law in real networks within the range 2 ≤ r ≤ d, where d is the effective diameter of the network, that is, the 90-th percentile distance. We term this relationship as power-hop and the corresponding power-law exponent as power-hop exponent h. We provide theoretical justification for this pattern under successful existing network models, while we analyze a large set of real and synthetic network datasets and we show the pervasiveness of the power-hop.
| S-EPMC4790966 | biostudies-literature
Project description:We study the spatial evolutionary public goods game (SEPGG) with voluntary or optional participation on a complete graph (CG) and on dense networks. Based on analyses of the SEPGG rate equation on finite CG, we find that SEPGG has two stable states depending on the value of multiplication factor r, illustrating how the "tragedy of the commons" and "an anomalous state without any active participants" occurs in real-life situations. When r is low (<<), the state with only loners is stable, and the state with only defectors is stable when r is high (>>). We also derive the exact scaling relation for r*. All of the results are confirmed by numerical simulation. Furthermore, we find that a cooperator-dominant state emerges when the number of participants or the mean degree, 〈k〉, decreases. We also investigate the scaling dependence of the emergence of cooperation on r and 〈k〉. These results show how "tragedy of the commons" disappears when cooperation between egoistic individuals without any additional socioeconomic punishment increases.
| S-EPMC4369736 | biostudies-other
Project description:Trophic coherence, a measure of a graph's hierarchical organisation, has been shown to be linked to a graph's structural and dynamical aspects such as cyclicity, stability and normality. Trophic levels of vertices can reveal their functional properties, partition and rank the vertices accordingly. Trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, i.e. vertices with zero in-degree. Consequently, trophic analysis of graphs had been restricted until now. In this paper we introduce a hierarchical framework which can be defined on any simple graph. Within this general framework, we develop several metrics: hierarchical levels, a generalisation of the notion of trophic levels, influence centrality, a measure of a vertex's ability to influence dynamics, and democracy coefficient, a measure of overall feedback in the system. We discuss how our generalisation relates to previous attempts and what new insights are illuminated on the topological and dynamical aspects of graphs. Finally, we show how the hierarchical structure of a network relates to the incidence rate in a SIS epidemic model and the economic insights we can gain through it.
| S-EPMC8260706 | biostudies-literature
Project description:ObjectiveTinnitus is a prevalent hearing disorder, which could have a devastating impact on a patient's life. Functional studies have revealed connectivity pattern changes in the tinnitus brains that suggested a change of network dynamics as well as topological organization. However, no studies have yet provided evidence for the topological network changes in the gray matter. In this research, we aim to use the graph-theoretical approach to investigate the changes of topology in the tinnitus brain using structural MRI data, which could provide insights into the underlying anatomical basis for the neural mechanism in generating phantom sounds.MethodsWe collected 3D MRI images on 46 bilateral tinnitus patients and 46 age and gender-matched healthy controls. Brain networks were constructed with correlation matrices of the cortical thickness and subcortical volumes of 80 cortical/subcortical regions of interests. Global network properties were analyzed using local and global efficiency, clustering coefficient, and small-world coefficient, and regional network properties were evaluated using the betweenness coefficient for hub connectivity, and interregional correlations for edge properties. Between-group differences in cortical thickness and subcortical volumes were assessed using independent sample t-tests, and local efficiency, global efficiency, clustering coefficient, sigma, and interregional correlation were compared using non-parametric permutation tests.ResultsTinnitus was found to have increased global efficiency, local efficiency, and cluster coefficient, indicating generally heightened connectivity of the network. The small-world coefficient remained normal for tinnitus, indicating intact small-worldness. Betweenness centrality analysis showed that hubs in the amygdala and parahippocampus were only found for tinnitus but not controls. In contrast, hubs in the auditory cortex, insula, and thalamus were only found for controls but not tinnitus. Interregional correlation analysis further found in tinnitus enhanced connectivity between the auditory cortex and prefrontal lobe, and decreased connectivity of the insula with anterior cingulate gyrus and parahippocampus.ConclusionThese findings provided the first morphological evidence of altered topological organization of the brain networks in tinnitus. These alterations suggest that heightened efficiency of the brain network and altered auditory-limbic connection for tinnitus, which could be developed in compensation for the auditory deafferentation, leading to overcompensation and, ultimately, an emotional and cognitive burden.
| S-EPMC7267018 | biostudies-literature