Phase transitions and overlapping modules in complex networks

Complex systems can be described in terms of networks capturing the intricate web of connections among the units they are made of. Here we review two aspects of the possible organization of such networks. First, we provide a phenomenological theory for topological transitions in restructuring networks. In this statistical mechanical approach energy is assigned to the different network topologies and temperature is used as a quantity referring to the level of noise during the rewiring of the edges. In our studies we find a rich variety of topological phase transitions when the temperature is varied. These transitions signal singular changes in the essential features of the global structure. Next, we address a question of great current interest which is about the modular structure of networks. We describe, how to interpret the global organization as the coexistence of structural sub-units (modules or communities) associated with more highly interconnected parts. The existing deterministic methods used for large networks find separated communities, while most of the actual networks are made of highly overlapping cohesive groups of nodes. We describe a recently introduced an approach to analyze the main statistical features of the interwoven sets of overlapping communities making a step towards the uncovering of the modular structure of complex systems. Our approach is based on defining communities as clusters of percolating complete subgraphs called k-cliques. We present the basic features of the associated percolation transition of overlapping k-cliques. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique to explore overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks.     

Tuning degree distributions: Departing from scale-free networks

Scale-free networks are characterized by a degree distribution with power-law behavior. Although scale-free networks have been shown to arise in many areas, ranging from the World Wide Web to transportation or social networks, degree distributions of other observed networks often differ from the power-law type. Data based investigations require modifications of the typical scale-free network.We present an algorithm that generates networks in which the shape of the degree distribution is tunable by modifying the preferential attachment step of the Barabási-Albert construction algorithm. The shape of the distribution is represented by dispersion measures such as the variance and the skewness, both of which are highly correlated with the maximal degree of the network and, therefore, adequately represents the influence of superspreaders or hubs. By combining our algorithm with work of Holme and Kim, we show how to generate networks with a variety of degree distributions and clustering coefficients.     

Topological relation of layered complex networks

We present analytically the relation functions between degrees or clustering coefficients of a common station in both space L layer and space P layer of transportation systems. A good agreement between the analytical results and the empirical investigations in a railway system and three bus systems in China is observed.     

A network model of the interbank market

This work introduces a network model of an interbank market based on interbank credit lending relationships. It generates some network features identified through empirical analysis. The critical issue to construct an interbank network is to decide the edges among banks, which is realized in this paper based on the interbank’s degree of trust. Through simulation analysis of the interbank network model, some typical structural features are identified in our interbank network, which are also proved to exist in real interbank networks. They are namely, a low clustering coefficient and a relatively short average path length, community structures, and a two-power-law distribution of out-degree and in-degree.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks

A large number of networks in the real world have a scale-free structure, and the parameters of the networks change stochastically with time. Searching for the shortest paths in a scale-free dynamic and stochastic network is not only necessary for the estimation of the statistical characteristics such as the average shortest path length of the network, but also challenges the traditional concepts related to the “shortest path” of a network and the design of path searching strategies. In this paper, the concept of shortest path is defined on the basis of a scale-free dynamic and stochastic network model, and a temporal ant colony optimization (TACO) algorithm is proposed for searching for the shortest paths in the network. The convergence and the setup for some important parameters of the TACO algorithm are discussed through theoretical analysis and computer simulations, validating the effectiveness of the proposed algorithm.     

Routing and wavelength assignment in WDM networks with dynamic link weight assignment

We consider the routing and wavelength assignment problem on wavelength division multiplexing networks without wavelength conversion. When the physical network and required connections are given, routing and wavelength assignment (RWA) is the problem to select a suitable path and wavelength among the many possible choices for each connection such that no two paths using the same wavelength pass through the same link. In wavelength division multiplexing (WDM) optical networks, there is need to maximize the number of connections established and to minimize the blocking probability using limited resources. In this paper, we have proposed three dynamic link weight assignment strategies that change the link weight according to the traffic. The performance of the existing trend and the proposed strategies is shown in terms of blocking probability. The simulation results show that all the proposed strategies perform better than the existing trend.     

On topological properties of the octahedral Koch network

In this article, we propose an octahedral Koch network exhibiting abundant new properties compared to the triangular Koch network. Analytical expressions for the degree distribution, clustering coefficient, and average path length are presented. The scale-free feature and small-world property of the octahedral Koch network are obtained via numerical analysis. Furthermore, we show that the octahedral Koch network is assortative. Finally, we show that the projection of the octahedral Koch network on the plane is the nearest neighbor coupled Koch network, and the critical exponents of degree distribution in the octahedral Koch network is greater than three.     

The nature of explosive percolation phase transition

In this Letter, we show that the explosive percolation is a novel continuous phase transition. The order-parameter-distribution histogram at the percolation threshold is studied in Erd?s-Rényi networks, scale-free networks, and square lattice. In finite system, two well-defined Gaussian-like peaks coexist, and the valley between the two peaks is suppressed with the system size increasing. This finite-size effect always appears in typical first-order phase transition. However, both of the two peaks shift to zero point in a power law manner, which indicates the explosive percolation is continuous in the thermodynamic limit. The nature of explosive percolation in all the three structures belongs to this novel continuous phase transition. Various scaling exponents concerning the order-parameter-distribution are obtained.     

Relationship between degree-rank distributions and degree distributions of complex networks

Both the degree distribution and the degree-rank distribution, which is a relationship function between the degree and the rank of a vertex in the degree sequence obtained from sorting all vertices in decreasing order of degree, are important statistical properties to characterize complex networks. We derive an exact mathematical relationship between degree-rank distributions and degree distributions of complex networks. That is, for arbitrary complex networks, the degree-rank distribution can be derived from the degree distribution, and the reverse is true. Using the mathematical relationship, we study the degree-rank distributions of scale-free networks and exponential networks. We demonstrate that the degree-rank distributions of scale-free networks follow a power law only if scaling exponent λ>2. We also demonstrate that the degree-rank distributions of exponential networks follow a logarithmic law. The simulation results in the BA model and the exponential BA model verify our results.     

