A new deterministic complex network model with hierarchical structure

We introduce a new simple pseudo tree-like network model, deterministic complex network (DCN). The proposed DCN model may simulate the hierarchical structure nature of real networks appropriately and have the unique property of ‘skipping the levels’, which is ubiquitous in social networks. Our results indicate that the DCN model has a rather small average path length and large clustering coefficient, leading to the small-world effect. Strikingly, our DCN model obeys a discrete power-law degree distribution P(k)∝k^−γ, with exponent γ approaching 1.0. We also discover that the relationship between the clustering coefficient and degree follows the scaling law C(k)∼k⁻¹, which quantitatively determines the DCN's hierarchical structure.     

Scale-free networks by super-linear preferential attachment rule

A network growth model with geographic limitation of accessible information about the status of existing nodes is investigated. In this model, the probability Π(k) of an existing node of degree k is found to be super-linear with Π(k)∼k^α and α>1 when there are links from new nodes. The numerical results show that the constructed networks have typical power-law degree distributions P(k)∼k^−γ and the exponent γ depends on the constraint level. An analysis of local structural features shows the robust emergence of scale-free network structure in spite of the super-linear preferential attachment rule. This local structural feature is directly associated with the geographical connection constraints which are widely observed in many real networks.     

Network topology and correlation features affiliated with European airline companies

The physics information of four specific airline flight networks in European Continent, namely the Austrian airline, the British airline, the France-Holland airline and the Lufthhansa airline, was quantitatively analyzed by the concepts of a complex network. It displays some features of small-world networks, namely a large clustering coefficient and small average shortest-path length for these specific airline networks. The degree distributions for the small degree branch reveal power law behavior with an exponent value of 2-3 for the Austrian and the British flight networks, and that of 1-2 for the France-Holland and the Lufthhansa airline flight networks. So the studied four airlines are sorted into two classes according to the topology structure. Similarly, the flight weight distributions show two kinds of different decay behavior with the flight weight: one for the Austrian and the British airlines and another for the France-Holland airline and the Lufthhansa airlines. In addition, the degree-degree correlation analysis shows that the network has disassortative behavior for all the value of degree k, and this phenomenon is different from the international airline network and US airline network. Analysis of the clustering coefficient (C(k)) versus k, indicates that the flight networks of the Austrian Airline and the British Airline reveal a hierarchical organization for all airports, however, the France-Holland Airline and the Lufthhansa Airline show a hierarchical organization mostly for larger airports. The correlation of node strength (S(k)) and degree is also analyzed, and a power-law fit S(k)∼k^1.1 can roughly fit all data of these four airline companies. Furthermore, we mention seasonal changes and holidays may cause the flight network to form a different topology. An example of the Austrian Airline during Christmas was studied and analyzed.     

An extended clique degree distribution and its heterogeneity in cooperation-competition networks

After Xiao et al. [W.-K. Xiao, J. Ren, F. Qi, Z.W. Song, M.X. Zhu, H.F. Yang, H.Y. Jin, B.-H. Wang, Tao Zhou, Empirical study on clique-degree distribution of networks, Phys. Rev. E 76 (2007) 037102], in this article we present an investigation on so-called k-cliques, which are defined as complete subgraphs of k (k>1) nodes, in the cooperation-competition networks described by bipartite graphs. In the networks, the nodes named actors are taking part in events, organizations or activities, named acts. We mainly examine a property of a k-clique called “k-clique act degree”, q, defined as the number of acts, in which the k-clique takes part. Our analytic treatment on a cooperation-competition network evolution model demonstrates that the distribution of k-clique act degrees obeys Mandelbrot distribution, P(q)∝(q+α)^−γ. To validate the analytical model, we have further studied 13 different empirical cooperation-competition networks with the clique numbers k=2 and k=3. Empirical investigation results show an agreement with the analytic derivations. We propose a new “heterogeneity index”, H, to describe the heterogeneous degree distributions of k-clique and heuristically derive the correlation between H and α and γ. We argue that the cliques, which take part in the largest number of acts, are the most important subgraphs, which can provide a new criterion to distinguish important cliques in the real world networks.     

