Self-organized scale-free networks

Emergent scale-free networks

Many complex systems-from the Internet to social, biological, and communication networks-are thought to exhibit scale-free structure. However, prevailing explanations require that networks grow over time, an assumption that fails in some real-world settings. Here, we explain how scale-free structure can emerge without growth through network self-organization. Beginning with an arbitrary network, we allow connections to detach from random nodes and then reconnect under a mixture of preferential and random attachment. While the numbers of nodes and edges remain fixed, the degree distribution evolves toward a power-law with an exponent γ = 1 + 1 p that depends only on the proportion p of preferential (rather than random) attachment. Applying our model to several real networks, we infer p directly from data and predict the relationship between network size and degree heterogeneity. Together, these results establish how scale-free structure can arise in networks of constant size and density, with broad implications for the structure and function of complex systems.

Comparison between classical Kelvin-Voigt and fractional derivative Kelvin-Voigt models in prediction of linear viscoelastic behaviour of waste activated sludge

Appropriate sewage sludge rheological models are essential for computational fluid dynamic simulation of wastewater treatment processes, in particular aerobic and anaerobic digestions. The liquid-like behaviour of sludge is well documented but the solid-like behaviour remains poorly described despite its importance for dead-zone formation. In this study, classical Kelvin-Voigt model, commonly used for sludge in literature, were compared with fractional derivative Kelvin-Voigt model regarding their predictive ability for describing the solid-like behaviour. Results showed that the fractional Kelvin-Voigt model best fitted the experimental data obtained from creep and frequency sweep tests. Whereas, classical Kelvin-Voigt could not fit the frequency sweep data as this model is not a function of angular velocity. Also, the Kelvin-Voigt model was unable to predict the creep data at low stresses.

Network rewiring dynamics with convergence towards a star network

Network rewiring as a method for producing a range of structures was first introduced in 1998 by Watts & Strogatz (Nature393, 440-442. (doi:10.1038/30918)). This approach allowed a transition from regular through small-world to a random network. The subsequent interest in scale-free networks motivated a number of methods for developing rewiring approaches that converged to scale-free networks. This paper presents a rewiring algorithm (RtoS) for undirected, non-degenerate, fixed size networks that transitions from regular, through small-world and scale-free to star-like networks. Applications of the approach to models for the spread of infectious disease and fixation time for a simple genetics model are used to demonstrate the efficacy and application of the approach.

Evolution of the statistical distribution in a topological defect network

The complex networks of numerous topological defects in hexagonal manganites are highly relevant to vastly different phenomena from the birth of our cosmos to superfluidity transition. The topological defects in hexagonal manganites form two types of domain networks: type-I without and type-II with electric self-poling. A combined phase-field simulations and experimental study shows that the frequencies of domains with N-sides, i.e. of N-gons, in a type-I network are fitted by a lognormal distribution, whereas those in type-II display a scale-free power-law distribution with exponent ∼2. A preferential attachment process that N-gons with a larger N have higher probability of coalescence is responsible for the emergence of the scale-free networks. Since the domain networks can be observed, analyzed, and manipulated at room temperature, hexagonal manganites provide a unique opportunity to explore how the statistical distribution of a topological defect network evolves with an external electric field.

Edge removal balances preferential attachment and triad closing

Most network formation analysis studies are centered on edge addition. However, edges in real world networks often have a rapid turnover with a large number of edges added and removed between each node addition or removal steps. In such a case, quasiequilibrium is obtained between edge addition and deletion. Edges have been shown to be added to nodes with a high degree and between pairs of nodes with a high number of common neighbors. If not balanced by a degree dependent edge removal, the preference for high degree nodes and node pairs with many common neighbors is expected to increase the average degree of high degree nodes and their clustering coefficient until very large cliques will be formed. Since such large cliques are not formed in real world networks, we conclude that the edge removal probability around high degree nodes and between node pairs with many common neighbors should be higher than around other nodes. We here show the existence of such a balancing mechanism through the relation between the future edge removal probability around nodes and their degree and a similar relation between the edge removal probability and the number of common neighbors of node pairs. In some networks, this preferential detachment process represents an explicit saturation process, and in others, it represents a random deletion process accompanied by a sublinear edge preferential attachment process. A more complex mechanism emerges in directed networks where the preferential detachment can be proportional to the in and out degrees of the nodes involved. In such networks, preferential detachment is stronger for the incoming edges than for the outgoing edges. We hypothesize multiple possible mechanisms that could explain this phenomenon.

Detection of scale-freeness in brain connectivity by functional MRI: signal processing aspects and implementation of an open hardware co-processor

An outstanding issue in graph-theoretical studies of brain functional connectivity is the lack of formal criteria for choosing parcellation granularity and correlation threshold. Here, we propose detectability of scale-freeness as a benchmark to evaluate time-series extraction settings. Scale-freeness, i.e., power-law distribution of node connections, is a fundamental topological property that is highly conserved across biological networks, and as such needs to be manifest within plausible reconstructions of brain connectivity. We demonstrate that scale-free network topology only emerges when adequately fine cortical parcellations are adopted alongside an appropriate correlation threshold, and provide the full design of the first open-source hardware platform to accelerate the calculation of large linear regression arrays.

