Ring structures and mean first passage time in networks

Reinforcement learning with thermal fluctuations at the nanoscale

Reinforcement Learning offers a framework to learn to choose actions in order to control a system. However, at small scales Brownian fluctuations limit the control of nanomachine actuation or nanonavigation and of the molecular machinery of life. We analyze this regime using the general framework of Markov decision processes. We show that at the nanoscale, while optimal control actions should bring an improvement proportional to the small ratio of the applied force times a length scale over the temperature, the learned improvement is smaller and proportional to the square of this small ratio. Consequently, the efficiency of learning, which compares the learning improvement to the theoretical optimal improvement, drops to zero. Nevertheless, these limitations can be circumvented by using actions learned at a lower temperature. These results are illustrated with simulations of the control of the shape of small particle clusters.

XGDAG: explainable gene-disease associations via graph neural networks

MOTIVATION

Disease gene prioritization consists in identifying genes that are likely to be involved in the mechanisms of a given disease, providing a ranking of such genes. Recently, the research community has used computational methods to uncover unknown gene-disease associations; these methods range from combinatorial to machine learning-based approaches. In particular, during the last years, approaches based on deep learning have provided superior results compared to more traditional ones. Yet, the problem with these is their inherent black-box structure, which prevents interpretability.

RESULTS

We propose a new methodology for disease gene discovery, which leverages graph-structured data using graph neural networks (GNNs) along with an explainability phase for determining the ranking of candidate genes and understanding the model's output. Our approach is based on a positive-unlabeled learning strategy, which outperforms existing gene discovery methods by exploiting GNNs in a non-black-box fashion. Our methodology is effective even in scenarios where a large number of associated genes need to be retrieved, in which gene prioritization methods often tend to lose their reliability.

AVAILABILITY AND IMPLEMENTATION

The source code of XGDAG is available on GitHub at: https://github.com/GiDeCarlo/XGDAG. The data underlying this article are available at: https://www.disgenet.org/, https://thebiogrid.org/, https://doi.org/10.1371/journal.pcbi.1004120.s003, and https://doi.org/10.1371/journal.pcbi.1004120.s004.

Controlling the Shape of Small Clusters with and without Macroscopic Fields

Despite major advances in the understanding of the formation and dynamics of nanoclusters in the past decades, theoretical bases for the control of their shape are still lacking. We investigate strategies for driving fluctuating few-particle clusters to an arbitrary target shape in minimum time with or without an external field. This question is recast into a first passage problem, solved numerically, and discussed within a high temperature expansion. Without field, large-enough low-energy target shapes exhibit an optimal temperature at which they are reached in minimum time. We then compute the optimal way to set an external field to minimize the time to reach the target, leading to a gain of time that grows when increasing cluster size or decreasing temperature. This gain can shift the optimal temperature or even create one. Our results could apply to clusters of atoms at equilibrium, and colloidal or nanoparticle clusters under thermo- or electrophoresis.

Random walks on activity-driven networks with attractiveness

Virtually all real-world networks are dynamical entities. In social networks, the propensity of nodes to engage in social interactions (activity) and their chances to be selected by active nodes (attractiveness) are heterogeneously distributed. Here, we present a time-varying network model where each node and the dynamical formation of ties are characterized by these two features. We study how these properties affect random-walk processes unfolding on the network when the time scales describing the process and the network evolution are comparable. We derive analytical solutions for the stationary state and the mean first-passage time of the process, and we study cases informed by empirical observations of social networks. Our work shows that previously disregarded properties of real social systems, such as heterogeneous distributions of activity and attractiveness as well as the correlations between them, substantially affect the dynamical process unfolding on the network.

Temporal-varying failures of nodes in networks

We consider networks in which random walkers are removed because of the failure of specific nodes. We interpret the rate of loss as a measure of the importance of nodes, a notion we denote as failure centrality. We show that the degree of the node is not sufficient to determine this measure and that, in a first approximation, the shortest loops through the node have to be taken into account. We propose approximations of the failure centrality which are valid for temporal-varying failures, and we dwell on the possibility of externally changing the relative importance of nodes in a given network by exploiting the interference between the loops of a node and the cycles of the temporal pattern of failures. In the limit of long failure cycles we show analytically that the escape in a node is larger than the one estimated from a stochastic failure with the same failure probability. We test our general formalism in two real-world networks (air-transportation and e-mail users) and show how communities lead to deviations from predictions for failures in hubs.

