An information‐theoretic primer on complexity,self‐organization,and emergence

Complex Systems Science aims to understand concepts like complexity, self‐organization, emergence and adaptation, among others. The inherent fuzziness in complex systems definitions is complicated by the unclear relation among these central processes: does self‐organisation emerge or does it set the preconditions for emergence? Does complexity arise by adaptation or is complexity necessary for adaptation to arise? The inevitable consequence of the current impasse is miscommunication among scientists within and across disciplines. We propose a set of concepts, together with their possible information‐theoretic interpretations, which can be used to facilitate the Complex Systems Science discourse. Our hope is that the suggested information‐theoretic baseline may promote consistent communications among practitioners, and provide new insights into the field. Published 2008 Wiley Periodicals, Inc. Complexity, 2009     

Consistent concepts of self‐organization and self‐assembly

We critically review concepts of self‐organization and self‐assembly, and extract from this analysis consistent and workable definitions of both concepts that are applicable across many scientific disciplines. In essence, we distinguish self‐organization from self‐assembly on a thermodynamic basis, where self‐organization implies a nonequilibrium process and self‐assembly is reserved for spontaneous processes tending toward equilibrium. This discrimination is consistent with early uses of both terms. © 2008 Wiley Periodicals, Inc. Complexity, 2008.     

The self‐organization of genomes

Menzerath‐Altmann law is a general law of human language stating, for instance, that the longer a word, the shorter its syllables. With the metaphor that genomes are words and chromosomes are syllables, we examine if genomes also obey the law. We find that longer genomes tend to be made of smaller chromosomes in organisms from three different kingdoms: fungi, plants, and animals. Our findings suggest that genomes self‐organize under principles similar to those of human language. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

Emergence of self‐similar tree network organization

The self‐similar tree topology in open dissipative systems is formed as a result of self‐organization and found in various examples, such as river networks, blood vessels, vascular organizations in plants, and even lightning. It is generally assumed that the tree organization is a result of a dynamic process that minimizes the dissipation of energy. Here, we argue that inherent randomness is a sufficient condition for the generation of tree patterns under evolutionary dynamics and the decrease of energy expenditure is not the cause but a consequent signature. © 2008 Wiley Periodicals, Inc. Complexity, 13: 30–37, 2008     

Emergence and self‐organization in partially ordered sets

The discovery of a simple functional the optimization of which by a dynamical process results in extraordinary structural organization in partially ordered sets is reported in this article. As partially ordered sets are one of the most prevalent and fundamental objects in Mathematics and are ubiquitous in nature, physics, engineering and technology in general, and since any system amenable to mathematical analysis can be represented as a partially ordered set, the discovery is proposed as an explanation for the phenomena of emergence and self‐organization in dynamical systems. © 2011Wiley Periodicals, Inc. Complexity, 17,19–38, 2011     

Fractality and self‐organization in the orthodox iconography

The authors consider the Orthodox iconography of Byzantine style aimed at examining the existence of complex behavior and fractal patterns. It has been demonstrated that fractality in icons is manifested as two types—descending and ascending, where the former one corresponds to the apparent information and the latter one to the hidden causal information defining the spatiality of icon. Self‐organization, recognized as the increase of the causal information in temporal domain, corresponds to contextualization of the observer's personage position. The results presented in the forms of plots and tables confirm the adequacy of the model being the completion of visual perception. © 2015 Wiley Periodicals, Inc. Complexity 21: 55–68, 2016     

Self‐organization and selection in the emergence of vocabulary

Human language may have started from a consistent set of mappings between meanings and signals. These mappings, referred to as the early vocabulary, are considered to be the results of conventions established among the agents of a population. In this study, we report simulation models for investigating how such conventions can be reached. We propose that convention is essentially the product of self‐organization of the population through interactions among the agents and that cultural selection is another mechanism that speeds up the establishment of convention. Whereas earlier studies emphasize either one or the other of these two mechanisms, our focus is to integrate them into one hybrid model. The combination of these two complementary mechanisms, i.e., self‐organization and cultural selection, provides a plausible explanation for cultural evolution, which progresses with high transmission rate. Furthermore, we observe that as the vocabulary tends to convergence there is a uniform tendency to exhibit a sharp phase transition. © 2002 Wiley Periodicals, Inc.     

Genome size,self‐organization and DNA's dark matter

Chromosomes exhibit several features indicating that its spatiotemporal dynamics is self‐organized. It has been recently suggested that a negative correlation between genome size and mean chromosome number would also be a fingerprint of selforganization, related to how human language is organized at the level of words and syllables. However, the vast dominance of non‐coding DNA in eukaryotic genomes should prevent an interpretation of genome/chromosome size based on functional trade‐offs related to information storage and transmission. Moreover, the reported negative correlation is shown to be an inevitable consequence of the definitions of chromosome and genome length and it is thus unrelated to any type of special generative process. © 2010 Wiley Periodicals, Inc. Complexity 16: 20–23, 2010     

