Mean first-passage time for maximal-entropy random walks in complex networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Lin Y
PROVIDER: S-EPMC4064359 | biostudies-other | 2014
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.
| S-EPMC5120342 | biostudies-literature
Project description:The first passage is a generic concept for quantifying when a random quantity such as the position of a diffusing molecule or the value of a stock crosses a preset threshold (target) for the first time. The last decade saw an enlightening series of new results focusing mostly on the so-called mean and global first passage time (MFPT and GFPT, respectively) of such processes. Here we push the understanding of first passage processes one step further. For a simple heterogeneous system we derive rigorously the complete distribution of first passage times (FPTs). Our results demonstrate that the typical FPT significantly differs from the MFPT, which corresponds to the long time behaviour of the FPT distribution. Conversely, the short time behaviour is shown to correspond to trajectories connecting directly from the initial value to the target. Remarkably, we reveal a previously overlooked third characteristic time scale of the first passage dynamics mirroring brief excursion away from the target.
| S-EPMC4745057 | biostudies-other
Project description:Persistence, defined as the probability that a signal has not reached a threshold up to a given observation time, plays a crucial role in the theory of random processes. Often, persistence decays algebraically with time with non trivial exponents. However, general analytical methods to calculate persistence exponents cannot be applied to the ubiquitous case of non-Markovian systems relaxing transiently after an imposed initial perturbation. Here, we introduce a theoretical framework that enables the non-perturbative determination of persistence exponents of Gaussian non-Markovian processes with non stationary dynamics relaxing to a steady state after an initial perturbation. Two situations are analyzed: either the system is subjected to a temperature quench at initial time, or its past trajectory is assumed to have been observed and thus known. Our theory covers the case of spatial dimension higher than one, opening the way to characterize non-trivial reaction kinetics for complex systems with non-equilibrium initial conditions.
| S-EPMC9463153 | biostudies-literature
Project description: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.
| S-EPMC2234100 | biostudies-literature
Project description:BackgroundThe concept of mean first-passage times (MFPTs) occupies an important place in the theory of stochastic processes, with the methods of their calculation being equally important in theoretical physics, chemistry and biology. We present here a software tool designed to support computational biology studies where Markovian dynamics takes place and MFPTs between initial and single or multiple final states in network-like systems are used. Two methods are made available for which their efficiency is strongly dependent on the topology of the defined network: the combinatorial Hill technique and the Monte Carlo simulation method.ResultsAfter a brief introduction to RaTrav, we highlight the utility of MFPT calculations by providing two examples (accompanied by Additional file 1) where they are deemed to be of importance: analysis of a protein-protein docking funnel and interpretation of the free energy transduction between two coupled enzymatic reactions controlled by the dynamics of transition between enzyme conformational states.ConclusionsRaTrav is a versatile and easy to use software tool for calculating MFPTs across biochemical networks. The user simply prepares a text file with the structure of a given network, along with some additional basic parameters such as transition probabilities, waiting probabilities (if any) and local times (weights of edges), which define explicitly the stochastic dynamics on the network. The RaTrav tool can then be applied in order to compute desired MFPTs. For the provided examples, we were able to find the favourable binding path within a protein-protein docking funnel and to calculate the degree of coupling for two chemical reactions catalysed simultaneously by the same protein enzyme. However, the list of possible applications is much wider.
| S-EPMC4222613 | biostudies-literature
Project description:Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyse random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyse the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both backtracking and visiting a neighbour of the previously visited node but do not avoid them completely.
| S-EPMC7735314 | biostudies-literature
Project description:The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on. The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times. Previously, however, there has been no general theory describing the distribution of possible paths followed by a random walk. Here, we show that for any random walk on a finite network, there are precisely three mutually exclusive possibilities for the form of the path distribution: finite, stretched exponential and power law. The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution. We use our theory to explain path distributions in domains such as sports, music, nonlinear dynamics and stochastic chemical kinetics.
| S-EPMC4214407 | biostudies-literature
Project description:BackgroundSeveral studies have demonstrated that synthetic lethal genetic interactions between gene mutations provide an indication of functional redundancy between molecular complexes and pathways. These observations help explain the finding that organisms are able to tolerate single gene deletions for a large majority of genes. For example, system-wide gene knockout/knockdown studies in S. cerevisiae and C. elegans revealed non-viable phenotypes for a mere 18% and 10% of the genome, respectively. It has been postulated that the low percentage of essential genes reflects the extensive amount of genetic buffering that occurs within genomes. Consistent with this hypothesis, systematic double-knockout screens in S. cerevisiae and C. elegans show that, on average, 0.5% of tested gene pairs are synthetic sick or synthetic lethal. While knowledge of synthetic lethal interactions provides valuable insight into molecular functionality, testing all combinations of gene pairs represents a daunting task for molecular biologists, as the combinatorial nature of these relationships imposes a large experimental burden. Still, the task of mapping pairwise interactions between genes is essential to discovering functional relationships between molecular complexes and pathways, as they form the basis of genetic robustness. Towards the goal of alleviating the experimental workload, computational techniques that accurately predict genetic interactions can potentially aid in targeting the most likely candidate interactions. Building on previous studies that analyzed properties of network topology to predict genetic interactions, we apply random walks on biological networks to accurately predict pairwise genetic interactions. Furthermore, we incorporate all published non-interactions into our algorithm for measuring the topological relatedness between two genes. We apply our method to S. cerevisiae and C. elegans datasets and, using a decision tree classifier, integrate diverse biological networks and show that our method outperforms established methods.ResultsBy applying random walks on biological networks, we were able to predict synthetic lethal interactions at a true positive rate of 95 percent against a false positive rate of 10 percent in S. cerevisiae. Similarly, in C. elegans, we achieved a true positive rate of 95 against a false positive rate of 7 percent. Furthermore, we demonstrate that the inclusion of non-interacting gene pairs results in a considerable performance improvement.ConclusionWe presented a method based on random walks that accurately captures aspects of network topology towards the goal of classifying potential genetic interactions as either synthetic lethal or non-interacting. Our method, which is generalizable to all types of biological networks, is likely to perform well with limited information, as estimated by holding out large portions of the synthetic lethal interactions and non-interactions.
| S-EPMC2653491 | biostudies-literature
Project description:MotivationAccurately representing biological networks in a low-dimensional space, also known as network embedding, is a critical step in network-based machine learning and is carried out widely using node2vec, an unsupervised method based on biased random walks. However, while many networks, including functional gene interaction networks, are dense, weighted graphs, node2vec is fundamentally limited in its ability to use edge weights during the biased random walk generation process, thus under-using all the information in the network.ResultsHere, we present node2vec+, a natural extension of node2vec that accounts for edge weights when calculating walk biases and reduces to node2vec in the cases of unweighted graphs or unbiased walks. Using two synthetic datasets, we empirically show that node2vec+ is more robust to additive noise than node2vec in weighted graphs. Then, using genome-scale functional gene networks to solve a wide range of gene function and disease prediction tasks, we demonstrate the superior performance of node2vec+ over node2vec in the case of weighted graphs. Notably, due to the limited amount of training data in the gene classification tasks, graph neural networks such as GCN and GraphSAGE are outperformed by both node2vec and node2vec+.Availability and implementationThe data and code are available on GitHub at https://github.com/krishnanlab/node2vecplus_benchmarks. All additional data underlying this article are available on Zenodo at https://doi.org/10.5281/zenodo.7007164.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC9891245 | biostudies-literature
Project description:Motile cells often explore natural environments characterized by a high degree of structural complexity. Moreover cell motility is also intrinsically noisy due to spontaneous random reorientations and speed fluctuations. This interplay of internal and external noise sources gives rise to a complex dynamical behavior that can be strongly sensitive to details and hard to model quantitatively. In striking contrast to this general picture we show that the mean residence time of swimming bacteria inside artificial complex microstructures is quantitatively predicted by a generic invariance property of random walks. We find that while external shape and internal disorder have dramatic effects on the distributions of path lengths and residence times, the corresponding mean values are constrained by the sole free surface to perimeter ratio. As a counterintuitive consequence, bacteria escape faster from structures with higher density of obstacles due to the lower accessible surface.
| S-EPMC6547659 | biostudies-literature