Centrality measure of complex networks using biased random walks

We propose a novel centrality measure based on the dynamical properties of a biased random walk to provide a general framework for the centrality of vertex and edge in scale-free networks (SFNs). The suggested centrality unifies various centralities such as betweenness centrality (BC), load centrality (LC) and random walk centrality (RWC) when the degree, k, is relatively large. The relation between our centrality and other centralities in SFNs is clearly shown by both analytic and numerical methods. Regarding to the edge centrality, there have been few established studies in complex networks. Thus, we also provide a systematic analysis for the edge BC (LC) in SFNs and show that the distribution of edge BC satisfies a power-law. Furthermore we also show that the suggested centrality measures on real networks work very well as on the SFNs.     

Firing activity of complex space-clamped FitzHugh-Nagumo neural networks

We investigate how firing activity of complex neural networks depends on the random long-range connections and coupling strength. Network elements are described by excitable space-clamped FitzHugh-Nagumo (SCFHN) neurons with the values of parameters at which no firing activity occurs. It is found that for a given appropriate coupling strength C, there exists a critical fraction of random connections (or randomness) p^*, such that if p > p^* the firing neurons, which are absent in the nearest-neighbor network, occur. The firing activity becomes more frequent as randomness p is further increased. On the other hand, when the p is smaller, there are no active neurons in network, no matter what the value of C is. For a given larger p, there exist optimal coupling strength levels, where firing activity reaches its maximum. To the best of our knowledge, this is a novel mechanism for the emergence of firing activity in neurons.     

Epidemic threshold and phase transition in scale-free networks with asymmetric infection

We study the SIS epidemic dynamics on scale-freeweighted networks with asymmetric infection, by both analysis andnumerical simulations, with focus on the epidemic threshold aswell as critical behaviors. It is demonstrated that the asymmetryof infection plays an important role: we could redistribute theasymmetry to balance the degree heterogeneity of the network andthen to restore the epidemic threshold to a fnite value. On theother hand, we show that the absence of the epidemic threshold isnot so bad as commented previously since the prevalence grows veryslowly in this case and one could only protect a few vertices toprevent the diseases propagation.     

Recursive weighted treelike networks

We propose a geometric growth model for weighted scale-free networks, which is controlled by two tunable parameters. We derive exactly the main characteristics of the networks, which are partially determined by the parameters. Analytical results indicate that the resulting networks have power-law distributions of degree, strength, weight and betweenness, a scale-free behavior for degree correlations, logarithmic small average path length and diameter with network size. The obtained properties are in agreement with empirical data observed in many real-life networks, which shows that the presented model may provide valuable insight into the real systems.     

Kinetic models for wealth exchange on directed networks

We propose some kinetic models of wealth exchange and investigate their behavior on directed networks though numerical simulations. We observe that network topology and directedness yields a variety of interesting features in these models. The nature of asset distribution in such directed networks show varied results, the degree of asset inequality increased with the degree of disorder in the graphs.     

On the rich-club effect in dense and weighted networks

For many complex networks present in nature only a single instance, usually of large size, is available. Any measurement made on this single instance cannot be repeated on different realizations. In order to detect significant patterns in a real-world network it is therefore crucial to compare the measured results with a null model counterpart. Here we focus on dense and weighted networks, proposing a suitable null model and studying the behaviour of the degree correlations as measured by the rich-club coefficient. Our method solves an existing problem with the randomization of dense unweighted graphs, and at the same time represents a generalization of the rich-club coefficient to weighted networks which is complementary to other recently proposed ones.     

Voltage distribution in growing conducting networks

We investigate by random-walk simulations and a mean-field theory how growth by biased addition of nodes affects flow of the current through the emergent conducting graph, representing a digital circuit. In the interior of a large network the voltage varies with the addition time s < t of the node as V(s) ∼ ln(s)/s ^θ when constant current enters the network at last added node t and leaves at the root of the graph which is grounded. The topological closeness of the conduction path and shortest path through a node suggests that the charged random walk determines these global graph properties by using only local search algorithms. The results agree with mean-field theory on tree structures, while the numerical method is applicable to graphs of any complexity. Received 26 August 2002 Published online 29 November 2002     