Randomly evolving idiotypic networks: structural properties and architecture

We consider a minimalistic dynamic model of the idiotypic network of B lymphocytes. A network node represents a population of B lymphocytes of the same specificity (idiotype), which is encoded by a bit string. The links of the network connect nodes with complementary and nearly complementary bit strings, allowing for a few mismatches. A node is occupied if a lymphocyte clone of the corresponding idiotype exists; otherwise it is empty. There is a continuous influx of new B lymphocytes of random idiotype from the bone marrow. B lymphocytes are stimulated by cross-linking their receptors with complementary structures. If there are too many complementary structures, steric hindrance prevents cross-linking. Stimulated cells proliferate and secrete antibodies of the same idiotype as their receptors; unstimulated lymphocytes die. Depending on few parameters, the autonomous system evolves randomly towards patterns of highly organized architecture, where the nodes can be classified into groups according to their statistical properties. We observe and describe analytically the building principles of these patterns, which make it possible to calculate number and size of the node groups and the number of links between them. The architecture of all patterns observed so far in simulations can be explained this way. A tool for real-time pattern identification is proposed.

Common and unique network dynamics in football games

The sport of football is played between two teams of eleven players each using a spherical ball. Each team strives to score by driving the ball into the opposing goal as the result of skillful interactions among players. Football can be regarded from the network perspective as a competitive relationship between two cooperative networks with a dynamic network topology and dynamic network node. Many complex large-scale networks have been shown to have topological properties in common, based on a small-world network and scale-free network models. However, the human dynamic movement pattern of this network has never been investigated in a real-world setting. Here, we show that the power law in degree distribution emerged in the passing behavior in the 2006 FIFA World Cup Final and an international “A” match in Japan, by describing players as vertices connected by links representing passes. The exponent values are similar to the typical values that occur in many real-world networks, which are in the range of , and are larger than that of a gene transcription network, . Furthermore, we reveal the stochastically switched dynamics of the hub player throughout the game as a unique feature in football games. It suggests that this feature could result not only in securing vulnerability against intentional attack, but also in a power law for self-organization. Our results suggest common and unique network dynamics of two competitive networks, compared with the large-scale networks that have previously been investigated in numerous works. Our findings may lead to improved resilience and survivability not only in biological networks, but also in communication networks.

Local-global interaction and the emergence of scale-free networks with community structures

Understanding complex networks in the real world is a nontrivial task. In the study of community structures we normally encounter several examples of these networks, which makes any statistical inferencing a challenging endeavor. Researchers resort to computer-generated networks that resemble networks encountered in the real world as a means to generate many networks with different sizes, while maintaining the real-world characteristics of interest. The generation of networks that resemble the real world turns out in itself to be a complex search problem. We present a new rewiring algorithm for the generation of networks with unique characteristics that combine the scale-free effects and community structures encountered in the real world. The algorithm is inspired by social interactions in the real world, whereby people tend to connect locally while occasionally they connect globally. This local-global coupling turns out to be a powerful characteristics that is required for our proposed rewiring algorithm to generate networks with community structures, power law distributions both in degree and in community size, positive assortative mixing by degree, and the rich-club phenomenon.

Competition for popularity in bipartite networks

We present a dynamical model for rewiring and attachment in bipartite networks. Edges are placed between nodes that belong to catalogs that can either be fixed in size or growing in size. The model is motivated by an empirical study of data from the video rental service Netflix, which invites its users to give ratings to the videos available in its catalog. We find that the distribution of the number of ratings given by users and that of the number of ratings received by videos both follow a power law with an exponential cutoff. We also examine the activity patterns of Netflix users and find bursts of intense video-rating activity followed by long periods of inactivity. We derive ordinary differential equations to model the acquisition of edges by the nodes over time and obtain the corresponding time-dependent degree distributions. We then compare our results with the Netflix data and find good agreement. We conclude with a discussion of how catalog models can be used to study systems in which agents are forced to choose, rate, or prioritize their interactions from a large set of options.

Software engineering and scale-free networks

Complex-network theory is a new approach in studying different types of large systems in both the physical and the abstract worlds. In this paper, we have studied two kinds of network from software engineering: the component dependence network and the sorting comparison network (SCN). It is found that they both show the same scale-free property under certain conditions as complex networks in other fields. These results suggest that complex-network theory can be a useful approach to the study of software systems. The special properties of SCNs provide a more repeatable and deterministic way to study the evolution and optimization of complex networks. They also suggest that the closer a sorting algorithm is to the theoretical optimal limit, the more its SCN is like a scale-free network. This may also indicate that, to store and retrieve information efficiently, a concept network might need to be scale-free.

Asymmetric disassembly and robustness in declining networks

