Optimal paths in disordered complex networks

We study the optimal distance in networks, l(opt), defined as the length of the path minimizing the total weight, in the presence of disorder. Disorder is introduced by assigning random weights to the links or nodes. For strong disorder, where the maximal weight along the path dominates the sum, we find that l(opt) approximately N(1/3) in both Erdos-Rényi (ER) and Watts-Strogatz (WS) networks. For scale-free (SF) networks, with degree distribution P(k) approximately k(-lambda), we find that l(opt) scales as N((lambda-3)/(lambda-1)) for 3 or =4. Thus, for these networks, the small-world nature is destroyed. For 2相似文献   

Graph partitioning induced phase transitions

We study the percolation properties of graph partitioning on random regular graphs with N vertices of degree k. Optimal graph partitioning is directly related to optimal attack and immunization of complex networks. We find that for any partitioning process (even if nonoptimal) that partitions the graph into essentially equal sized connected components (clusters), the system undergoes a percolation phase transition at f = fc = 1-2/k where f is the fraction of edges removed to partition the graph. For optimal partitioning, at the percolation threshold, we find S approximately N 0.4 where S is the size of the clusters and l approximately N 0.25 where l is their diameter. Also, we find that S undergoes multiple nonpercolation transitions for f相似文献   

Optimal paths in disordered media: scaling of the crossover from self-similar to self-affine behavior

We study optimal paths in disordered energy landscapes using energy distributions of the type P(log(10) E)=const that lead to the strong disorder limit. If we truncate the distribution, so that P(log(10) E)=const only for E(min) < or =E < or =E(max), and P(log(10) E)=0 otherwise, we obtain a crossover from self-similar (strong disorder) to self-affine (moderate disorder) behavior at a path length l(x). We find that l(x) proportional, variant[log(10)(E(max)/E(min))](kappa), where the exponent kappa has the value kappa=1.60 +/- 0.03 both in d=2 and d=3. We show how the crossover can be understood from the distribution of local energies on the optimal paths.     

Phase diagram of the random Heisenberg antiferromagnetic spin-1 chain

We present a new perturbative real space renormalization group (RG) to study random quantum spin chains and other one-dimensional disordered quantum systems. The method overcomes problems of the original approach which fails for quantum random chains with spins larger than S=1/2. Since it works even for weak disorder, we are able to obtain the zero temperature phase diagram of the random antiferromagnetic Heisenberg spin-1 chain as a function of disorder. We find a random singlet phase for strong disorder. As the disorder decreases, the system shows a crossover from a Griffiths to a disordered Haldane phase.     

Breakdown of the internet under intentional attack

We study the tolerance of random networks to intentional attack, whereby a fraction p of the most connected sites is removed. We focus on scale-free networks, having connectivity distribution P(k) approximately k(-alpha), and use percolation theory to study analytically and numerically the critical fraction p(c) needed for the disintegration of the network, as well as the size of the largest connected cluster. We find that even networks with alpha < or = 3, known to be resilient to random removal of sites, are sensitive to intentional attack. We also argue that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.     

Potts model on complex networks

We consider the general p-state Potts model on random networks with a given degree distribution (random Bethe lattices). We find the effect of the suppression of a first order phase transition in this model when the degree distribution of the network is fat-tailed, that is, in more precise terms, when the second moment of the distribution diverges. In this situation the transition is continuous and of infinite order, and size effect is anomalously strong. In particular, in the case of p = 1, we arrive at the exact solution, which coincides with the known solution of the percolation problem on these networks.Received: 3 December 2003, Published online: 17 February 2004PACS: 05.10.-a Computational methods in statistical physics and nonlinear dynamics - 05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion - 05.50. + q Lattice theory and statistics (Ising, Potts, etc.) - 87.18.Sn Neural networks     

Multi-Type Directed Scale-Free Percolation

