Browse
Submit Data
Databases
API
Help

Dataset Information

31 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Graph distance for complex networks.

ABSTRACT: 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.

SUBMITTER: Shimada Y

PROVIDER: S-EPMC5057156 | biostudies-literature | 2016 Oct

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Graph distance for complex networks.

Shimada Yutaka Y Hirata Yoshito Y Ikeguchi Tohru T Aihara Kazuyuki K

Scientific reports 20161011

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 m ...[more]

PMID: 27725690

Similar Datasets

The distance backbone of complex networks.

Project description:Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges-those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.

| S-EPMC10859673 | biostudies-literature

Exponential random graph modeling for complex brain networks.

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

Input graph: the hidden geometry in controlling complex networks.

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

Supervised learning of gene-regulatory networks based on graph distance profiles of transcriptomics data.

Project description:Characterisation of gene-regulatory network (GRN) interactions provides a stepping stone to understanding how genes affect cellular phenotypes. Yet, despite advances in profiling technologies, GRN reconstruction from gene expression data remains a pressing problem in systems biology. Here, we devise a supervised learning approach, GRADIS, which utilises support vector machine to reconstruct GRNs based on distance profiles obtained from a graph representation of transcriptomics data. By employing the data from Escherichia coli and Saccharomyces cerevisiae as well as synthetic networks from the DREAM4 and five network inference challenges, we demonstrate that our GRADIS approach outperforms the state-of-the-art supervised and unsupervided approaches. This holds when predictions about target genes for individual transcription factors as well as for the entire network are considered. We employ experimentally verified GRNs from E. coli and S. cerevisiae to validate the predictions and obtain further insights in the performance of the proposed approach. Our GRADIS approach offers the possibility for usage of other network-based representations of large-scale data, and can be readily extended to help the characterisation of other cellular networks, including protein-protein and protein-metabolite interactions.

| S-EPMC7327016 | biostudies-literature

GraphSNP: an interactive distance viewer for investigating outbreaks and transmission networks using a graph approach.

Project description:BackgroundCluster and transmission analysis utilising pairwise SNP distance are increasingly used in genomic epidemiological studies. However, current methods are often challenging to install and use, and lack interactive functionalities for easy data exploration.ResultsGraphSNP is an interactive visualisation tool running in a web browser that allows users to rapidly generate pairwise SNP distance networks, investigate SNP distance distributions, identify clusters of related organisms, and reconstruct transmission routes. The functionality of GraphSNP is demonstrated using examples from recent multi-drug resistant bacterial outbreaks in healthcare settings.ConclusionsGraphSNP is freely available at https://github.com/nalarbp/graphsnp . An online version of GraphSNP, including demonstration datasets, input templates, and quick start guide is available for use at https://graphsnp.fordelab.com .

| S-EPMC10199467 | biostudies-literature

Generalised power graph compression reveals dominant relationship patterns in complex networks.

Project description:We introduce a framework for the discovery of dominant relationship patterns in complex networks, by compressing the networks into power graphs with overlapping power nodes. When paired with enrichment analysis of node classification terms, the most compressible sets of edges provide a highly informative sketch of the dominant relationship patterns that define the network. In addition, this procedure also gives rise to a novel, link-based definition of overlapping node communities in which nodes are defined by their relationships with sets of other nodes, rather than through connections within the community. We show that this completely general approach can be applied to undirected, directed, and bipartite networks, yielding valuable insights into the large-scale structure of real-world networks, including social networks and food webs. Our approach therefore provides a novel way in which network architecture can be studied, defined and classified.

| S-EPMC3964517 | biostudies-other

The effect of genome graph expressiveness on the discrepancy between genome graph distance and string set distance.

Project description:MotivationIntra-sample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets.ResultsWe extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Mover's Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upper-bound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated T-cell receptor sequences and actual Hepatitis B virus genomes, we show that the diameter-corrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%.Availability and implementationData and source code for reproducing the experiments are available at: https://github.com/Kingsford-Group/gtedemedtest/.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC9235494 | biostudies-literature

Spatial evolutionary public goods game on complete graph and dense complex networks.

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

Graph hierarchy: a novel framework to analyse hierarchical structures in complex networks.

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

Graph diffusion distance: Properties and efficient computation.

Project description:We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponential matrices, under norm-preserving and sparsity constraints. Variants of the distance metric are introduced to consider such optimized maps under sparsity constraints as well as fixed time-scaling between the two Laplacians. The objective function of this optimization is multimodal and has discontinuous slope, and is hence difficult for univariate optimizers to solve. We demonstrate a novel procedure for efficiently calculating these optima for two of our distance measure variants. We present numerical experiments demonstrating that (a) upper bounds of our distance metrics can be used to distinguish between lineages of related graphs; (b) our procedure is faster at finding the required optima, by as much as a factor of 103; and (c) the upper bounds satisfy the triangle inequality exactly under some assumptions and approximately under others. We also derive an upper bound for the distance between two graph products, in terms of the distance between the two pairs of factors. Additionally, we present several possible applications, including the construction of infinite "graph limits" by means of Cauchy sequences of graphs related to one another by our distance measure.

| S-EPMC8078789 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data