A scale-free network with limiting on vertices

We propose and analyze a random graph model which explains a phenomena in the economic company network in which company may not expand its business at some time due to the limiting of money and capacity. The random graph process is defined as follows: at any time-step t, (i) with probability α(k) and independently of other time-step, each vertex is inactive which means it cannot be connected by more edges, where k is the degree of v_i at the time-step t; (ii) a new vertex v_t is added along with m edges incident with v_t at one time and its neighbors are chosen in the manner of preferential attachment. We prove that the degree distribution P(k) of this random graph process satisfies if α(⋅) is a constant α₀; and P(k)∝C₂k⁻³ if α(?)↓0 as ?↑∞, where C₁,C₂ are two positive constants. The analytical result is found to be in good agreement with that obtained by numerical simulations. Furthermore, we get the degree distributions in this model with m-varying functions by simulation.     

Fluctuations with a 1/f α spectrum in nonequilibrium phase transitions in a spatially distributed system

Statistics of fluctuations in a spatially distributed system describing the interaction of nonequilibrium phase transitions is studied. It is shown that for a certain value of the intensity of external white noise acting on phase transitions, the time and spatial spectra of fluctuations exhibit power dependences S(f) ～ f ^?α and S(k) ～ k ^?γ. The dependence of exponents α and γ on the diffusion coefficient determining the spatial interaction of fluctuations is determined. Extremal low-frequency fluctuations are singled out and the distribution functions of their duration (P(τ) ～ τ^?β) and size (P(s) ～ s^?ν)) are constructed. It is found that exponent α in the time spectral dependence and exponent β in the duration of fluctuations are connected via the relation α + β = 2. Exponents γ and ν in the spatial spectral dependence and in the size distribution function are connected via an analogous relation (γ + ν = 2).     

A Monte Carlo model for networks between professionals and society

We propose a network model with a fixed number of nodes and links and with a dynamic which favors links between nodes differing in connectivity. We observe a phase transition and parameter regimes with degree distributions following power laws, P(k)∼k^-γ$P(k)\sim k^{-\gamma }$, with γ$\gamma$ ranging from 0.2$0.2$ to 0.5$0.5$, small-world properties, with a network diameter following D(N)∼logN$D(N)\sim \log N$ and relative high clustering, following C(N)∼1/N$C(N)\sim 1/N$ and C(k)∼k^-α$C(k)\sim k^{-\alpha }$, with α$\alpha$ close to 3. We compare our results with data from real-world protein interaction networks.     

Dynamical theory for photon and photoelectric pulse distributions in single molecule fluorescence

A single two-level molecule driven by CW-laser field and a photomultiplier tube (PMT) are considered as two parts of the united dynamical system connected with each other by photons of molecular fluorescence. Each PMT is characterized by a rate α of photo-effect and by a rate β of PMT recovery. A theory for the photon distribution function w_N(t) and for the photoelectric pulse distribution function f_n(t) for such a system is built up. If times 1/ α and 1/ β characterizing PMT are much shorter as compared to the average time interval 1/ k between two successively emitted photons of fluorescence, the photon and the photoelectron distribution functions coincide with each other, i.e. f_n(t) ≅ w_N(t). A relation between w_N(t) and f_n(t) is studied in detail for the case in which PMT works slower as compared to the rate k of photon emission, i.e. at 1/ α, 1/ β ≥ 1/ k.     

Epidemic outbreaks in growing scale-free networks with local structure