In this paper,we study a long-range percolation model on the lattice Z d with multi-type vertices and directed edges.Each vertex x ∈ Z d is independently assigned a non-negative weight Wx and a type ψx,where(Wx) x∈Z d are i.i.d.random variables,and(ψx) x∈Z d are also i.i.d.Conditionally on weights and types,and given λ,α 0,the edges are independent and the probability that there is a directed edge from x to y is given by pxy = 1 exp(λφψ x ψ y WxWy /| x-y | α),where φij 's are entries from a type matrix Φ.We show that,when the tail of the distribution of Wx is regularly varying with exponent τ-1,the tails of the out/in-degree distributions are both regularly varying with exponent γ = α(τ-1) /d.We formulate conditions under which there exist critical values λ WCC c ∈(0,∞) and λ SCC c ∈(0,∞) such that an infinite weak component and an infinite strong component emerge,respectively,when λ exceeds them.A phase transition is established for the shortest path lengths of directed and undirected edges in the infinite component at the point γ = 2,where the out/in-degrees switch from having finite to infinite variances.The random graph model studied here features some structures of multi-type vertices and directed edges which appear naturally in many real-world networks,such as the SNS networks and computer communication networks.     

Percolation and epidemic thresholds in clustered networks

We develop a theoretical approach to percolation in random clustered networks. We find that, although clustering in scale-free networks can strongly affect some percolation properties, such as the size and the resilience of the giant connected component, it cannot restore a finite percolation threshold. In turn, this implies the absence of an epidemic threshold in this class of networks, thus extending this result to a wide variety of real scale-free networks which shows a high level of transitivity. Our findings are in good agreement with numerical simulations.     

Crossover between universality classes in the statistics of rare events in disordered conductors

The crossover from orthogonal to the unitary universality classes in the distribution of the anomalously localized states (ALS) in two-dimensional disordered conductors is traced as a function of magnetic field. We demonstrate that the microscopic origin of the crossover is the change in the symmetry of the underlying disorder configurations that are responsible for ALS. These disorder configurations are of weak magnitude (compared to the Fermi energy) and of small size (compared to the mean free path). We find their shape explicitly by means of the direct optimal fluctuation method.     

Directed polymer – directed percolation transition: the strong disorder case

The transition of physical properties in disordered systems from strong disorder characteristics to weak disorder characteristics is studied for the directed polymer case. It is shown analytically that this transition is governed by the ratio (pc)/k, where is the probability density of the maximal bond of the optimal Min-Max path, pc is the critical probability of directed percolation, and k is the degree of disorder. This analytic result is found to be in agreement with numerical results related to this transition.     

Probability distribution for percolation clusters generated on a cayley tree at criticality

We present analytical and numerical results for the probability distributions of the number of sitesS as a function of the number of shellsl for several ensembles of percolation clusters generated on a Cayley tree at criticality. We find that for the incipient infinite percolation cluster the probability distribution isP(S¦l)~(S/l ⁴)exp(- aS/l ²) for Sl1.     

Minimum spanning trees on random networks

We show that the geometry of minimum spanning trees (MST) on random graphs is universal. Because of this geometric universality, we are able to characterize the energy of MST using a scaling distribution [P(epsilon)] found using uniform disorder. We show that the MST energy for other disorder distributions is simply related to P(epsilon). We discuss the relationship to invasion percolation, to the directed polymer in a random media, to uniform spanning trees, and also the implications for the broader issue of universality in disordered systems.     

Elementary models of dynamic networks

Inspecting the dynamics of networks opens a new dimension in understanding the interactions among the components of complex systems. Our goal is to understand the baseline properties expected from elementary random changes over time, in order to be able to assess the various effects found in longitudinal data. We created elementary dynamic models from classic random and preferential networks. Focusing on edge dynamics, we defined several processes for changing networks of a fixed size. We applied simple rules, including random, preferential and assortative modifications of existing edges – or a combination of these. Starting from initial Erdos-Rényi networks, we examined various basic network properties (e.g., density, clustering, average path length, number of components, degree distribution, etc.) of both snapshot and cumulative networks (for various lengths of aggregation time windows). Our results provide a baseline for changes to be expected in dynamic networks. We found universalities in the dynamic behavior of most network statistics. Furthermore, our findings suggest that certain network properties have a strong, non-trivial dependence on the length of the sampling window.     

Resilience of the internet to random breakdowns

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, P(k) = ck(-alpha). We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, p(c), that needs to be removed before the network disintegrates. We show analytically and numerically that for alpha0.99.     

