Levels of a scale‐free tree

Consider the random graph model of Barabási and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices the graph will be a tree. These graphs have been shown to have power law degree distributions, the same as observed in some large real‐world networks. We show that the degree distribution is the same on every sufficiently high level of the tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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     

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     

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     

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     

The degree sequences and spectra of scale‐free random graphs

We investigate the degree sequences of scale‐free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non‐rigorous arguments of Dorogovtsev, Mendes, and Samukhin ( 14 ). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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     

A scale‐free network model for HIV transmission among men who have sex with men in China

Objective: The study aimed to analyze sexual networks and sex role preference as factors of HIV transmission among men who have sex with men (MSM) in China. Methods: We have developed a new scale‐free network model with a sex role preference framework to study HIV transmission among MSM. We have studied the influence of different sexual networks and the effect of different proportion of sex role preference upon HIV transmission. The results are that the average ones drawn from the scenarios have been simulated for more than 30 times. Results: Compared with the traditional mathematical model, the sexual networks provide a different prediction of the HIV transmission in the next 30 years. Without any intervention, the proportion of HIV carriers will descend after some time. Conclusions: There is significant associations among network characteristics, sex role preference, and HIV infection. Although network‐based intervention is efficient in reducing HIV transmission among MSM, there are only few studies of the characteristics of sexual network, and such gaps deserve more attention and exploration. Copyright © 2016 John Wiley & Sons, Ltd.     

Diameter in ultra‐small scale‐free random graphs

It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k^{?(τ ? 1)} with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree d_fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.     

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     

On centripetal flows of entities in scale‐free networks with nodes of finite capability

We examine the transmission of entities from the peripheries of scale‐free networks toward their centers when the nodes of the network have finite processing capabilities. We look at varying network utilization, U and find that clogging of the network sets in after a threshold value has been exceeded, and that the congestion sets in at the downstream nodes (those nearer to the collector) having large numbers of upstream neighbors. Investigation of the question of the degree of correlation of several characteristics of scale‐free networks (such as the average path length to the collector <l_(min)> and the average clustering coefficient ) with the dynamics of centripetal flow in them reveals a negative answer: any correlation is indirect and will manifest in the number of producer nodes (which dictate the effective heaviness of the flow) and the interconnectedness of the feeder nodes, those nodes which are immediate neighbors of the collector node. An examination of reinforcement strategies shows dramatic improvements in both the finishing rate, and the average total transmission time, when the more centrally‐placed nodes are reinforced first, showing that the entities spend a large amount of their lifetime waiting in line at those nodes (which constitute the bottlenecks in the network) compared to the nodes in the periphery. Our results reinforce the importance of a network's hubs and their immediate environs, and suggest strategies for prioritizing elements of a network for optimization. © 2014 Wiley Periodicals, Inc. Complexity 21: 283–295, 2015     

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     

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     

Nonextensive model of self‐organizing systems

The article concerns the new nonextensive model of self‐organizing systems and consists of two interrelated parts. The first one presents a new nonextensive model of interaction between elements of systems. The second one concerns the relationship between microscopic and macroscopic processes in complex systems. It is shown that nonextensivity and self‐organization of systems is a result of mismatch between its elements. © 2013 Wiley Periodicals, Inc. Complexity 18: 28–36, 2013     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Global solutions of a radiative and reactive gas with self‐gravitation for higher‐order kinetics

The existence of global solutions is established for compressible Navier–Stokes equations by taking into account the radiative and reactive processes, when the heat conductivity κ (κ₁(1 + θ^q) ≤ κ ≤ κ₂(1 + θ^q),q ≥ 0), where θ is the temperature. This improves the previous results by enlarging the scope of q including the constant heat conductivity. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

The complexity of advice‐giving

Advice‐giving about personal problems is a common form of human interaction. However, an open question is whether there is an abstract and general logic that explains how advice‐giving works. In this study, we addressed this question from the perspective of dynamical systems. We measured the nonlinear dynamics of advice‐giving by using recurrence quantification analysis. Analyzing 600 texts of request for advice and the advice given, our results uncover a typical logic of advice‐giving, and suggest that advice‐giving may be understood as a dynamic manipulation of perspective‐taking. © 2009 Wiley Periodicals, Inc. Complexity 2009     

The complexity of the free space for a robot moving amidst fat obstacles

We propose a new definition of fatness of geometric objects and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot, with any fixed number of degrees of freedom moving in a d-dimensional Euclidean workspace with fat obstacles, is linear in the number of obstacles. The complexity of motion planning algorithms depends on the complexity of the robot's free space, and theoretically, the complexity of the free space can be very high. Thus, our result opens the way to devising provable efficient motion planning algorithms in certain realistic settings.     

Extreme self‐adjoint extensions of a semibounded ‐difference operator

For a certain q‐difference operator introduced and studied in a series of articles by the same authors, we investigate its extreme self‐adjoint extensions, i.e., the so‐called Friedrichs and Kre?n extensions. We show that for the interval of parameters under consideration, the Friedrichs extension and the Kre?n extension are distinct and give values of the parameter in the von Neumann formulas that correspond to those extensions and describe their resolvent operators. A crucial rôle in our investigation plays the fact that both the Friedrichs and the Kre?n extensions are scale invariant.