Metastable states of spin glasses on random thin graphs

In this paper we calculate the mean number of metastable states for spin glasses on so called random thin graphs with couplings taken from a symmetric binary distribution . Thin graphs are graphs where the local connectivity of each site is fixed to some value c. As in totally connected mean field models we find that the number of metastable states increases exponentially with the system size. Furthermore we find that the average number of metastable states decreases as c in agreement with previous studies showing that finite connectivity corrections of order 1/c increase the number of metastable states with respect to the totally connected mean field limit. We also prove that the average number of metastable states in the limit is finite and converges to the average number of metastable states in the Sherrington-Kirkpatrick model. An annealed calculation for the number of metastable states of energy E is also carried out giving a lower bound on the ground state energy of these spin glasses. For small c one may obtain analytic expressions for . Received 14 October 1999 and Received in final form 14 December 1999     

干涉项对e~+e~-→q+ng两种色连接几率的影响

传统高能e+ e-→hadrons事例产生器普遍采用大Nc 近似 ,使色单态链产生几率达到 10 0 %而色分离态几率为 0 .本文在Nc=3的真实情况下 ,研究了干涉项中颜色部分和动量部分的来源及性质后发现 ,对e+ e-→qq +ng部分子末态中胶子数 2 ,3,干涉项使色单态链产生几率进一步下降到 6 7% ,5 8% ,而n =2时的色分离态几率则增大至不考虑干涉项的 2倍 .由上推断当胶子数n更大时色单态链几率将远小于 1,色分离态几率将更显著增加     

Structure of growing networks with preferential linking

The model of growing networks with the preferential attachment of new links is generalized to include initial attractiveness of sites. We find the exact form of the stationary distribution of the number of incoming links of sites in the limit of long times, P(q), and the long-time limit of the average connectivity q(s,t) of a site s at time t (one site is added per unit of time). At long times, P(q) approximately q(-gamma) at q-->infinity and q(s,t) approximately (s/t)(-beta) at s/t-->0, where the exponent gamma varies from 2 to infinity depending on the initial attractiveness of sites. We show that the relation beta(gamma-1) = 1 between the exponents is universal.     

Transport Efficiency of Continuous-Time Quantum Walks on Graphs

Continuous-time quantum walk describes the propagation of a quantum particle (or an excitation) evolving continuously in time on a graph. As such, it provides a natural framework for modeling transport processes, e.g., in light-harvesting systems. In particular, the transport properties strongly depend on the initial state and specific features of the graph under investigation. In this paper, we address the role of graph topology, and investigate the transport properties of graphs with different regularity, symmetry, and connectivity. We neglect disorder and decoherence, and assume a single trap vertex that is accountable for the loss processes. In particular, for each graph, we analytically determine the subspace of states having maximum transport efficiency. Our results provide a set of benchmarks for environment-assisted quantum transport, and suggest that connectivity is a poor indicator for transport efficiency. Indeed, we observe some specific correlations between transport efficiency and connectivity for certain graphs, but, in general, they are uncorrelated.     

Synchronization in power-law networks

We consider realistic power-law graphs, for which the power-law holds only for a certain range of degrees. We show that synchronizability of such networks depends on the expected average and expected maximum degree. In particular, we find that networks with realistic power-law graphs are less synchronizable than classical random networks. Finally, we consider hybrid graphs, which consist of two parts: a global graph and a local graph. We show that hybrid networks, for which the number of global edges is proportional to the number of total edges, almost surely synchronize.     

Velocity distributions in dissipative granular gases

Motivated by recent experiments reporting non-Gaussian velocity distributions in driven dilute granular materials, we study by numerical simulation the properties of 2D inelastic gases. We find theoretically that the form of the observed velocity distribution is governed primarily by the coefficient of restitution eta and q=N(H)/N(C), the ratio between the average number of heatings and the average number of collisions in the gas. The differences in distributions we find between uniform and boundary heating can then be understood as different limits of q, for q>1 and q less, similar 1, respectively.     

