Exactly solvable scale-free network model

Hierarchical deposition and scale-free networks: A visibility algorithm approach

The growth of an interface formed by the hierarchical deposition of particles of unequal size is studied in the framework of a dynamical network generated by a horizontal visibility algorithm. For a deterministic model of the deposition process, the resulting network is scale free with dominant degree exponent γ_{e}=ln3/ln2 and transient exponent γ_{o}=1. An exact calculation of the network diameter and clustering coefficient reveals that the network is scale invariant and inherits the modular hierarchical nature of the deposition process. For the random process, the network remains scale free, where the degree exponent asymptotically converges to γ=3, independent of the system parameters. This result shows that the model is in the class of fractional Gaussian noise through the relation between the degree exponent and the series' Hurst exponent H. Finally, we show through the degree-dependent clustering coefficient C(k) that the modularity remains present in the system.

Two-point resistances in an Apollonian network

The computation of resistance between two nodes in a resistor network is a classical problem in electric theory and graph theory. Based on the Apollonian packing, Andrade et al. introduced a deterministic growing type of networks A(k) [Phys. Rev. Lett. 94, 018702 (2005)PRLTAO0031-900710.1103/PhysRevLett.94.018702]. In this paper, first, a recursive algorithm for computing resistance between any two nodes in A(k) is given. Then as explanations, using the algorithm, explicit expressions for some resistances in A(k) are obtained.

Multiple-node basin stability in complex dynamical networks

Dynamical entities interacting with each other on complex networks often exhibit multistability. The stability of a desired steady regime (e.g., a synchronized state) to large perturbations is critical in the operation of many real-world networked dynamical systems such as ecosystems, power grids, the human brain, etc. This necessitates the development of appropriate quantifiers of stability of multiple stable states of such systems. Motivated by the concept of basin stability (BS) [P. J. Menck et al., Nat. Phys. 9, 89 (2013)1745-247310.1038/nphys2516], we propose here the general framework of multiple-node basin stability for gauging the global stability and robustness of networked dynamical systems in response to nonlocal perturbations simultaneously affecting multiple nodes of a system. The framework of multiple-node BS provides an estimate of the critical number of nodes that, when simultaneously perturbed, significantly reduce the capacity of the system to return to the desired stable state. Further, this methodology can be applied to estimate the minimum number of nodes of the network to be controlled or safeguarded from external perturbations to ensure proper operation of the system. Multiple-node BS can also be utilized for probing the influence of spatially localized perturbations or targeted attacks to specific parts of a network. We demonstrate the potential of multiple-node BS in assessing the stability of the synchronized state in a deterministic scale-free network of Rössler oscillators and a conceptual model of the power grid of the United Kingdom with second-order Kuramoto-type nodal dynamics.

Random walks in unweighted and weighted modular scale-free networks with a perfect trap

Designing optimal structure favorable to diffusion and effectively controlling the trapping process are crucial in the study of trapping problem--random walks with a single trap. In this paper, we study the trapping problem occurring on unweighted and weighted networks, respectively. The networks under consideration display the striking scale-free, small-world, and modular properties, as observed in diverse real-world systems. For binary networks, we concentrate on three cases of trapping problems with the trap located at a peripheral node, a neighbor of the root with the least connectivity, and a farthest node, respectively. For weighted networks with edge weights controlled by a parameter, we also study three trapping problems, in which the trap is placed separately at the root, a neighbor of the root with the least degree, and a farthest node. For all the trapping problems, we obtain the analytical formulas for the average trapping time (ATT) measuring the efficiency of the trapping process, as well as the leading scaling of ATT. We show that for all the trapping problems in the binary networks with a trap located at different nodes, the dominating scalings of ATT reach the possible minimum scalings, implying that the networks have optimal structure that is advantageous to efficient trapping. Furthermore, we show that for trapping in the weighted networks, the ATT is controlled by the weight parameter, through modifying which, the ATT can behave superlinearly, linearly, sublinearly, or logarithmically with the system size. This work could help improving the design of systems with efficient trapping process and offers new insight into control of trapping in complex systems.

Exact calculations of first-passage quantities on recursive networks

We present general methods to exactly calculate mean first-passage quantities on self-similar networks defined recursively. In particular, we calculate the mean first-passage time and the splitting probabilities associated to a source and one or several targets; averaged quantities over a given set of sources (e.g., same-connectivity nodes) are also derived. The exact estimate of such quantities highlights the dependency of first-passage processes with respect to the source-target distance, which has recently revealed to be a key parameter in characterizing transport in complex media. We explicitly perform calculations for different classes of recursive networks [finitely ramified fractals, scale-free (trans)fractals, nonfractals, mixtures between fractals and nonfractals, nondecimable hierarchical graphs] of arbitrary size. Our approach unifies and significantly extends the available results in the field.