On the motif distribution in random block-hierarchical networks

The distribution of motifs in random hierarchical topological networks defined by nonsymmetric random block-hierarchical adjacency matrices, is constructed for the first time. According to the classification of U. Alon et al. of network superfamilies (Milo et al., 2004 [11]) by their motifs distributions, our artificial directed random hierarchical networks fall into the superfamily of natural networks to which the neuron networks belong. This is the first example of a class of “handmade” topological networks with the motifs distribution as in a special class of natural networks of essential biological importance.     

Emergence and evolution of multiple clusters of attracting agents

We investigate a multi-agent system with a behavior akin to the cluster formation in systems of coupled oscillators. The saturating attractive interactions between an infinite number of non-identical agents, characterized by a multimodal distribution of their natural velocities, lead to the emergence of clusters. We derive expressions that characterize the clusters, and calculate the asymptotic velocities of the agents and the critical value for the coupling strength under which no clustering can occur. The results are supported by mathematical analysis.For the particular case of a symmetric and unimodal distribution of the natural velocities, the relationship with the Kuramoto model of coupled oscillators is highlighted. While in the generic case the emergence of a cluster corresponds to a second-order phase transition, for a specific choice of the natural velocity distribution a first-order phase transition may occur, a phenomenon recently observed in the Kuramoto model. We also present an example for which the clustering behavior is quantitatively described in terms of the coupling strength.As an illustration of the potential of the model, we discuss how it applies to the dynamic process of opinion formation.     

Time evolution of the degree distribution of model A of random attachment growing networks

For random growing networks, Barabás and Albert proposed a kind of model in Barabás et al. [Physica A 272 (1999) 173], i.e. model A. In this paper, for model A, we give the differential format of master equation of degree distribution and obtain its analytical solution. The obtained result P(k, t) is the time evolution of degree distribution. P(k, t) is composed of two terms. At given finite time, one term decays exponentially, the other reflects size effect. At infinite time, the degree distribution is the same as that of Barabás and Albert. In this paper, we also discuss the normalization of degree distribution P(k, t) in detail.     

A topological phase transition between small-worlds and fractal scaling in urban railway transportation networks?

Fractal and small-worlds scaling laws are applied to study the growth of urban railway transportation networks using total length and total population as observational parameters. In spite of the variety of populations and urban structures, the variation of the total length of the railway network with the total population of conurbations follows similar patterns for large and middle metropolis. Diachronous analysis of data for urban transportation networks suggests that there is second-order phase transition from small-worlds behaviour to fractal scaling during their early stages of development.     

An inverse voter model for co-evolutionary networks: Stationary efficiency and phase transitions

In some co-evolutionary networks, the nodes always flip their states between two opposite ones, changing the types of the links to others correspondingly. Meanwhile, the link-rewiring and state-flipping processes feed back each other, and only the links between the nodes in the opposite states are productive in generating flow for the network. We propose an inverse voter model to depict the basic features of them. New phase transitions from full efficiency to deficiency state are found by both the analysis and simulations starting from the random graphs and small-world networks. We suggest a new way to measure the efficiency of networks.     

The nature of anharmonicity and anomalous piezoelectric properties of ferroelectric SbSBr crystal

The contribution of soft mode at Sb atom's sites, to the temperature dependences of Sb atom's equilibrium position's difference Δz(T) has been studied theoretically, when SbSBr crystal is deformed along a(x), b(y) and c(z)-axis in paraelectric phase and is deformed along c(z)-axis in ferroelectric phase. The largest change of Δz₃₃(T) occurs in the ferroelectric phase near the phase transition temperature in the range from 16 K to 21 K. The temperature dependence of Sb atom's equilibrium position's displacements Δz₃₃ is very similar to the temperature dependence of experimental piezoelectric modulus, when SbSBr crystal is deformed in the direction of c(z)-axis in ferroelectric phase.     

Characteristics of microRNA co-target networks

The database of microRNAs and their predicted target genes in humans were used to extract a microRNA co-target network. Based on the finding that more than two miRNAs can target the same gene, we constructed a microRNA co-target network and analyzed it from the perspective of the complex network. We found that a network having a positive assortative mixing can be characterized by small-world and scale-free characteristics which are found in most complex networks. The network was further analyzed by the nearest-neighbor average connectivity, and it was shown that the more assortative a microRNA network is, the wider the range of increasing average connectivity. In particular, an assortative network has a power-law relationship of the average connectivity with a positive exponent. A percolation analysis of the network showed that, although the network is diluted, there is no percolation transition in the network. From these findings, we infer that the microRNAs in the network are clustered together, forming a core group. The same analyses carried out on different species confirmed the robustness of the main results found in the microRNA networks of humans.     

A model of phase transitions in double-well Morse potential: Application to hydrogen bond

A model of phase transitions in double-well Morse potential is developed. Application of this model to the hydrogen bond is based on ab initio electron density calculations, which proved that the predominant contribution to the hydrogen bond energy originates from the interaction of proton with the electron shells of hydrogen-bonded atoms. This model uses a double-well Morse potential for proton. Analytical expressions for the hydrogen bond energy and the frequency of O–H stretching vibrations were obtained. Experimental data on the dependence of O–H vibration frequency on the bond length were successfully fitted with model-predicted dependences in classical and quantum mechanics approaches. Unlike empirical exponential function often used previously for dependence of O–H vibration frequency on the hydrogen bond length (Libowitzky, Mon. Chem., 1999, vol.130, 1047), the dependence reported here is theoretically substantiated.