Rounding by disorder of first-order quantum phase transitions: emergence of quantum critical points

We give a heuristic argument for disorder rounding of a first-order quantum phase transition into a continuous phase transition. From both weak and strong disorder analysis of the N-color quantum Ashkin-Teller model in one spatial dimension, we find that, for N > or =3, the first-order transition is rounded to a continuous transition and the physical picture is the same as the random transverse field Ising model for a limited parameter regime. The results are strikingly different from the corresponding classical problem in two dimensions where the fate of the renormalization group flows is a fixed point corresponding to N-decoupled pure Ising models.     

Minimal path on the hierarchical diamond lattice

We consider the minimal paths on a hierarchical diamond lattice, where bonds are assigned a random weight. Depending on the initial distribution of weights, we find all possible asymptotic scaling properties. The different cases found are the small-disorder case, the analog of Lévy's distributions with a power-law decay at-, and finally a limit of large disorder which can be identified as a percolation problem. The asymptotic shape of the stable distributions of weights of the minimal path are obtained, as well as their scaling properties. As a side result, we obtain the asymptotic form of the distribution of effective percolation thresholds for finite-size hierarchical lattices.     

Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements

We present a comparative network-theoretic analysis of the two largest global transportation networks: the worldwide air-transportation network (WAN) and the global cargo-ship network (GCSN). We show that both networks exhibit surprising statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segregate into two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest path trees for strongly weighted symmetric networks and show that in a shortest path tree representation the most significant features of both networks can be readily seen. We show that effective shortest path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.     

Robustness of a network of networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of n interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of n fully dependent Erd?s-Rényi (ER) networks, each of average degree k, we find that the giant component is P∞ =p[1-exp(-kP∞)](n) where 1-p is the initial fraction of removed nodes. This general result coincides for n = 1 with the known second-order phase transition for a single network. For any n>1 cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, P∞ depends also on the topology-in contrast to case (i). (iii) For a looplike network formed by n partially dependent ER networks, P∞ is independent of n.     

含随机裂纹网络孔隙材料渗透率的逾渗模型研究

采用逾渗理论对含随机裂纹网络的孔隙材料渗透性进行研究. 开裂孔隙材料渗透率的影响因素包括裂纹网络的几何特征、孔隙材料本体渗透率以及裂纹开度, 本文使用连续区逾渗理论模型建立了渗透率的标度律. 对于裂纹网络的几何特征, 本文基于连续区逾渗理论并考虑裂纹网络的分形特征提出了有限区域内二维随机裂纹网络的连通度定义; 对随机裂纹网络的几何分析表明, 随机裂纹局部团簇效应会降低裂纹网络的整体连通性, 随机裂纹网络的标度指数并非经典逾渗理论给出的固定值, 而是随着网络的分形维数的减小而增大. 本文在网络连通度和主裂纹团的曲折度的基础上, 提出了开裂孔隙材料渗透率标度律的解析表达, K=K₀(K_m,b)(ρ-ρ_c)^μ, 分别考虑了裂纹网络的几何逾渗特征 (ρ-ρ_c)^μ、孔隙材料渗透率K_m 以及裂纹开度比b; 对有限区域含有随机裂纹网络的孔隙材料渗透过程的有限元模拟表明, K₀ 在裂纹逾渗阈值附近与b呈指数关系, 但当裂纹的局部渗透率与K_m比值高于10⁶ 后, 开度比b对渗透率不再有影响.     

Variational Formulas and Cocycle solutions for Directed Polymer and Percolation Models

We discuss variational formulas for the law of large numbers limits of certain models of motion in a random medium: namely, the limiting time constant for last-passage percolation and the limiting free energy for directed polymers. The results are valid for models in arbitrary dimension, steps of the admissible paths can be general, the environment process is ergodic under spatial translations, and the potential accumulated along a path can depend on the environment and the next step of the path. The variational formulas come in two types: one minimizes over gradient-like cocycles, and another one maximizes over invariant measures on the space of environments and paths. Minimizing cocycles can be obtained from Busemann functions when these can be proved to exist. The results are illustrated through 1+1 dimensional exactly solvable examples, periodic examples, and polymers in weak disorder.