Spectral analysis and slow dynamics on quenched complex networks Géza Ódor MTA-TTK-MFA Budapest 19/09/2013 Partners: R. Juhász M. A. Munoz C. Castellano R. Pastor-Satorras „Infocommunication technologies and the society of future (FuturICT.hu)” TÁMOP-4.2.2.C-11/1/KONV-20120013 Budapest Granada Roma Barcelona Scaling in nonequilibrium system Scaling and universality classes appear in complex system due to : x i.e: near critical points, due to currents ... Basic models are classified by universal scaling behavior in Euclidean, regular system Why don't we see universality classes in models defined on networks ? Power laws are frequent in nature Tuning to critical point ? I'll show a possible way to understand these Criticality in networks ? Brain : PL size distribution of neural avalanches G. Werner : Biosystems, 90 (2007) 496, Internet: worm recovery time is slow: Can we expect slow dynamics in small-world network models ? Correlation length (x) diverges Haimovici et al PRL (2013) : Brain complexity born out of criticality. Network statphys research Expectation: small world topology mean-field behavior & fast dynamics Prototype: Contact Process (CP) or Susceptible-Infected-Susceptible (SIS) two-state models: Infect: l / (1+l) Heal: 1 / (1+l) For SIS : Infections attempted for all nn Order parameter : density of active ( ) sites Regular, Euclidean lattice: DP critical point : lc > 0 between inactive and active phases Rare Region theory for quench disordered CP Fixed (quenched) disorder/impurity „dirty critical point” changes the local birth rate l c > lc0 Locally active, but arbitrarily large GP Rare Regions „clean critical point” in the inactive phase due to the inhomogeneities lc Act. lc0 Abs. Probability of RR of size LR: w(LR ) ~ exp (-c LR ) contribute to the density: r(t) ~ ∫ dLR LR w(LR ) exp [-t /t (LR)] For l < lc0 : conventional (exponentially fast) decay At lc0 the characteristic time scales as: t (LR) ~ LR Z ln r(t) ~ t d / ( d + Z) For lc0 < l < lc : stretched exponential t (LR) ~ exp(b LR): r(t) ~ t - c / b r(t) ~ ln(t) -a saddle point analysis: Griffiths Phase continuously changing exponents At lc : b may diverge In case of correlated RR-s with dimension > d - : smeared transition Infinite randomness fixed point scaling Networks considered From regular to random networks: Erdős-Rényi (p = 1) Degree (k) distribution in N→ node limit: P(k) = e-<k> <k>k / k! Topological dimension: N(r) ∼ r d Above perc. thresh.: d = Below percolation d=0 Scale free networks: Degree distribution: P(k) = k - ( 2< < 3) Topological dimension: d = Example: Barabási-Albert lin. prefetential attachment A Rare region effects in networks ? Rare active regions below lc with: t(A)~ eA → slow dynamics (Griffiths Phase) ? M. A. Munoz, R. Juhász, C. Castellano and G. Ódor, PRL 105, 128701 (2010) 1. Inherent disorder in couplings 2. Disorder induced by topology Optimal fluctuation theory + simulations: YES In Erdős-Rényi networks below the percolation threshold In generalized small-world networks with finite topological dimension Spectral Analysis of networks – Quenched Mean-Field method Master (rate) equation of SIS for occupancy prob. at site i: Weighted (real symmetric) Adjacency matrix: Express ri on orthonormal eigenvector ( fi (L) ) basis: Mean-field estimate Total infection density vanishes near lc as : QMF results for Erdős-Rényi Percolative ER IPR ~ 1/N → delocalization → multi-fractal exponent → Rényi entropy L1 = 1/lc → 5.2(2) L1 = k =4 Fragmented ER IPR → 0.22(2) → localization Simulation results for ER graphs Percolative ER Fragmented ER Weighted SIS on ER graph G.Ó.: PRE 2013 C. Buono, F. Vazquez, P. A. Macri, and L. A. Braunstein, PRE 88, 022813 (2013) QMF supports these results Quenched Mean-Field method for scale-free BA graphs Barabási-Albert graph attachment prob.: IPR remains small but exhibits large fluctuations as N (wide distribution) Lack of clustering in the steady state, mean-field transition Contact Process on Barabási-Albert (BA) network Heterogeneous mean-field theory: conventional critical point, with linear density decay: with logarithmic correction Extensive simulations confirm this No Griffiths phase observed Steady state density vanishes at lc 1 linearly, HMF: b = 1 (+ log. corrections) G. Ódor, R. Pastor-Storras PRE 86 (2012) 026117 SIS on weigthed Barabási-Albert graphs Excluding loops slows down the spreading WBAT-II: disassortative weight scheme l dependent density decay exponents: Griffiths Phases or Smeared phase transition ? + Weights: Do power-laws survive the thermodynamic limit ? Finite size analysis shows the disappearance of a power-law scaling: Power-law → saturation explained by smeared phase transition: High dimensional rare sub-spaces Rare-region effects in aging BA graphs BA followed by preferential edge removal pij ki kj dilution is repeated until 20% of links are removed QMF IPR → 0.28(5) No size dependence → Griffiths Phase Localization in the steady state Summary Quenched disorder in complex networks can cause slow (PL) dynamics : Rare-regions → Griffiths phases → no tuning or self-organization needed ! GP can occur due to purely topological disorder In infinite dim. Networks (ER, BA) mean-field transition of CP with logarithmic corrections (HMF + simulations, QMF) In weighted BA trees non-universal, slow, power-law dynamics can occur for finite N, but in the N limit saturation was observed Smeared transition can describe this, percolation analysis confirms the existence of arbitrarily large dimensional sub-spaces with (correlated) large weights Quenched mean-field approximation gives correct description of rare-region effects and the possibility of phases with extended slow dynamics GP in important models: Q-ER (F2F experiments), aging BA graph Acknowledgements to : HPC-Europa2, OTKA, Osiris FP7, FuturICT.hu  M. A. Munoz, R. Juhasz, C. Castellano, and G, Ódor, Phys. Rev. Lett. 105, 128701 (2010)  G. Ódor, R. Juhasz, C. Castellano, M. A. Munoz, AIP Conf. Proc. 1332, Melville, New York (2011) p. 172-178.  R. Juhasz, G. Ódor, C. Castellano, M. A. Munoz, Phys. Rev. E 85, 066125 (2012)  G. Ódor and Romualdo Pastor-Satorras, Phys. Rev. E 86, 026117 (2012)  G. Ódor, Phys. Rev. E 87, 042132 (2013)  G. Ódor, Phys. Rev. E 88, 032109 (2013) „Infocommunication technologies and the society of future (FuturICT.hu)” TÁMOP-4.2.2.C11/1/KONV-2012-0013 l CP + Topological disorder results Generalized Small World networks: P(l) ~ b l - 2 (link length probability) Top. dim: N(r) ∼ r d d(b ) finite: lc(b ) decreases monotonically from lc(0 )= 3.29785 (1d CP) to: limb lc(b ) = 1 towards mean-field CP value l < lc(b ) inactive, there can be locally ordered, rare regions due to more than average, active, incoming links Griffiths phase: l - dep. continuously changing dynamical power laws: for example : r(t) ∼ t - a (l) Logarithmic corrections ! Ultra-slow (“activated”) scaling: r ln(t)- a at lc As b 1 Griffiths phase shrinks/disappears Same results for: cubic, regular random nets higher dimensions ? l GP Percolation analysis of the weighted BA tree We consider a network of a given size N, and delete all the edges with a weight smaller than a threshold wth. For small values of wth, many edges remain in the system, and they form a connected network with a single cluster encompassing almost all the vertices in the network. When increasing the value of wth, the network breaks down into smaller subnetworks of connected edges, joined by weights larger than wth. The size of the largest ones grows linearly with the network size N « standard percolation transition. These clusters, which can become arbitrarily large in the thermodynamic limit, play the role of correlated RRs, sustaining independently activity and smearing down the phase transition.