Dynamic Pattern Evolution on Scale-Free Networks

• Published in: Proceedings of the National Academy of Sciences - PNAS 2005-07, Vol.102 (29), p.10052-10057
• Main Authors: Zhou, Haijun, Lipowsky, Reinhard, Fisher, Michael E.
• Format: Article
• Language: English
• Subjects: Boolean data; Computer memory; Computer networks; Computer simulation; Dynamic modeling; Evolution equations; Majority rule; Memory; Modeling; Physical Sciences; Physics; Random variables; Self consistent fields; Simulation; Trajectories; Vertices
• ISSN: 0027-8424; 1091-6490
• DOI: 10.1073/pnas.0409296102

A general class of dynamic models on scale-free networks is studied by analytical methods and computer simulations. Each network consists of N vertices and is characterized by its degree distribution, P(k), which represents the probability that a randomly chosen vertex is connected to k nearest neighbors. Each vertex can attain two internal states described by binary variables or Ising-like spins that evolve in time according to local majority rules. Scale-free networks, for which the degree distribution has a power law tail P(k) ∼ k-γ, are shown to exhibit qualitatively different dynamic behavior for γ < 5/2 and γ > 5/2, shedding light on the empirical observation that many real-world networks are scale-free with 2 < γ < 5/2. For 2 < γ < 5/2, strongly disordered patterns decay within a finite decay time even in the limit of infinite networks. For γ > 5/2, on the other hand, this decay time diverges as In(N) with the network size N. An analogous distinction is found for a variety of more complex models including Hopfield models for associative memory networks. In the latter case, the storage capacity is found, within mean field theory, to be independent of N in the limit of large N for γ > 5/2 but to grow as Nαwith α = (5 - 2γ)/(γ - 1) for 2 < γ < 5/2.