Developmental time windows for spatial growth generate multiple-cluster small-world networks

Many networks extent in space, may it be metric (e.g. geographic) or non-metric (ordinal). Spatial network growth, which depends on the distance between nodes, can generate a wide range of topologies from small-world to linear scale-free networks. However, networks often lacked multiple clusters or communities. Multiple clusters can be generated, however, if there are time windows during development. Time windows ensure that regions of the network develop connections at different points in time. This novel approach could generate small-world but not scale-free networks. The resulting topology depended critically on the overlap of time windows as well as on the position of pioneer nodes.     

Spectral universality of phase synchronization in non-identical oscillator networks

We employ a spectral decomposition method to analyze synchronization of a non-identical oscillator network. We study the case that a small parameter mismatch of oscillators is characterized by one parameter and phase synchronization is observed. We derive a linearized equation for each eigenmode of the coupling matrix. The parameter mismatch is reflected on inhomogeneous term in the linearized equation. We find that the oscillation of each mode is essentially characterized only by the eigenvalue of the coupling matrix with a suitable normalization. We refer to this property as spectral universality, because it is observed irrespective of network topology. Numerical results in various network topologies show good agreement with those based on linearized equation. This universality is also observed in a system driven by additive independent Gaussian noise.     

Rank-based model for weighted network with hierarchical organization and disassortative mixing

In this paper, we study a rank-based model for weighted network. The evolution rule of the network is based on the ranking of node strength, which couples the topological growth and the weight dynamics. Analytically and by simulations, we demonstrate that the generated networks recover the scale-free distributions of degree and strength in the whole region of the growth dynamics parameter (α>0). Moreover, this network evolution mechanism can also produce scale-free property of weight, which adds deeper comprehension of the networks growth in the presence of incomplete information. We also characterize the clustering and correlation properties of this class of networks. It is showed that at α=1 a structural phase transition occurs, and for α>1 the generated network simultaneously exhibits hierarchical organization and disassortative degree correlation, which is consistent with a wide range of biological networks.     

Response of boolean networks to perturbations

We evaluate the probability that a Boolean network returns to an attractor after perturbing h nodes. We find that the return probability as function of h can display a variety of different behaviours, which yields insights into the state-space structure. In addition to performing computer simulations, we derive analytical results for several types of Boolean networks, in particular for Random Boolean Networks. We also apply our method to networks that have been evolved for robustness to small perturbations, and to a biological example.     

Loop statistics in complex networks

We study a scaling property of the number M_h(N) of loops of size h in complex networks with respect to a network size N. For networks with a bounded second moment of degree, we find two distinct scaling behaviors: M_h(N) ~ (constant) and M_h(N) ~ lnN as N increases. Uncorrelated random networks specified only with a degree distribution and Markovian networks specified only with a nearest neighbor degree-degree correlation display the former scaling behavior, while growing network models display the latter. The difference is attributed to structural correlation that cannot be captured by a short-range degree-degree correlation.     

Load-dependent random walks on complex networks

Load-dependent random walks are used to investigate the evolution of load distribution in transportation network systems. The walkers hop to a node according to node load of the last time step. The preference of walks leads to a change in the load distribution. It changes from degree-dependent distribution in the case of non-preference walks to eigenvector-centrality-dependent distribution. By numerical simulations, it is shown that the network heterogeneity has a influence on the effect of walk preference. In the cascading failure phenomenon, an appropriate degree correlation can guarantee a low risk of cascading failures.     

Topological properties of phylogenetic trees in evolutionary models

The extent to which evolutionary processes affect the shape of phylogenetic trees is an important open question. Analyses of small trees seem to detect non-trivial asymmetries which are usually ascribed to the presence of correlations in speciation rates. Many models used to construct phylogenetic trees have an algorithmic nature and are rarely biologically grounded. In this article, we analyze the topological properties of phylogenetic trees generated by different evolutionary models (populations of RNA sequences and a simple model with inheritance and mutation) and compare them with the trees produced by known uncorrelated models as the backward coalescent, paying special attention to large trees. Our results demonstrate that evolutionary parameters as mutation rate or selection pressure have a weak influence on the scaling behavior of the trees, while the size of phylogenies strongly affects measured scaling exponents. Within statistical errors, the topological properties of phylogenies generated by evolutionary models are compatible with those measured in balanced, uncorrelated trees.     

