Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Path and Minimal Spanning Trees in Random Weighted Networks
65
0
0.0
(
0
)
Added by
Lidia A. Braunstein
Publication date
2006
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We review results on the scaling of the optimal path length in random networks with weighted links or nodes. In strong disorder we find that the length of the optimal path increases dramatically compared to the known small world result for the minimum distance. For ErdH{o}s-Renyi (ER) and scale free networks (SF), with parameter $lambda$ ($lambda >3$), we find that the small-world nature is destroyed. We also find numerically that for weak disorder the length of the optimal path scales logaritmically with the size of the networks studied. We also review the transition between the strong and weak disorder regimes in the scaling properties of the length of the optimal path for ER and SF networks and for a general distribution of weights, and suggest that for any distribution of weigths, the distribution of optimal path lengths has a universal form which is controlled by the scaling parameter $Z=ell_{infty}/A$ where $A$ plays the role of the disorder strength, and $ell_{infty}$ is the length of the optimal path in strong disorder. The relation for $A$ is derived analytically and supported by numerical simulations. We then study the minimum spanning tree (MST) and show that it is composed of percolation clusters, which we regard as super-nodes, connected by a scale-free tree. We furthermore show that the MST can be partitioned into two distinct components. One component the {it superhighways}, for which the nodes with high centrality dominate, corresponds to the largest cluster at the percolation threshold which is a subset of the MST. In the other component, {it roads}, low centrality nodes dominate. We demonstrate the significance identifying the superhighways by showing that one can improve significantly the global transport by improving a very small fraction of the network.
rate research
Read More
A complete understanding of real networks requires us to understand the consequences of the uneven interaction strengths between a systems components. Here we use the minimum spanning tree (MST) to explore the effect of weight assignment and network topology on the organization of complex networks. We find that if the weight distribution is correlated with the network topology, the MSTs are either scale-free or exponential. In contrast, when the correlations between weights and topology are absent, the MST degree distribution is a power-law and independent of the weight distribution. These results offer a systematic way to explore the impact of weak links on the structure and integrity of complex networks.
In this work we study of the dynamics of large size random neural networks. Different methods have been developed to analyse their behavior, most of them rely on heuristic methods based on Gaussian assumptions regarding the fluctuations in the limit of infinite sizes. These approaches, however, do not justify the underlying assumptions systematically. Furthermore, they are incapable of deriving in general the stability of the derived mean field equations, and they are not amenable to analysis of finite size corrections. Here we present a systematic method based on Path Integrals which overcomes these limitations. We apply the method to a large non-linear rate based neural network with random asymmetric connectivity matrix. We derive the Dynamic Mean Field (DMF) equations for the system, and derive the Lyapunov exponent of the system. Although the main results are well known, here for the first time, we calculate the spectrum of fluctuations around the mean field equations from which we derive the general stability conditions for the DMF states. The methods presented here, can be applied to neural networks with more complex dynamics and architectures. In addition, the theory can be used to compute systematic finite size corrections to the mean field equations.
We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-Renyi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as $N^{alpha}$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance $d=lfloor 1/alpha rfloor$ from each other. The distribution of shortest path lengths between nodes of degree $m$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of $m$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.
Given a compact $E subset mathbb{R}^n$ and $s > 0$, the maximum distance problem seeks a compact and connected subset of $mathbb{R}^n$ of smallest one dimensional Hausdorff measure whose $s$-neighborhood covers $E$. For $Esubset mathbb{R}^2$, we prove that minimizing over minimum spanning trees that connect the centers of balls of radius $s$, which cover $E$, solves the maximum distance problem. The main difficulty in proving this result is overcome by the proof of Lemma 3.5, which states that one is able to cover the $s$-neighborhood of a Lipschitz curve $Gamma$ in $mathbb{R}^2$ with a finite number of balls of radius $s$, and connect their centers with another Lipschitz curve $Gamma_ast$, where $mathcal{H}^1(Gamma_ast)$ is arbitrarily close to $mathcal{H}^1(Gamma)$. We also present an open source package for computational exploration of the maximum distance problem using minimum spanning trees, available at https://github.com/mtdaydream/MDP_MST.
Despite their apparent simplicity, random Boolean networks display a rich variety of dynamical behaviors. Much work has been focused on the properties and abundance of attractors. The topologies of random Boolean networks with one input per node can be seen as graphs of random maps. We introduce an approach to investigating random maps and finding analytical results for attractors in random Boolean networks with the corresponding topology. Approximating some other non-chaotic networks to be of this class, we apply the analytic results to them. For this approximation, we observe a strikingly good agreement on the numbers of attractors of various lengths. We also investigate observables related to the average number of attractors in relation to the typical number of attractors. Here, we find strong differences that highlight the difficulties in making direct comparisons between random Boolean networks and real systems. Furthermore, we demonstrate the power of our approach by deriving some results for random maps. These results include the distribution of the number of components in random maps, along with asymptotic expansions for cumulants up to the 4th order.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