Duality relation on spectra of self‐affine measures

The present paper establishes a duality relation for the spectra of self‐affine measures. This is done under the condition of compatible pair and is motivated by a duality conjecture of Dutkay and Jorgensen on the spectrality of self‐affine measures. For the spectral self‐affine measure, we first obtain a structural property of spectra which indicates that one can get new spectra from old ones. We then establish a duality property for the spectra which confirms the conjecture in a certain case.     

Swarm contours: A fast self‐organization approach for snake initialization

A major obstacle in real‐time performance of a visual tracking system is its initialization phase. Inspired by social behavior in fish and ant groups, a fast self‐organization approach to active‐contour initialization is proposed. Contours are emerged during two separate phases of aggregation and self‐assembly. Aggregation is achieved by a superposition of simpler behaviors, hunting, avoidance, and opportunism. Self‐assembly, which constitutes the explicit contour formation, occurs by mating behavior when the swarm becomes quite stable. Experiments indicate that the proposed method outperforms exhaustive image search for finding contours in high resolutions. © 2006 Wiley Periodicals, Inc. Complexity 12: 41–52, 2006     

Using self‐dissimilarity to quantify complexity

For many systems characterized as “complex” the patterns exhibited on different scales differ markedly from one another. For example, the biomass distribution in a human body “looks very different” depending on the scale at which one examines it. Conversely, the patterns at different scales in “simple” systems (e.g., gases, mountains, crystals) vary little from one scale to another. Accordingly, the degrees of self‐dissimilarity between the patterns of a system at various scales constitute a complexity “signature” of that system. Here we present a novel quantification of self‐dissimilarity. This signature can, if desired, incorporate a novel information‐theoretic measure of the distance between probability distributions that we derive here. Whatever distance measure is chosen, our quantification of self‐dissimilarity can be measured for many kinds of real‐world data. This allows comparisons of the complexity signatures of wholly different kinds of systems (e.g., systems involving information density in a digital computer vs. species densities in a rain forest vs. capital density in an economy, etc.). Moreover, in contrast to many other suggested complexity measures, evaluating the self‐dissimilarity of a system does not require one to already have a model of the system. These facts may allow self‐dissimilarity signatures to be used as the underlying observational variables of an eventual overarching theory relating all complex systems. To illustrate self‐dissimilarity, we present several numerical experiments. In particular, we show that the underlying structure of the logistic map is picked out by the self‐dissimilarity signature of time series produced by that map. © 2007 Wiley Periodicals, Inc. Complexity 12: 77–85, 2007     

H‐self‐adjoint matrices. Application to radiosity

In computer graphics, in the radiosity context, a linear system Φx=b must be solved and there exists a diagonal positive matrix H such that H Φ is symmetric. In this article, we extend this property to complex matrices: we are interested in matrices which lead to Hermitian matrices under premultiplication by a Hermitian positive‐definite matrix H. We shall prove that these matrices are self‐adjoint with respect to a particular innerproduct defined on ?ⁿ. As a result, like Hermitian matrices, they have real eigenvalues and they are diagonalizable. We shall also show how to extend the Courant–Fisher theorem to this class of matrices. Finally, we shall give a new preconditioning matrix which really improves the convergence speed of the conjugate gradient method used for solving the radiosity problem. Copyright © 2002 John Wiley & Sons, Ltd.     

Life‐like self‐reproducers

In order to understand the interplay among information, genetic instructions, and phenotypic variations, self‐reproducers discovered in two‐dimensional cellular automata are considered as proto‐organisms, which undergo to mutations as they were in a real environmental situation. We realized a computational model through which we have been able to discover the genetic map of the self‐reproducers and the networks they use. Identifying in these maps sets of different functional genes, we found that mutations in the genetic sequences could affect both external shapes and behavior of the self‐reproducers, thus realizing different life‐like strategies in the evolution process. The results highlight that some strategies evolution uses in selecting organisms that are fitting with changing environmental situations maintain the self‐reproducing function, whereas other variations create new self‐reproducers. These self‐reproducers in turn realize different genetic networks, which can be very different from the basic ancestors pools. The mutations that are disruptive bring self‐reproducers to disappear, while other proto‐organisms are generated. © 2004 Wiley Periodicals, Inc. Complexity 9: 38–55, 2004     

Self‐dual and self‐petrie‐dual regular maps