Network robustness to targeted attacks. The interplay of expansibility and degree distribution

We study the property of certain complex networks of being both sparse and highly connected, which is known as “good expansion” (GE). A network has GE properties if every subset S of nodes (up to 50% of the nodes) has a neighborhood that is larger than some “expansion factor” φ multiplied by the number of nodes in S. Using a graph spectral method we introduce here a new parameter measuring the good expansion character of a network. By means of this parameter we are able to classify 51 real-world complex networks — technological, biological, informational, biological and social — as GENs or non-GENs. Combining GE properties and node degree distribution (DD) we classify these complex networks in four different groups, which have different resilience to intentional attacks against their nodes. The simultaneous existence of GE properties and uniform degree distribution contribute significantly to the robustness in complex networks. These features appear solely in 14% of the 51 real-world networks studied here. At the other extreme we find that ∼40% of all networks are very vulnerable to targeted attacks. They lack GE properties, display skewed DD — exponential or power-law — and their topologies are changed more dramatically by targeted attacks directed at bottlenecks than by the removal of network hubs.     

Cascade defense via navigation in scale free networks

In this paper, we investigate cascade defense and control in scale free networks via navigation strategy. It is found that with an appropriate parameter a, which is tunable in controlling the effect of degree in the navigation strategy, one can reduce the risk of cascade break down. By checking the distribution of efficient betweenness centrality (EBC) and the average EBC of vertices with degree k, the validity can be guaranteed. Despite the advantage of cascade defense, the degree based navigation strategy may also lead to lower network efficiency. To avoid this disadvantage, we propose a new navigation strategy. Importantly and interestingly, the new strategy can defend cascade break down effectively even without reducing the network efficiency. Distribution of the EBC and EBC-degree correlation of the new strategy are also investigated to explain the effectiveness in cascade defense.     

Random pseudofractal scale-free networks with small-world effect

A random pseudofractal network (RPN) is generated by a recursive growing rule. The RPN is of the scale-free feature and small-world effect. We obtain the theoretical results of power-law exponent γ=3, clustering coefficient C=3π²-19≈ 0.74, and a proof that the mean distance increases no faster than ln N, where N is the network size. These results agree with the numerical simulation very well. In particular, we explain the property of growth and preferential attachment in RPNs. And the properties of a class of general RPNs are discussed in the end.     

Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems

We have recently introduced [Phys. Rev. E 75, 045102(R) (2007); AIP Conference Proceedings 965, 2007, p. 323] an efficient method for the detection and identification of modules in complex networks, based on the de-synchronization properties (dynamical clustering) of phase oscillators. In this paper we apply the dynamical clustering tecnique to the identification of communities of marine organisms living in the Chesapeake Bay food web. We show that our algorithm is able to perform a very reliable classification of the real communities existing in this ecosystem by using different kinds of dynamical oscillators. We compare also our results with those of other methods for the detection of community structures in complex networks.     

Incompatibility networks as models of scale-free small-world graphs

We make a mapping from Sierpinski fractals to a new class of networks, the incompatibility networks, which are scale-free, small-world, disassortative, and maximal planar graphs. Some relevant characteristics of the networks such as degree distribution, clustering coefficient, average path length, and degree correlations are computed analytically and found to be peculiarly rich. The method of network representation can be applied to some real-life systems making it possible to study the complexity of real networked systems within the framework of complex network theory.     

Heterogeneous network with distance dependent connectivity

We investigate a network model based on an infinite regular square lattice embedded in the Euclidean plane where the node connection probability is given by the geometrical distance of nodes. We show that the degree distribution in the basic model is sharply peaked around its mean value. Since the model was originally developed to mimic the social network of acquaintances, to broaden the degree distribution we propose its generalization. We show that when heterogeneity is introduced to the model, it is possible to obtain fat tails of the degree distribution. Meanwhile, the small-world phenomenon present in the basic model is not affected. To support our claims, both analytical and numerical results are obtained.