Detecting unknown paths on complex networks through random walks

In this article, we investigate the problem of detecting unknown paths on complex networks through random walks. To detect a given path on a network a random walker should pass through the path from its initial node to its terminal node in turn. We calculate probability ?(t) that a random walker detects a given path on a connected network in t steps when it starts out from source node s. We propose an iteration formula for calculating ?(t). Generating function of ?(t) is also derived. Major factors affecting ?(t), such as walking time t, path length l, starting point of the walker, structure of the path, and topological structure of the underlying network are further discussed. Among these factors, two most outstanding ones are walking time t and path length l. On the one hand, ?(t) increases as t increases, and ?(∞)=1, which shows that the longer the walking time, the higher the chance of detecting a given path, and the walker will discover the path sooner or later so long as it keeps wandering on the network. On the other hand, ?(t) drops substantially as path length l increases, which shows that the longer the path, the lower the chance for the walker to find it in a given time. Apart from path length, path structure also has obvious effect on ?(t). Starting point of the walker has only minor influence on ?(t), but topological structure of the underlying network has strong influence on ?(t). Simulations confirm our analytic results.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs

We study network growth from a fixed set of initially isolated nodes placed at random on the surface of a sphere. The growth mechanism we use adds edges to the network depending on strictly local gain and cost criteria. Only nodes that are not too far apart on the sphere may be considered for being joined by an edge. Given two such nodes, the joining occurs only if the gain of doing it surpasses the cost. Our model is based on a multiplicative parameter λ that regulates, in a function of node degrees, the maximum geodesic distance that is allowed between nodes for them to be considered for joining. For n nodes distributed uniformly on the sphere, and for within limits that depend on cost-related parameters, we have found that our growth mechanism gives rise to power-law distributions of node degree that are invariant for constant . We also study connectivity- and distance-related properties of the networks.     

Diffusive capture processes for information search

We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2% of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈T〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ=2.4. We also discuss the possible relationship between 〈T〉 and 〈k²〉, the second moment of the degree distribution of the networks.     

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.     

Step-by-Step Random Walk Network with Power-Law Clique-Degree Distribution

We propose a simple mechanism for generating scale-free networks with degree exponent γ= 3, where the new node is connected to the existing nodes by step-by-step random walk. It is found that the clique-degree distribution based on our model obeys a power-law form, which is in agreement with the recently empirical evidences. In addition, our model displays the small-world effect and the hierarchical structure.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

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.     

First passage time of multiple Brownian particles on networks with applications

In this article, we study some theoretical and technological problems with relation to multiple Brownian particles on networks. We are especially interested in the behavior of the first arriving Brownian particle when all the Brownian particles start out from the source s simultaneously and head to the destination h randomly. We analyze the first passage time (FPT) Y_sh(z) and the mean first passage time (MFPT) 〈Y_sh(z)〉 of multiple Brownian particles on complex networks. Equations of Y_sh(z) and 〈Y_sh(z)〉 are obtained. On a variety of commonly encountered networks, we observe first passage properties of multiple Brownian particles from different aspects. We find that 〈Y_sh(z)〉 drops substantially when particle number z increases at the first stage, and converges to d_sh, the distance between the source and the destination when z→∞. The distribution of FPT Prob{Y_sh(z)=t},t=0,1,2,… is also analyzed in these networks. The distribution curve peaks up towards t=d_sh when z increases. Consequently, if particle number z is set appropriately large, the first arriving Brownian particle will go along the shortest or near shortest paths between the source and the destination with high probability. Simulations confirm our analysis. Based on theoretical studies, we also investigate some practical problems using multiple Brownian particles, such as communication on P2P networks, optimal routing in small world networks, phenomenon of asymmetry in scale-free networks, information spreading in social networks, pervasion of viruses on the Internet, and so on. Our analytic and experimental results on multiple Brownian particles provide useful evidence for further understanding and properly tackling these problems.     

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.     

Kinetic-growth self-avoiding walks on small-world networks

Kinetically-grown self-avoiding walks have been studied on Watts-Strogatz small-world networks, rewired from a two-dimensional square lattice. The maximum length L of this kind of walks is limited in regular lattices by an attrition effect, which gives finite values for its mean value 〈L 〉. For random networks, this mean attrition length 〈L 〉 scales as a power of the network size, and diverges in the thermodynamic limit (system size N ↦∞). For small-world networks, we find a behavior that interpolates between those corresponding to regular lattices and randon networks, for rewiring probability p ranging from 0 to 1. For p < 1, the mean self-intersection and attrition length of kinetically-grown walks are finite. For p = 1, 〈L 〉 grows with system size as N^1/2, diverging in the thermodynamic limit. In this limit and close to p = 1, the mean attrition length diverges as (1-p)^-4. Results of approximate probabilistic calculations agree well with those derived from numerical simulations.     

Comparison of the small-world topology between anatomical and functional connectivity in the human brain