Regular maps are cellular decompositions of surfaces with the “highest level of symmetry”, not necessarily orientation‐preserving. Such maps can be identified with three‐generator presentations of groups G of the form G = 〈a, b, c|a² = b² = c² = (ab)^k = (bc)^m = (ca)² = … = 1〉; the positive integers k and m are the face length and the vertex degree of the map. A regular map (G;a, b, c) is self‐dual if the assignment b?b, c?a and a?c extends to an automorphism of G, and self‐Petrie‐dual if G admits an automorphism fixing b and c and interchanging a with ca. In this note we show that for infinitely many numbers k there exist finite, self‐dual and self‐Petrie‐dual regular maps of vertex degree and face length equal to k. We also prove that no such map with odd vertex degree is a normal Cayley map. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:152‐159, 2012     

Teaching complexity theory through student construction of a course wiki: The self‐organization of a scale‐free network

Complex systems are fascinating because emergent phenomena are often unpredictable and appear to arise ex nihilo. The other side of this fascination, however, is a certain difficulty in comprehending complex systems, particularly for students. To help students more fully understand emergence and self‐organization, a course on complexity theory was designed to not only be about these two concepts, but itself embody them. The principal design tool was a course wiki. Here, we quantitatively demonstrate that this course wiki self‐organized into a scale‐free network. This is particularly notable given the small size of the network. We conclude by noting a few qualitative examples of emergence, as well as offering recommendations for the future use of wikis in teaching complexity theory. © 2010 Wiley Periodicals, Inc. Complexity 16: 41–48, 2011     

Non‐Abelian homomorphism testing,and distributions close to their self‐convolutions

In this paper, we study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G,H (not necessarily Abelian), an arbitrary map f : G,H, and a parameter 0 < ε < 1, say that f is ε‐close to a homomorphism if there is some homomorphism g such that g and f differ on at most ε | G | elements of G, and say that f is ε‐far otherwise. For a given f and ε, a homomorphism tester should distinguish whether f is a homomorphism, or if f is ε‐far from a homomorphism. When G is Abelian, it was known that the test which picks O(1/ε) random pairs x,y and tests that f(x) + f(y) = f(x + y) gives a homomorphism tester. Our first result shows that such a test works for all groups G. Next, we consider functions that are close to their self‐convolutions. Let A = {a_g | g ε G} be a distribution on G. The self‐convolution of A, A^′ = {a | g ε G}, is defined by It is known that A= A^′ exactly when A is the uniform distribution over a subgroup of G. We show that there is a sense in which this characterization is robust—that is, if A is close in statistical distance to A^′, then A must be close to uniform over some subgroup of G. Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self‐convolutions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Approach to self‐similarity in Smoluchowski's coagulation equations

We consider the approach to self‐similarity (or dynamical scaling) in Smoluchowski's equations of coagulation for the solvable kernels K(x, y) = 2, x + y and xy. In addition to the known self‐similar solutions with exponential tails, there are one‐parameter families of solutions with algebraic decay, whose form is related to heavy‐tailed distributions well‐known in probability theory. For K = 2 the size distribution is Mittag‐Leffler, and for K = x + y and K = xy it is a power‐law rescaling of a maximally skewed α‐stable Lévy distribution. We characterize completely the domains of attraction of all self‐similar solutions under weak convergence of measures. Our results are analogous to the classical characterization of stable distributions in probability theory. The proofs are simple, relying on the Laplace transform and a fundamental rigidity lemma for scaling limits. © 2003 Wiley Periodicals, Inc.     

Decomposition of integral self‐affine multi‐tiles

In contrast to the situation with self‐affine tiles, the representation of self‐affine multi‐tiles may not be unique (for a fixed dilation matrix). Let be an integral self‐affine multi‐tile associated with an integral, expansive matrix B and let K tile by translates of . In this work, we propose a stepwise method to decompose K into measure disjoint pieces  satisfying in such a way that the collection of sets forms an integral self‐affine collection associated with the matrix B and this with a minimum number of pieces . When used on a given measurable subset K which tiles by translates of , this decomposition terminates after finitely many steps if and only if the set K is an integral self‐affine multi‐tile. Furthermore, we show that the minimal decomposition we provide is unique.     

Non‐Cayley‐isomorphic self‐complementary circulant graphs

Non‐CI self‐complementary circulant graphs of prime‐squared order are constructed and enumerated. It is shown that for prime p, there exists a self‐complementary circulant graph of order p² not Cayley isomorphic to its complement if and only if p ≡ 1 (mod 8). Such graphs are also enumerated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 128–141, 2000     

Transitive tournaments and self‐complementary graphs

A simple proof is given for a result of Sali and Simonyi on self‐complementary graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 111–112, 2001