The class of generative models has already attracted considerable interest from researchers in recent years and much expanded the original ideas described in BA model. Most of these models assume that only one node per time step joins the network. In this paper, we grow the network by adding n interconnected nodes as a local structure into the network at each time step with each new node emanating m new edges linking the node to the preexisting network by preferential attachment. This successfully generates key features observed in social networks. These include power-law degree distribution p_k∼k^−(3+μ), where μ=(n−1)/m is a tuning parameter defined as the modularity strength of the network, nontrivial clustering, assortative mixing, and modular structure. Moreover, all these features are dependent in a similar way on the parameter μ. We then study the susceptible-infected epidemics on this network with identical infectivity, and find that the initial epidemic behavior is governed by both of the infection scheme and the network structure, especially the modularity strength. The modularity of the network makes the spreading velocity much lower than that of the BA model. On the other hand, increasing the modularity strength will accelerate the propagation velocity.     

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.     

Asymptotic inverse spectral problem for anharmonic oscillators

We study perturbationsL=A+B of the harmonic oscillatorA=1/2(??²+x ²?1) on ?, when potentialB(x) has a prescribed asymptotics at ∞,B(x)～|x|^?α V(x) with a trigonometric even functionV(x)=Σa _mcosω _m x. The eigenvalues ofL are shown to be λ _k =k+μ _k with small μ _k =O(k ^?γ), γ=1/2+1/4. The main result of the paper is an asymptotic formula for spectral fluctuations {μ _k }, $$\mu _k \sim k^{ - \gamma } \tilde V(\sqrt {2k} ) + c/\sqrt {2k} ask \to \infty ,$$ whose leading term \(\tilde V\) represents the so-called “Radon transform” ofV, $$\tilde V(x) = const\sum {\frac{{a_m }}{{\sqrt {\omega _m } }}\cos (\omega _m x - \pi /4)} .$$ as a consequence we are able to solve explicitly the inverse spectral problem, i.e., recover asymptotic part |x ^?α|V(x) ofB from asymptotics of {µ _k }. ₁ ^∞      

Edge-based-attack induced cascading failures on scale-free networks

Most previous existing works on cascading failures only focused on attacks on nodes rather than on edges. In this paper, we discuss the response of scale-free networks subject to two different attacks on edges during cascading propagation, i.e., edge removal by either the descending or ascending order of the loads. Adopting a cascading model with a breakdown probability p of an overload edge and the initial load (k_ik_j)^α of an edge ij, where k_i and k_j are the degrees of the nodes connected by the edge ij and α is a tunable parameter, we investigate the effects of two attacks for the robustness of Barabási-Albert (BA) scale-free networks against cascading failures. In the case of α<1, our investigation by the numerical simulations leads to a counterintuitive finding that BA scale-free networks are more sensitive to attacks on the edges with the lowest loads than the ones with the highest loads, not relating to the breakdown probability. In addition, the same effect of two attacks in the case of α=1 may be useful in furthering studies on the control and defense of cascading failures in many real-life networks. We then confirm by the theoretical analysis these results observed in simulations.     

Assortativity of complementary graphs

Newman's measure for (dis)assortativity, the linear degree correlationρ _D , is widely studied although analytic insight into the assortativity of an arbitrary network remains far from well understood. In this paper, we derive the general relation (2), (3) and Theorem 1 between the assortativity ρ _D (G) of a graph G and the assortativityρ _D (G ^c) of its complement G ^c. Both ρ _D (G) and ρ _D (G ^c) are linearly related by the degree distribution in G. When the graph G(N,p) possesses a binomial degree distribution as in the Erd?s-Rényi random graphs G _p (N), its complementary graph G _p ^c (N) = G _{1- p} (N) follows a binomial degree distribution as in the Erd?s-Rényi random graphs G _{1- p} (N). We prove that the maximum and minimum assortativity of a class of graphs with a binomial distribution are asymptotically antisymmetric: ρ _max(N,p) = -ρ _min(N,p) for N → ∞. The general relation (3) nicely leads to (a) the relation (10) and (16) between the assortativity range ρ _max(G)–ρ _min(G) of a graph with a given degree distribution and the range ρ _max(G ^c)–ρ _min(G ^c) of its complementary graph and (b) new bounds (6) and (15) of the assortativity. These results together with our numerical experiments in over 30 real-world complex networks illustrate that the assortativity range ρ _max–ρ _min is generally large in sparse networks, which underlines the importance of assortativity as a network characterizer.     