Mechanisms that enable declining networks to avert structural collapse and performance degradation are not well understood. This knowledge gap reflects a shortage of data on declining networks and an emphasis on models of network growth. Analyzing >700,000 transactions between firms in the New York garment industry over 19 years, we tracked this network's decline and measured how its topology and global performance evolved. We find that favoring asymmetric (disassortative) links is key to preserving the topology and functionality of the declining network. Based on our findings, we tested a model of network decline that combines an asymmetric disassembly process for contraction with a preferential attachment process for regrowth. Our simulation results indicate that the model can explain robustness under decline even if the total population of nodes contracts by more than an order of magnitude, in line with our observations for the empirical network. These findings suggest that disassembly mechanisms are not simply assembly mechanisms in reverse and that our model is relevant to understanding the process of decline and collapse in a broad range of biological, technological, and financial networks.

Multicommunity weight-driven bipartite network model

Community structure and rewiring phenomena exist in many complex networks, particularly in bipartite networks. We construct a model for the degree distribution of the rewiring problem in a multicommunity weight-driven bipartite network (MCWBN). The network consists of many interconnected communities, each of which holds a bipartite graph. The bipartite graph consists of two sets of nodes. We name each node in one set a "producer" and each node in the other set a "consumer." A weight value matrix defining the trade barrier between any two communities is used to characterize the structure of the communities, which ensures the higher preferential attachment probability in intracommunity than in intercommunity. The size of one producer is defined as the number of consumers connected to it. We find that the nonlinear dynamics of the scale of production, or the total size of all producers in each community is dependent only on the initial scale of production in each community, and independent of the distribution of the producer size. Furthermore, if the nonlinear system of the scale of production in each community is at an equilibrium state, the distribution of the producer size in each community of the MCWBN model is equivalent to that in a one-community model.

Higher-order distributions and nongrowing complex networks without multiple connections

We study stochastic processes that generate nongrowing complex networks without self-loops and multiple edges (simple graphs). The work concentrates on understanding and formulation of constraints which keep the rewiring stochastic processes within the class of simple graphs. To formulate these constraints a different concept of wedge distribution (paths of length 2) is introduced and its relation to degree-degree correlation is studied. The analysis shows that the constraints, together with edge selection rules, do not even allow the formulation of a closed master equation in the general case. We also introduce a particular stochastic process which does not contain edge selection rules, but which, we believe, can provide some insight into the complexities of simple graphs.

Self-organization and neuronal avalanches in networks of dissociated cortical neurons

Dissociated cortical neurons from rat embryos cultured onto micro-electrode arrays exhibit characteristic patterns of electrophysiological activity, ranging from isolated spikes in the first days of development to highly synchronized bursts after 3-4 weeks in vitro. In this work we analyzed these features by considering the approach proposed by the self-organized criticality theory: we found that networks of dissociated cortical neurons also generate spontaneous events of spreading activity, previously observed in cortical slices, in the form of neuronal avalanches. Choosing an appropriate time scale of observation to detect such neuronal avalanches, we studied the dynamics by considering the spontaneous activity during acute recordings in mature cultures and following the development of the network. We observed different behaviors, i.e. sub-critical, critical or super-critical distributions of avalanche sizes and durations, depending on both the age and the development of cultures. In order to clarify this variability, neuronal avalanches were correlated with other statistical parameters describing the global activity of the network. Criticality was found in correspondence to medium synchronization among bursts and high ratio between bursting and spiking activity. Then, the action of specific drugs affecting global bursting dynamics (i.e. acetylcholine and bicuculline) was investigated to confirm the correlation between criticality and regulated balance between synchronization and variability in the bursting activity. Finally, a computational model of neuronal network was developed in order to interpret the experimental results and understand which parameters (e.g. connectivity, excitability) influence the distribution of avalanches. In summary, cortical neurons preserve their capability to self-organize in an effective network even when dissociated and cultured in vitro. The distribution of avalanche features seems to be critical in those cultures displaying medium synchronization among bursts and poor random spiking activity, as confirmed by chemical manipulation experiments and modeling studies.

How scale-free networks and large-scale collective cooperation emerge in complex homogeneous social systems

We study how heterogeneous degree distributions and large-scale collective cooperation in social networks emerge in complex homogeneous systems by a simple local rule: learning from the best in both strategy selections and linking choices. The prisoner's dilemma game is used as the local dynamics. We show that the social structure may evolve into single-scale, broad-scale, and scale-free (SF) degree distributions for different control parameters. In particular, in a relatively strong-selfish parameter region the SF property can be self-organized in social networks by dynamic evolutions and these SF structures help the whole node community to reach a high level of cooperation under the poor condition of a high selfish intention of individuals.

Exact solution for the time evolution of network rewiring models

We consider the rewiring of a bipartite graph using a mixture of random and preferential attachment. The full mean-field equations for the degree distribution and its generating function are given. The exact solution of these equations for all finite parameter values at any time is found in terms of standard functions. It is demonstrated that these solutions are an excellent fit to numerical simulations of the model. We discuss the relationship between our model and several others in the literature, including examples of urn, backgammon, and balls-in-boxes models, the Watts and Strogatz rewiring problem, and some models of zero range processes. Our model is also equivalent to those used in various applications including cultural transmission, family name and gene frequencies, glasses, and wealth distributions. Finally some Voter models and an example of a minority game also show features described by our model.