Random walks in modular scale-free networks with multiple traps

Extensive empirical investigation has shown that a plethora of real networks synchronously exhibit scale-free and modular structure and it is thus of great importance to uncover the effects of these two striking properties on various dynamical processes occurring on such networks. In this paper, we examine two cases of random walks performed on a class of modular scale-free networks with multiple traps located at several given nodes. We first derive a formula of the mean first-passage time (MFPT) for a general network, which is the mean of the expected time to absorption originating from a specific node, averaged over all nontrap starting nodes. Although the computation is complex, the expression of the formula is exact; moreover, the computational approach and procedure are independent of the number and position of the traps. We then determine analytically the MFPT for the two random walks being considered. The obtained analytical results are in complete agreement with the numerical ones. Our results show that the number and location of traps play an important role in the behavior of the MFPT, since for both cases the MFPT grows as a power-law function of the number of nodes, but their exponents are quite different. We demonstrate that the root of the difference in the behavior of MFPT is attributed to the modular and scale-free topologies of the networks. This work can deepen the understanding of diffusion on networks with modular and scale-free architecture and motivate relevant studies for random walks running on complex random networks with multiple traps.

Effective target arrangement in a deterministic scale-free graph

We study the random-walk problem on a deterministic scale-free network, in the presence of a set of static, identical targets; due to the strong inhomogeneity of the underlying structure the mean first-passage time (MFPT), meant as a measure of transport efficiency, is expected to depend sensitively on the position of targets. We consider several spatial arrangements for targets and we calculate, mainly rigorously, the related MFPT, where the average is taken over all possible starting points and over all possible paths. For all the cases studied, the MFPT asymptotically scales like ∼Nθ, being N the volume of the substrate and θ ranging from 1-log 2/log 3, for central target(s), to 1, for a single peripheral target.

Random walks on deterministic scale-free networks: exact results

We study the random walk problem on a class of deterministic scale-free networks displaying a degree sequence for hubs scaling as a power law with an exponent gamma=log 3/log 2. We find exact results concerning different first-passage phenomena and, in particular, we calculate the probability of first return to the main hub. These results allow to derive the exact analytic expression for the mean time to first reach the main hub, whose leading behavior is given by tau approximately V1-1/gamma, where V denotes the size of the structure, and the mean is over a set of starting points distributed uniformly over all the other sites of the graph. Interestingly, the process turns out to be particularly efficient. We also discuss the thermodynamic limit of the structure and some local topological properties.

Evolving Apollonian networks with small-world scale-free topologies

We propose two types of evolving networks: evolutionary Apollonian networks (EANs) and general deterministic Apollonian networks (GDANs), established by simple iteration algorithms. We investigate the two networks by both simulation and theoretical prediction. Analytical results show that both networks follow power-law degree distributions, with distribution exponents continuously tuned from 2 to 3. The accurate expression of clustering coefficient is also given for both networks. Moreover, the investigation of the average path length of EAN and the diameter of GDAN reveals that these two types of networks possess small-world feature. In addition, we study the collective synchronization behavior on some limitations of the EAN.

Growth model for complex networks with hierarchical and modular structures

A hierarchical and modular network model is suggested by adding a growth rule along with the preferential attachment (PA) rule into Motter's modeling procedure. The proposed model has an increasing number of vertices but a fixed number of modules and hierarchical levels. The vertices form lowest-level modules which in turn constitute higher-level modules hierarchically. The creation of connections between two vertices in a single module or in two different modules of the same level obeys the PA rule. The structural characteristics of this model are investigated analytically and numerically. The results show that the degree distribution, the module size distribution, and the clustering function of the model possess a power-law property which is similar to that in many real-world networks. The model is then used to predict the growth trends of real-world networks with modular and hierarchical structures. By comparing this model with those real-world networks, an interesting conclusion is found: that many real-world networks are in their early stages of development, and when the growth time is large enough, the modules and levels of the networks will be ultimately merged.

Spectral properties of disordered fully connected graphs

The spectral properties of disordered fully connected graphs with a special type of node-node interactions are investigated. The approximate analytical expression for the ensemble-averaged spectral density for the Hamiltonian defined on the fully connected graph is derived and analyzed for both the electronic and vibrational problems which can be related to the contact process and to the problem of stochastic diffusion, respectively. It is demonstrated how to evaluate the extreme eigenvalues and use them for finding the lower-bound estimates of the critical parameter for the contact process on the disordered fully connected graphs.