Optimal search strategies on complex multi-linked networks

In this paper we consider the problem of optimal search strategies on multi-linked networks, i.e. graphs whose nodes are endowed with several independent sets of links. We focus preliminarily on agents randomly hopping along the links of a graph, with the additional possibility of performing non-local hops to randomly chosen nodes with a given probability. We show that an optimal combination of the two jump rules exists that maximises the efficiency of target search, the optimum reflecting the topology of the network. We then generalize our results to multi-linked networks with an arbitrary number of mutually interfering link sets.

Hitting and trapping times on branched structures

In this work we consider a simple random walk embedded in a generic branched structure and we find a close-form formula to calculate the hitting time H(i,f) between two arbitrary nodes i and j. We then use this formula to obtain the set of hitting times {H(i,f)} for combs and their expectation values, namely, the mean first-passage time, where the average is performed over the initial node while the final node f is given, and the global mean first-passage time, where the average is performed over both the initial and the final node. Finally, we discuss applications in the context of reaction-diffusion problems.

Characteristic times of biased random walks on complex networks

We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree k is proportional to k(α), where α is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely (i) the time the walker needs to come back to the starting node, (ii) the time it takes to visit a given node for the first time, and (iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of α which minimizes the three characteristic times differs from the value α(min)=-1 analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of α(min) in the range [-1,-0.5], while disassortative networks have α(min) in the range [-0.5,0]. We derive an analytical relation between the degree correlation exponent ν and the optimal bias value α(min), which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks by means of an appropriate tuning of the motion bias.

Anomalous biased diffusion in networks

We study diffusion with a bias toward a target node in networks. This problem is relevant to efficient routing strategies in emerging communication networks like optical networks. Bias is represented by a probability p of the packet or particle to travel at every hop toward a site that is along the shortest path to the target node. We investigate the scaling of the mean first passage time (MFPT) with the size of the network. We find by using theoretical analysis and computer simulations that for random regular (RR) and Erdős-Rényi networks, there exists a threshold probability, p(th), such that for p<p(th) the MFPT scales anomalously as N(α), where N is the number of nodes, and α depends on p. For p>p(th), the MFPT scales logarithmically with N. The threshold value p(th) of the bias parameter for which the regime transition occurs is found to depend only on the mean degree of the nodes. An exact solution for every value of p is given for the scaling of the MFPT in RR networks. The regime transition is also observed for the second moment of the probability distribution function, the standard deviation. For the case of scale-free (SF) networks, we present analytical bounds and simulations results showing that the MFPT scales at most as lnN to a positive power for any finite bias, which means that in SF networks even a very small bias is considerably more efficient in comparison to unbiased walk.

Spectral coarse graining for random walks in bipartite networks

Many real-world networks display a natural bipartite structure, yet analyzing and visualizing large bipartite networks is one of the open challenges in complex network research. A practical approach to this problem would be to reduce the complexity of the bipartite system while at the same time preserve its functionality. However, we find that existing coarse graining methods for monopartite networks usually fail for bipartite networks. In this paper, we use spectral analysis to design a coarse graining scheme specific for bipartite networks, which keeps their random walk properties unchanged. Numerical analysis on both artificial and real-world networks indicates that our coarse graining can better preserve most of the relevant spectral properties of the network. We validate our coarse graining method by directly comparing the mean first passage time of the walker in the original network and the reduced one.

Random walks on temporal networks

Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various time scales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as a paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.

Accuracy of mean-field theory for dynamics on real-world networks

Mean-field analysis is an important tool for understanding dynamics on complex networks. However, surprisingly little attention has been paid to the question of whether mean-field predictions are accurate, and this is particularly true for real-world networks with clustering and modular structure. In this paper, we compare mean-field predictions to numerical simulation results for dynamical processes running on 21 real-world networks and demonstrate that the accuracy of such theory depends not only on the mean degree of the networks but also on the mean first-neighbor degree. We show that mean-field theory can give (unexpectedly) accurate results for certain dynamics on disassortative real-world networks even when the mean degree is as low as 4.

The unreasonable effectiveness of tree-based theory for networks with clustering

We demonstrate that a tree-based theory for various dynamical processes operating on static, undirected networks yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance ℓ is sufficiently small--that is, as long as it is close to the value of ℓ in a random network with negligible clustering and the same degree-degree correlations. We support this hypothesis numerically using both real-world networks from various domains and several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks, provided that the networks are "sufficiently small" worlds.

Influence of zero range process interaction on diffusion

We study the aspects of diffusion for the case of zero range process interaction on scale-free networks, through statistical quantities such as the mean first passage time, coverage, mean square displacement etc., and pay attention to how the interaction, especially the resulted condensation, influences the diffusion. By mean-field theory we show that the statistical quantities of diffusion can be significantly reduced by the condensation and can be figured out by the waiting time of a particle staying at a node. Numerical simulations have confirmed the theoretical predictions.

Diffusion dynamics and first passage time in a two-coupled pendulum system

We present the numerical investigation of diffusion process and features of first passage time (FPT) and mean FPT (MFPT) in a two-coupled damped and periodically driven pendulum system. The effect of amplitude of the external periodic force and phase of the force on diffusion constant, distribution of FPT, P(tFPT), and MFPT is analyzed. Normal diffusion is found. Diffusion constant is found to show power-law variation near intermittency and sudden widening crises while linear variation is observed in the quasiperiodic region. In the intermittency crisis the divergence of diffusion constant is similar to the divergence of mean bursting length. P(tFPT) of critical distances of state variable exhibit periodic multiple peaks with decaying amplitude. MFPT of critical distances also follows power-law variation. Diffusion constant and MFPT are sensitive to the phase factor of the periodic force.

Mean-field diffusive dynamics on weighted networks

Diffusion is a key element of a large set of phenomena occurring on natural and social systems modeled in terms of complex weighted networks. Here, we introduce a general formalism that allows to easily write down mean-field equations for any diffusive dynamics on weighted networks. We also propose the concept of annealed weighted networks, in which such equations become exact. We show the validity of our approach addressing the problem of the random walk process, pointing out a strong departure of the behavior observed in quenched real scale-free networks from the mean-field predictions. Additionally, we show how to employ our formalism for more complex dynamics. Our work sheds light on mean-field theory on weighted networks and on its range of validity, and warns about the reliability of mean-field results for complex dynamics.

Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs

We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdös-Rényi graphs. Using the tree approach, which is expected to be exact in the large graph limit, we show how to solve for the distribution of these quantities and we find that these distributions exhibit a form of self-similarity.

Trapping in scale-free networks with hierarchical organization of modularity

A wide variety of real-life networks share two remarkable generic topological properties: scale-free behavior and modular organization, and it is natural and important to study how these two features affect the dynamical processes taking place on such networks. In this paper, we investigate a simple stochastic process--trapping problem, a random walk with a perfect trap fixed at a given location, performed on a family of hierarchical networks that exhibit simultaneously striking scale-free and modular structure. We focus on a particular case with the immobile trap positioned at the hub node having the largest degree. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping problem, which is the mean of the node-to-trap first-passage time over the entire network. The exact expression for the MFPT is calculated through the recurrence relations derived from the special construction of the hierarchical networks. The obtained rigorous formula corroborated by extensive direct numerical calculations exhibits that the MFPT grows algebraically with the network order. Concretely, the MFPT increases as a power-law function of the number of nodes with the exponent much less than 1. We demonstrate that the hierarchical networks under consideration have more efficient structure for transport by diffusion in contrast with other analytically soluble media including some previously studied scale-free networks. We argue that the scale-free and modular topologies are responsible for the high efficiency of the trapping process on the hierarchical networks.

Structure of shells in complex networks

We define shell l in a network as the set of nodes at distance l with respect to a given node and define rl as the fraction of nodes outside shell l . In a transport process, information or disease usually diffuses from a random node and reach nodes shell after shell. Thus, understanding the shell structure is crucial for the study of the transport property of networks. We study the statistical properties of the shells of a randomly chosen node. For a randomly connected network with given degree distribution, we derive analytically the degree distribution and average degree of the nodes residing outside shell l as a function of rl. Further, we find that rl follows an iterative functional form rl=phi(rl-1) , where phi is expressed in terms of the generating function of the original degree distribution of the network. Our results can explain the power-law distribution of the number of nodes Bl found in shells with l larger than the network diameter d , which is the average distance between all pairs of nodes. For real-world networks the theoretical prediction of rl deviates from the empirical rl. We introduce a network correlation function c(rl) identical with rl/phi(rl-1) to characterize the correlations in the network, where rl is the empirical value and phi(rl-1) is the theoretical prediction. c(rl)=1 indicates perfect agreement between empirical results and theory. We apply c(rl) to several model and real-world networks. We find that the networks fall into two distinct classes: (i) a class of poorly connected networks with c(rl)>1 , where a larger (smaller) fraction of nodes resides outside (inside) distance l from a given node than in randomly connected networks with the same degree distributions. Examples include the Watts-Strogatz model and networks characterizing human collaborations such as citation networks and the actor collaboration network; (ii) a class of well-connected networks with c(rl)<1 . Examples include the Barabási-Albert model and the autonomous system Internet network.

Bosonic reaction-diffusion processes on scale-free networks

Reaction-diffusion processes can be adopted to model a large number of dynamics on complex networks, such as transport processes or epidemic outbreaks. In most cases, however, they have been studied from a fermionic perspective, in which each vertex can be occupied by at most one particle. While still useful, this approach suffers from some drawbacks, the most important probably being the difficulty to implement reactions involving more than two particles simultaneously. Here we develop a general framework for the study of bosonic reaction-diffusion processes on complex networks, in which there is no restriction on the number of interacting particles that a vertex can host. We describe these processes theoretically by means of continuous-time heterogeneous mean-field theory and divide them into two main classes: steady-state and monotonously decaying processes. We analyze specific examples of both behaviors within the class of one-species processes, comparing the results (whenever possible) with the corresponding fermionic counterparts. We find that the time evolution and critical properties of the particle density are independent of the fermionic or bosonic nature of the process, while differences exist in the functional form of the density of occupied vertices in a given degree class k . We implement a continuous-time Monte Carlo algorithm, well suited for general bosonic simulations, which allows us to confirm the analytical predictions formulated within mean-field theory. Our results, at both the theoretical and numerical levels, can be easily generalized to tackle more complex, multispecies, reaction-diffusion processes and open a promising path for a general study and classification of this kind of dynamical systems on complex networks.

Random walks on complex trees

We study the properties of random walks on complex trees. We observe that the absence of loops is reflected in physical observables showing large differences with respect to their looped counterparts. First, both the vertex discovery rate and the mean topological displacement from the origin present a considerable slowing down in the tree case. Second, the mean first passage time (MFPT) displays a logarithmic degree dependence, in contrast to the inverse degree shape exhibited in looped networks. This deviation can be ascribed to the dominance of source-target topological distance in trees. To show this, we study the distance dependence of a symmetrized MFPT and derive its logarithmic profile, obtaining good agreement with simulation results. These unique properties shed light on the recently reported anomalies observed in diffusive dynamical systems on trees.

Exact mean first-passage time on the T-graph

We consider a simple random walk on the T-fractal and we calculate the exact mean time taug to first reach the central node i0. The mean is performed over the set of possible walks from a given origin and over the set of starting points uniformly distributed throughout the sites of the graph, except i0. By means of analytic techniques based on decimation procedures, we find the explicit expression for taug as a function of the generation g and of the volume V of the underlying fractal. Our results agree with the asymptotic ones already known for diffusion on the T-fractal and, more generally, they are consistent with the standard laws describing diffusion on low-dimensional structures.

Distance distribution in random graphs and application to network exploration

We consider the problem of determining the proportion of edges that are discovered in an Erdos-Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.

Spectral coarse graining of complex networks

Reducing the complexity of large systems described as complex networks is key to understanding them and a crucial issue is to know which properties of the initial system are preserved in the reduced one. Here we use random walks to design a coarse graining scheme for complex networks. By construction the coarse graining preserves the slow modes of the walk, while reducing significantly the size and the complexity of the network. In this sense our coarse graining allows us to approximate large networks by smaller ones, keeping most of their relevant spectral properties.