Self-avoiding walks on scale-free networks

Universal scaling in real dimension

The concept of universality has shaped our understanding of many-body physics, but is mostly limited to homogenous systems. Here, we present a study of universality on a non-homogeneous graph, the long-range diluted graph (LRDG). Its scaling theory is controlled by a single parameter, the spectral dimension ds, which plays the role of the relevant parameter on complex geometries. The graph under consideration allows us to tune the value of the spectral dimension continuously also to noninteger values and to find the universal exponents as continuous functions of the dimension. By means of extensive numerical simulations, we probe the scaling exponents of a simple instance of O ( N ) symmetric models on the LRDG showing quantitative agreement with the theoretical prediction of universal scaling in real dimensions.

Self-avoiding walks and connective constants in clustered scale-free networks

Various types of walks on complex networks have been used in recent years to model search and navigation in several kinds of systems, with particular emphasis on random walks. This gives valuable information on network properties, but self-avoiding walks (SAWs) may be more suitable than unrestricted random walks to study long-distance characteristics of complex systems. Here we study SAWs in clustered scale-free networks, characterized by a degree distribution of the form P(k)∼k^{-γ} for large k. Clustering is introduced in these networks by inserting three-node loops (triangles). The long-distance behavior of SAWs gives us information on asymptotic characteristics of such networks. The number of self-avoiding walks, a_{n}, has been obtained by direct enumeration, allowing us to determine the connective constant μ of these networks as the large-n limit of the ratio a_{n}/a_{n-1}. An analytical approach is presented to account for the results derived from walk enumeration, and both methods give results agreeing with each other. In general, the average number of SAWs a_{n} is larger for clustered networks than for unclustered ones with the same degree distribution. The asymptotic limit of the connective constant for large system size N depends on the exponent γ of the degree distribution: For γ>3, μ converges to a finite value as N→∞; for γ=3, the size-dependent μ_{N} diverges as lnN, and for γ<3 we have μ_{N}∼N^{(3-γ)/2}.

Biological network border detection

Complex networks have been widely used to model biological systems. The concept of accessibility has been proposed recently as a means to organize the nodes of complex networks as belonging to its border or center. Such an approach paves the way to investigating how the functional and structural properties of nodes vary with their respective position in the networks. In this work, we approach such a problem in a biological context applying border detection to Protein-Protein Interaction networks from four organisms of the Mycoplasma genus. We found evidence that the borderness of proteins bears a relation with their spatial organization and molecular function specificity.

Network exploration using true self-avoiding walks

We study the mean first passage time (MFPT) of true self-avoiding walks (TSAWs) on various networks as a measure of searching efficiency. From the numerical analysis, we find that the MFPT of TSAWs, τ^{TSAW}, approaches the theoretical minimum τ^{th}/N=1/2 on synthetic networks whose degree-degree correlations are positive. On the other hand, for biased random walks (BRWs) we find that the MFPT, τ^{BRW}, depends on the parameter α, which controls the degree-dependent bias. More importantly, we find that the minimum MFPT of BRWs, τ_{min}^{BRW}, always satisfies the inequality τ_{min}^{BRW}>τ^{TSAW} on any synthetic network. The inequality is also satisfied on various real networks. From these results, we show that the TSAW is one of the most efficient models, whose efficiency approaches the theoretical limit in network explorations.

Self-avoiding walk on fractal complex networks: Exactly solvable cases

We study the self-avoiding walk on complex fractal networks called the (u,v)-flower by mapping it to the N-vector model in a generating function formalism. First, we analytically calculate the critical exponent ν and the connective constant by a renormalization-group analysis in arbitrary fractal dimensions. We find that the exponent ν is equal to the displacement exponent, which describes the speed of diffusion in terms of the shortest distance. Second, by obtaining an exact solution for the (u,u)-flower, we provide an example which supports the conjecture that the universality class of the self-avoiding walk on graphs is not determined only by the fractal dimension.

Dynamic source routing strategy for two-level flows on scale-free networks

Packets transmitting in real communication networks such as the Internet can be classified as time-sensitive or time-insensitive. To better support the real-time and time-insensitive applications, we propose a two-level flow traffic model in which packets are labeled as level-1 or level-2, and those with level-1 have higher priority to be transmitted. In order to enhance the traffic capacity of the two-level flow traffic model, we expand the global dynamic routing strategy and propose a new dynamic source routing which supports no routing-flaps, high traffic capacity, and diverse traffic flows. As shown in this paper, the proposed dynamic source routing can significantly enhance the traffic capacity and quality of time-sensitive applications compared with the global shortest path routing strategy.

Self avoiding paths routing algorithm in scale-free networks

In this paper, we present a new routing algorithm called "the self avoiding paths routing algorithm." Its application to traffic flow in scale-free networks shows a great improvement over the so called "efficient routing" protocol while at the same time maintaining a relatively low average packet travel time. It has the advantage of minimizing path overlapping throughout the network in a self consistent manner with a relatively small number of iterations by maintaining an equilibrated path distribution especially among the hubs. This results in a significant shifting of the critical packet generation rate over which traffic congestion occurs, thus permitting the network to sustain more information packets in the free flow state. The performance of the algorithm is discussed both on a Barábasi-Albert network and real autonomous system network data.

Global dynamic routing for scale-free networks

Traffic is essential for many dynamic processes on networks. The efficient routing strategy [G. Yan, T. Zhou, B. Hu, Z. Q. Fu, and B. H. Wang, Phys. Rev. E 73, 046108 (2006)] can reach a very high capacity of more than ten times of that with shortest path strategy. In this paper, we propose a global dynamic routing strategy for network systems based on the information of the queue length of nodes. Under this routing strategy, the traffic capacity is further improved. With time delay of updating node queue lengths and the corresponding paths, the system capacity remains constant, while the travel time for packets increases.

Pheromone routing protocol on a scale-free network

This paper proposes a routing strategy for network systems based on the local information of "pheromone." The overall traffic capacity of a network system can be evaluated by the critical packet generating rate R(c). Under this critical generating rate, the total packet number in the system first increases and then decreases to reach a balance state. The system behaves differently from that with a local routing strategy based on the node degree or shortest path routing strategy. Moreover, the pheromone routing strategy performs much better than the local routing strategy, which is demonstrated by a larger value of the critical generating rate. This protocol can be an alternation for superlarge networks, in which the global topology may not be available.

Searching method through biased random walks on complex networks

Information search is closely related to the first-passage property of diffusing particle. The physical properties of diffusing particle is affected by the topological structure of the underlying network. Thus, the interplay between dynamical process and network topology is important to study information search on complex networks. Designing an efficient method has been one of main interests in information search. Both reducing the network traffic and decreasing the searching time have been two essential factors for designing efficient method. Here we propose an efficient method based on biased random walks. Numerical simulations show that the average searching time of the suggested model is more efficient than other well-known models. For a practical interest, we demonstrate how the suggested model can be applied to the peer-to-peer system.

Traffic dynamics based on local routing protocol on a scale-free network

We propose a packet routing strategy with a tunable parameter based on the local structural information of a scale-free network. As free traffic flow on the communication networks is key to their normal and efficient functioning, we focus on the network capacity that can be measured by the critical point of phase transition from free flow to congestion. Simulations show that the maximal capacity corresponds to alpha= -1 in the case of identical nodes' delivering ability. To explain this, we investigate the number of packets of each node depending on its degree in the free flow state and observe the power law behavior. Other dynamic properties including average packets traveling time and traffic load are also studied. Inspiringly, our results indicate that some fundamental relationships exist between the dynamics of synchronization and traffic on the scale-free networks.

Cycles and clustering in bipartite networks

We investigate the clustering coefficient in bipartite networks where cycles of size three are absent and therefore the standard definition of clustering coefficient cannot be used. Instead, we use another coefficient given by the fraction of cycles with size four, showing that both coefficients yield the same clustering properties. The new coefficient is computed for two networks of sexual contacts, one bipartite and another where no distinction between the nodes is made (monopartite). In both cases the clustering coefficient is similar. Furthermore, combining both clustering coefficients we deduce an expression for estimating cycles of larger size, which improves previous estimations and is suitable for either monopartite and multipartite networks, and discuss the applicability of such analytical estimations.