Systems with separable many-particle interactions. I

In this paper we give an exact evaluation of the free energy per particle for systems with separable many-particle interactions described by a hamiltonian of the type ? = ∑_kT(k) + NP (N^-1 ∑_kV(k)), where P is an arbitrary polynomial. In the proof use is made of a fundamental theorem due to Bogoliubov Jr. for ferromagnetic quadratic operators. The free energy can be obtained from a trial hamiltonian, which is linear in the operators T and V.     

Triadic Closure in Configuration Models with Unbounded Degree Fluctuations

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for \(k=\varOmega (\sqrt{n})\) settles on a power law \(c(k)\sim n^{5-2\tau }k^{-2(3-\tau )}\) with \(\tau \in (2,3)\) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

The Combined Effect of Connectivity and Dependency Links on Percolation of Networks

Percolation theory is extensively studied in statistical physics and mathematics with applications in diverse fields. However, the research is focused on systems with only one type of links, connectivity links. We review a recently developed mathematical framework for analyzing percolation properties of realistic scenarios of networks having links of two types, connectivity and dependency links. This formalism was applied to study Erdős-Rényi (ER) networks that include also dependency links. For an ER network with average degree [`(k)]\bar{k} that is composed of dependency clusters of size s, the fraction of nodes that belong to the giant component, P <sub>∞</sub>, is given by P<sub>￥</sub>=p<sup>s-1</sup>[1-exp(-[`(k)]pP_￥) ]^sP_{\infty}=p^{s-1}[1-\exp{(-\bar{k}pP_{\infty})} ]^{s} where 1−p is the initial fraction of randomly removed nodes. Here, we apply the formalism to the study of random-regular (RR) networks and find a formula for the size of the giant component in the percolation process: P _∞=p ^s−1(1−r ^k ) ^s where r is the solution of r=p ^s (r ^k−1−1)(1−r ^k )+1, and k is the degree of the nodes. These general results coincide, for s=1, with the known equations for percolation in ER and RR networks respectively without dependency links. In contrast to s=1, where the percolation transition is second order, for s>1 it is of first order. Comparing the percolation behavior of ER and RR networks we find a remarkable difference regarding their resilience. We show, analytically and numerically, that in ER networks with low connectivity degree or large dependency clusters, removal of even a finite number (zero fraction) of the infinite network nodes will trigger a cascade of failures that fragments the whole network. Specifically, for any given s there exists a critical degree value, [`(k)]<sub>min</sub>\bar{k}_{\min}, such that an ER network with [`(k)] ￡ [`(k)]_min\bar{k}\leq \bar{k}_{\min} is unstable and collapse when removing even a single node. This result is in contrast to RR networks where such cascades and full fragmentation can be triggered only by removal of a finite fraction of nodes in the network.     

A model for cascading failures in scale-free networks with a breakdown probability

Considering that not all overload nodes will be removed from networks due to some effective measures to protect them, we propose a new cascading model with a breakdown probability. Adopting the initial load of a node j to be L_j=[k_j(∑_m∈Γjk_m)]^α with k_j and Γ_j being the degree of the node j and the set of its neighboring nodes, respectively, where α is a tunable parameter, we investigate the relationship between some parameters and universal robustness characteristics against cascading failures on scale-free networks. According to a new measure originated from a phase transition from the normal state to collapse, the numerical simulations show that Barabási-Albert (BA) networks reach the strongest robustness level against cascading failures when the tunable parameter α=0.5, while not relating to the breakdown probability. We furthermore explore the effect of the average degree 〈k〉 for network robustness, thus obtaining a positive correlation between 〈k〉 and network robustness. We then analyze the effect of the breakdown probability on the network robustness and confirm by theoretical predictions this universal robustness characteristic observed in simulations. Our work may have practical implications for controlling various cascading-failure-induced disasters in the real world.