We applied graph analysis to both anatomical and functional connectivity in the human brain. Anatomical connectivity was acquired from diffusion tensor imaging data by probabilistic fiber tracking, and functional connectivity was extracted from resting-state functional magnetic resonance imaging data by calculating correlation maps of time series. For the same subject, anatomical networks seemed to be disassortative, while functional networks were significantly assortative. Anatomical networks showed higher efficiency and smaller diameters than functional networks. It can be proposed that anatomical connectivity, as a major constraint of functional connectivity, has a relatively stable and efficient structure to support functional connectivity that is more changeable and flexible.     

The randomly organized structure of urban ground bus-transport networks in China

In this paper, the evolution dynamical properties of four topological urban ground bus-transport networks (BTNs) in China are empirically researched. As the statistical results of some common used measurements show that there are large fluctuations because of small sample sizes to induce some indistinct conclusions, and there are even incorrect BTN structure pictures as positive degree relation of the adjacent vertices in those BTNs though they are actually uncorrelated at all, i.e., exhibiting “pseudo positive connectivity correction”. Thus in order to uncover the randomly organized architecture of BTNs, new measurements of the average sum of the nearest-neighbors’ degree-degree correlation D_nn(k), and the degree average edges among the nearest-neighbors L(k) are proposed. The obtained results of two new measurements do reflect that the considered BTNs are organized randomly. In this point, those empirical results provide one new framework for a more realistic BTN model, which will capture the underlying evolution principles of a BTN in the geographical topology.     

The web of connections between tourism companies: Structure and dynamics

Tourism destination networks are amongst the most complex dynamical systems, involving a myriad of human-made and natural resources. In this work we report a complex network-based systematic analysis of the Elba (Italy) tourism destination network, including the characterization of its structure in terms of several traditional measurements, the investigation of its modularity, as well as its comprehensive study in terms of the recently reported superedges approach. In particular, structural (the number of paths of distinct lengths between pairs of nodes, as well as the number of reachable companies) and dynamical features (transition probabilities and the inward/outward activations and accessibilities) are measured and analyzed, leading to a series of important findings related to the interactions between tourism companies. Among the several reported results, it is shown that the type and size of the companies influence strongly their respective activations and accessibilities, while their geographical position does not seem to matter. It is also shown that the Elba tourism network is largely fragmented and heterogeneous, so that it could benefit from increased integration.     

Walks on Weighted Networks

We investigate the dynamics of random walks on weighted networks. Assuming that the edge weight and the node strength are used as local information by a random walker. Two kinds of walks, weight-dependent walk and strength-dependent walk, are studied. Exact expressions for stationary distribution and average return time are derived and confirmed by computer simulations. The distribution of average return time and the mean-square displacement are calculated for two walks on the Barrat-Barthelemy-Vespignani （BBV） networks. It is found that a weight-dependent walker can arrive at a new territory more easily than a strength-dependent one.     

Influence of different initial distributions on robust cooperation in scale-free networks: A comparative study

We study the evolutionary Prisoner's dilemma game on scale-free networks, focusing on the influence of different initial distributions for cooperators and defectors on the evolution of cooperation. To address this issue, we consider three types of initial distributions for defectors: uniform distribution at random, occupying the most connected nodes, and occupying the lowest-degree nodes, respectively. It is shown that initial configurations for defectors can crucially influence the cooperation level and the evolution speed of cooperation. Interestingly, the situation where defectors initially occupy the lowest-degree vertices can exhibit the most robust cooperation, compared with two other distributions. That is, the cooperation level is least affected by the initial percentage of defectors. Moreover, in this situation, the whole system evolves fastest to the prevalent cooperation. Besides, we obtain the critical values of initial frequency of defectors above which the extinction of cooperators occurs for the respective initial distributions. Our results might be helpful in explaining the maintenance of high cooperation in scale-free networks.     

English and Chinese languages as weighted complex networks

In this paper, we analyze statistical properties of English and Chinese written human language within the framework of weighted complex networks. The two language networks are based on an English novel and a Chinese biography, respectively, and both of the networks are constructed in the same way. By comparing the intensity and density of connections between the two networks, we find that high weight connections in Chinese language networks prevail more than those in English language networks. Furthermore, some of the topological and weighted quantities are compared. The results display some differences in the structural organizations between the two language networks. These observations indicate that the two languages may have different linguistic mechanisms and different combinatorial natures.     

Effect of edge removal on topological and functional robustness of complex networks

We study the robustness of several network models subject to edge removal. The robustness is measured by the statistics of network breakdowns, where a breakdown is defined as the destroying of the total connectedness of a network, rather than the disappearance of the giant component. We introduce a simple traffic dynamics as the function of a network topology, and the total connectedness can be destroyed in the sense of either the topology or the function. The overall effect of the topological breakdown and the functional breakdown, as well as the relative importance of the topological robustness and the functional robustness, are studied under two edge removal strategies.     

Estimating the clustering coefficient in scale-free networks on lattices with local spatial correlation structure

When we study the architecture of networks of spatially extended systems the nodes in the network are subject to local correlation structures. In this case, we show that for scale-free networks the traditional way to estimate the clustering coefficient may not be meaningful. Here we explain why and propose an approach that corrects this problem.