Exact solutions for diluted spin glasses and optimization problems

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma(d) = 0.818, and gamma(s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( gamma(var)(c) = 4.396 and gamma(var)(c) = 2.149).     

n-Particle Quantum Statistics on Graphs

We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n-particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.     

Synchronizability of chaotic logistic maps in delayed complex networks

We study a network of coupled logistic maps whose interactions occur with a certain distribution of delay times. The local dynamics is chaotic in the absence of coupling and thus the network is a paradigm of a complex system. There are two regimes of synchronization, depending on the distribution of delays: when the delays are sufficiently heterogeneous the network synchronizes on a steady-state (that is unstable for the uncoupled maps); when the delays are homogeneous, it synchronizes in a time-dependent state (that is either periodic or chaotic). Using two global indicators we quantify the synchronizability on the two regimes, focusing on the roles of the network connectivity and the topology. The connectivity is measured in terms of the average number of links per node, and we consider various topologies (scale-free, small-world, star, and nearest-neighbor with and without a central hub). With weak connectivity and weak coupling strength, the network displays an irregular oscillatory dynamics that is largely independent of the topology and of the delay distribution. With heterogeneous delays, we find a threshold connectivity level below which the network does not synchronize, regardless of the network size. This minimum average number of neighbors seems to be independent of the delay distribution. We also analyze the effect of self-feedback loops and find that they have an impact on the synchronizability of small networks with large coupling strengths. The influence of feedback, enhancing or degrading synchronization, depends on the topology and on the distribution of delays.     

复杂网络的顶点着色及其在疾病免疫中的应用

在复杂网络研究中, 对于网络结构特征的分析已经引起了人们的极大关注, 而其中的网络着色问题却没有得到足够的重视. 为了理解网络结构与着色之间的关系, 本文研究了WS, BA网络以及不同宏观结构参量对于正常K色数的影响, 发现最大团数可以大致反映正常K色数的变化趋势, 而网络的平均度和匹配系数比异质性和聚类系数对于色数的影响更大. 对于一些实际网络的正常着色验证了本文的分析结果. 对复杂网络的顶点进行着色后, 根据独立集内任意两个顶点均不相邻的特点, 我们提出了基于独立集的免疫策略. 与全网随机免疫相比, 基于独立集的免疫策略可令网络更为脆弱, 从而有效抑制疾病的传播. 基于网络着色的独立集提供了一种崭新的免疫思路, 作为一个简单而适用的平台,有助于设计更为有效的免疫策略. 关键词： 复杂网络 正常着色 独立集 免疫策略     

Coherent periodic activity in excitatory Erdös-Renyi neural networks: the role of network connectivity

In this article, we investigate the role of connectivity in promoting coherent activity in excitatory neural networks. In particular, we would like to understand if the onset of collective oscillations can be related to a minimal average connectivity and how this critical connectivity depends on the number of neurons in the networks. For these purposes, we consider an excitatory random network of leaky integrate-and-fire pulse coupled neurons. The neurons are connected as in a directed Erdo?s-Renyi graph with average connectivity scaling as a power law with the number of neurons in the network. The scaling is controlled by a parameter γ, which allows to pass from massively connected to sparse networks and therefore to modify the topology of the system. At a macroscopic level, we observe two distinct dynamical phases: an asynchronous state corresponding to a desynchronized dynamics of the neurons and a regime of partial synchronization (PS) associated with a coherent periodic activity of the network. At low connectivity, the system is in an asynchronous state, while PS emerges above a certain critical average connectivity (c). For sufficiently large networks, (c) saturates to a constant value suggesting that a minimal average connectivity is sufficient to observe coherent activity in systems of any size irrespectively of the kind of considered network: sparse or massively connected. However, this value depends on the nature of the synapses: reliable or unreliable. For unreliable synapses, the critical value required to observe the onset of macroscopic behaviors is noticeably smaller than for reliable synaptic transmission. Due to the disorder present in the system, for finite number of neurons we have inhomogeneities in the neuronal behaviors, inducing a weak form of chaos, which vanishes in the thermodynamic limit. In such a limit, the disordered systems exhibit regular (non chaotic) dynamics and their properties correspond to that of a homogeneous fully connected network for any γ-value. Apart for the peculiar exception of sparse networks, which remain intrinsically inhomogeneous at any system size.     

Percolation on Infinite Graphs and Isoperimetric Inequalities

We consider the Bernoulli bond percolation process (with parameter p) on infinite graphs and we give a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a bi-infinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. This new criterion extends previous criteria and brings together a large class of amenable graphs (such as regular lattices) and non-amenable graphs (such trees). We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesic always have finite connectivity functions with exponential decay when p is sufficiently close to one. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays sub-exponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close to one.     

Chimeras in random non-complete networks of phase oscillators

We consider the simplest network of coupled non-identical phase oscillators capable of displaying a "chimera" state (namely, two subnetworks with strong coupling within the subnetworks and weaker coupling between them) and systematically investigate the effects of gradually removing connections within the network, in a random but systematically specified way. We average over ensembles of networks with the same random connectivity but different intrinsic oscillator frequencies and derive ordinary differential equations (ODEs), whose fixed points describe a typical chimera state in a representative network of phase oscillators. Following these fixed points as parameters are varied we find that chimera states are quite sensitive to such random removals of connections, and that oscillations of chimera states can be either created or suppressed in apparent bifurcation points, depending on exactly how the connections are gradually removed.     

Non-abelian quantum Hall effect in topological flat bands

Inspired by the recent theoretical discovery of robust fractional topological phases without a magnetic field, we search for the non-abelian quantum Hall effect in lattice models with topological flat bands. Through extensive numerical studies on the Haldane model with three-body hard-core bosons loaded into a topological flat band, we find convincing numerical evidence of a stable ν=1 bosonic non-abelian quantum Hall effect, with the characteristic threefold quasidegeneracy of ground states on a torus, a quantized Chern number, and a robust spectrum gap. Moreover, the spectrum for two-quasihole states also shows a finite energy gap, with the number of states in the lower-energy sector satisfying the same counting rule as the Moore-Read pfaffian state.     

Accuracy and scaling phenomena in Internet mapping

It was recently argued that sampling a network by traversing it with paths from a small number of sources, as with traceroutes on the Internet, creates a fundamental bias in observed topological features like the degree distribution. We examine this bias analytically and experimentally. For Erdo s-Re nyi random graphs with mean degree c, we show analytically that such sampling gives an observed degree distribution P(k) approximately k(-1) for k less, similarc, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails P(k) approximately k(-alpha), sampling can significantly underestimate alpha when the graph has a large excess (i.e., many more edges than vertices). We find that in order to accurately estimate alpha, one must use a number of sources which grows linearly in the mean degree of the underlying graph. Finally, we comment on the accuracy of the published values of alpha for the Internet.     

Sharp transition for single polarons in the one-dimensional Su-Schrieffer-Heeger model

We study a single polaron in the Su-Schrieffer-Heeger (SSH) model using four different techniques (three numerical and one analytical). Polarons show a smooth crossover from weak to strong coupling, as a function of the electron-phonon coupling strength λ, in all models where this coupling depends only on phonon momentum q. In the SSH model the coupling also depends on the electron momentum k; we find it has a sharp transition, at a critical coupling strength λ(c), between states with zero and nonzero momentum of the ground state. All other properties of the polaron are also singular at λ=λ(c). This result is representative of all polarons with coupling depending on k and q, and will have important experimental consequences (e.g., in angle-resolved photoemission spectroscopy and conductivity experiments).     

Trapping of continuous-time quantum walks on Erdös–Rényi graphs

We consider the coherent exciton transport, modeled by continuous-time quantum walks, on Erdös–Rény graphs in the presence of a random distribution of traps. The role of trap concentration and of the substrate dilution is deepened showing that, at long times and for intermediate degree of dilution, the survival probability typically decays exponentially with a (average) decay rate which depends non-monotonically on the graph connectivity; when the degree of dilution is either very low or very high, stationary states, not affected by traps, get more likely giving rise to a survival probability decaying to a finite value. Both these features constitute a qualitative difference with respect to the behavior found for classical walks.     

Novel route to a finite center-of-mass momentum pairing state for superconductors: A current-driven Fulde-Ferrell-Larkin-Ovchinnikov state

The previously studied Fulde-Ferrell-Larkin-Ovchinnikov (FFLO) state is stabilized by a magnetic field via the Zeeman coupling in spin-singlet superconductors. Here we suggest a novel route to achieve nonzero center-of-mass momentum pairing states in superconductors with Fermi surface nesting. We investigate two-dimensional superconductors under a uniform external current, proportional to a finite pair momentum of q(e). We find that an FFLO state with a spontaneous pair momentum of q(s) is stabilized above a certain critical current that depends on the direction of the external current. A finite q(s) arises in order to make the total pair-momentum of q(t)(=q(s) + q(e)) perpendicular to the nesting vector, which is independent of spin states of Cooper pairs. We also discuss experimental signatures of the FFLO state.     

Mobile user forecast and power-law acceleration invariance of scale-free networks

This paper studies and predicts the number growth of China's mobile users by using the power-law regression. We find that the number growth of the mobile users follows a power law. Motivated by the data on the evolution of the mobile users, we consider scenarios of self-organization of accelerating growth networks into scale-free structures and propose a directed network model, in which the nodes grow following a power-law acceleration. The expressions for the transient and the stationary average degree distributions are obtained by using the Poisson process. This result shows that the model generates appropriate power-law connectivity distributions. Therefore, we find a power-law acceleration invariance of the scale-free networks. The numerical simulations of the models agree with the analytical results well.     

Spin glasses on Bethe lattices for large coordination number

We study spin glasses on random lattices with finite connectivity. In the infinite connectivity limit they reduce to the Sherrington Kirkpatrick model. In this paper we investigate the expansion around the high connectivity limit. Within the replica symmetry breaking scheme at two steps, we compute the free energy at the first order in the expansion in inverse powers of the average connectivity (z), both for the fixed connectivity and for the fluctuating connectivity random lattices. It is well known that the coefficient of the 1/z correction for the free energy is divergent at low temperatures if computed in the one step approximation. We find that this annoying divergence becomes much smaller if computed in the framework of the more accurate two steps breaking. Comparing the temperature dependance of the coefficients of this divergence in the replica symmetric, one step and two steps replica symmetry breaking, we conclude that this divergence is an artefact due to the use of a finite number of steps of replica symmetry breaking. The 1/z expansion is well defined also in the zero temperature limit. Received 15 July 2002 Published online 31 December 2002