Do you want to publish a course? Click here

Minimum spanning trees on weighted scale-free networks

200   0   0.0 ( 0 )
 Added by Eivind Almaas
 Publication date 2004
  fields Physics
and research's language is English




Ask ChatGPT about the research

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.



rate research

Read More

The studies based on $A+A rightarrow emptyset$ and $A+Brightarrow emptyset$ diffusion-annihilation processes have so far been studied on weighted uncorrelated scale-free networks and fractal scale-free networks. In the previous reports, it is widely accepted that the segregation of particles in the processes is introduced by the fractal structure. In this paper, we study these processes on a family of weighted scale-free networks with identical degree sequence. We find that the depletion zone and segregation are essentially caused by the disassortative mixing, namely, high-degree nodes tend to connect with low-degree nodes. Their influence on the processes is governed by the correlation between the weight and degree. Our finding suggests both the weight and degree distribution dont suffice to characterize the diffusion-annihilation processes on weighted scale-free networks.
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.
115 - T. S. Jackson , N. Read 2009
Continuing the program begun by the authors in a previous paper, we develop an exact low-density expansion for the random minimum spanning tree (MST) on a finite graph, and use it to develop a continuum perturbation expansion for the MST on critical percolation clusters in space dimension d. The perturbation expansion is proved to be renormalizable in d=6 dimensions. We consider the fractal dimension D_p of paths on the latter MST; our previous results lead us to predict that D_p=2 for d>d_c=6. Using a renormalization-group approach, we confirm the result for d>6, and calculate D_p to first order in epsilon=6-d for dleq 6 using the connection with critical percolation, with the result D_p = 2 - epsilon/7 + O(epsilon^2).
We investigate analytically and numerically the critical line in undirected random Boolean networks with arbitrary degree distributions, including scale-free topology of connections $P(k)sim k^{-gamma}$. We show that in infinite scale-free networks the transition between frozen and chaotic phase occurs for $3<gamma < 3.5$. The observation is interesting for two reasons. First, since most of critical phenomena in scale-free networks reveal their non-trivial character for $gamma<3$, the position of the critical line in Kauffman model seems to be an important exception from the rule. Second, since gene regulatory networks are characterized by scale-free topology with $gamma<3$, the observation that in finite-size networks the mentioned transition moves towards smaller $gamma$ is an argument for Kauffman model as a good starting point to model real systems. We also explain that the unattainability of the critical line in numerical simulations of classical random graphs is due to percolation phenomena.
Scale-free networks with topology-dependent interactions are studied. It is shown that the universality classes of critical behavior, which conventionally depend only on topology, can also be explored by tuning the interactions. A mapping, $gamma = (gamma - mu)/(1-mu)$, describes how a shift of the standard exponent $gamma$ of the degree distribution $P(q)$ can absorb the effect of degree-dependent pair interactions $J_{ij} propto (q_iq_j)^{-mu}$. Replica technique, cavity method and Monte Carlo simulation support the physical picture suggested by Landau theory for the critical exponents and by the Bethe-Peierls approximation for the critical temperature. The equivalence of topology and interaction holds for equilibrium and non-equilibrium systems, and is illustrated with interdisciplinary applications.
comments
Fetching comments Fetching comments
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا