Search

We study two measures of the complexity of heterogeneous extended systems, taking random Boolean networks as prototypical cases. A measure defined by Shalizi et al. for cellular automata, based on a criterion for optimal statistical prediction [Shalizi et al, Phys. Rev. Lett. 93, 118701 (2004)], does not distinguish between the spatial inhomogeneity of the ordered phase and the dynamical inhomogeneity of the disordered phase. A modification in which complexities of individual nodes are calculated yields vanishing complexity values for networks in the ordered and critical regimes and for highly disordered networks, peaking somewhere in the disordered regime. Individual nodes with high complexity are the ones that pass the most information from the past to the future, a quantity that depends in a nontrivial way on both the Boolean function of a given node and its location within the network. [ABSTRACT FROM AUTHOR]

We consider a simplified model of a social network in which individuals have one of two opinions (called 0 and 1) and their opinions and the network connections coevolve. Edges are picked at random. If the two connected individuals hold different opinions then. with probability 1 - α, one imitates the opinion of the other; otherwise (i.e., with probability a), the link between them is broken and one of them makes a new connection to an individual chosen at random (i) from those with the same opinion or (ii) from the network as a whole. The evolution of the system stops when there are no longer any discordant edges connecting individuals with different opinions. Letting ρ be the fraction of voters holding the minority opinion after the evolution stops, we are interested in how ρ depends on a and the initial fraction u of voters with opinion 1. In case (i), there is a critical value αc which does not depend on u, with ρ u for α > αc and p ≈ 0 for α <αc. In case (ii), the transition point αc(u) depends on the initial density u. For α > αc(u), p ≈ u, but for α <αc(u). we have ρ(α,u) = ρ(α,1/2). Using simulations and approximate calculations, we explain why these two nearly identical models have such dramatically different phase transitions. [ABSTRACT FROM AUTHOR]