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

Strategic variability in routing: Enhancing network performance in two-layer traffic systems

We develop a model for two-layer traffic flow in which a batch of n_{o} packets are dispatched from the source at regular intervals. This scenario is applicable in various communication and transportation systems, such as TCP congestion control mechanisms and congestion management through traffic lights. We demonstrate that implementing stochastic switching between the shortest-path and greedy approaches in the routing strategy of packet transmission results in a significant reduction in the total transmission weight when n_{o} exceeds a certain threshold. This phenomenon mirrors Parrondo's paradox, in which two games or strategies, individually yielding losses, produce a winning outcome or optimal results when combined. In addition, we observe that the influence of layer 1 on overall dynamics surpasses that of layer 2. Furthermore, we find that the impact of the structural characteristics of layers is more significant for switching probability γ<0.5.

Social Network Forensics Analysis Model Based on Network Representation Learning

The rapid evolution of computer technology and social networks has led to massive data generation through interpersonal communications, necessitating improved methods for information mining and relational analysis in areas such as criminal activity. This paper introduces a Social Network Forensic Analysis model that employs network representation learning to identify and analyze key figures within criminal networks, including leadership structures. The model incorporates traditional web forensics and community algorithms, utilizing concepts such as centrality and similarity measures and integrating the Deepwalk, Line, and Node2vec algorithms to map criminal networks into vector spaces. This maintains node features and structural information that are crucial for the relational analysis. The model refines node relationships through modified random walk sampling, using BFS and DFS, and employs a Continuous Bag-of-Words with Hierarchical Softmax for node vectorization, optimizing the value distribution via the Huffman tree. Hierarchical clustering and distance measures (cosine and Euclidean) were used to identify the key nodes and establish a hierarchy of influence. The findings demonstrate the effectiveness of the model in accurately vectorizing nodes, enhancing inter-node relationship precision, and optimizing clustering, thereby advancing the tools for combating complex criminal networks.

Optimal exploration of random walks with local bias on networks

We propose local-biased random walks on general networks where a Markovian walker is defined by different types of biases in each node to establish transitions to its neighbors depending on their degrees. For this ergodic dynamics, we explore the capacity of the random walker to visit all the nodes characterized by a global mean first passage time. This quantity is calculated using eigenvalues and eigenvectors of the transition matrix that defines the dynamics. In the first part, we illustrate how our framework leads to optimal exploration for small-size graphs through the analysis of all the possible bias configurations. In the second part, we study the most favorable configurations in each node by using simulated annealing. This heuristic algorithm allows obtaining approximate solutions of the optimal bias in different types of networks. The results show how the local bias can optimize the exploration of the network in comparison with the unbiased random walk. The methods implemented in this research are general and open the doors to a broad spectrum of tools applicable to different random walk strategies and dynamical processes on networks.

Biased random walkers and extreme events on the edges of complex networks

Extreme events have low occurrence probabilities and display pronounced deviation from their average behavior, such as earthquakes or power blackouts. Such extreme events occurring on the nodes of a complex network have been extensively studied earlier through the modeling framework of unbiased random walks. They reveal that the occurrence probability for extreme events on nodes of a network has a strong dependence on the nodal properties. Apart from these, a recent work has shown the independence of extreme events on edges from those occurring on nodes. Hence, in this work, we propose a more general formalism to study the properties of extreme events arising from biased random walkers on the edges of a network. This formalism is applied to biases based on a variety network centrality measures including PageRank. It is shown that with biased random walkers as the dynamics on the network, extreme event probabilities depend on the local properties of the edges. The probabilities are highly variable for some edges of the network, while they are approximately a constant for some other edges on the same network. This feature is robust with respect to different biases applied to the random walk algorithm. Further, using the results from this formalism, it is shown that a network is far more robust to extreme events occurring on edges when compared to those occurring on the nodes.

Mean encounter times for multiple random walkers on networks

We introduce a general approach for the study of the collective dynamics of noninteracting random walkers on connected networks. We analyze the movement of R independent (Markovian) walkers, each defined by its own transition matrix. By using the eigenvalues and eigenvectors of the R independent transition matrices, we deduce analytical expressions for the collective stationary distribution and the average number of steps needed by the random walkers to start in a particular configuration and reach specific nodes the first time (mean first-passage times), as well as global times that characterize the global activity. We apply these results to the study of mean first-encounter times for local and nonlocal random walk strategies on different types of networks, with both synchronous and asynchronous motion.

Development of the Theory of Six Value Aggregation Paths in Network Modeling for Spatial Analyses

The dynamic development of spatial structures entails looking for new methods of spatial analysis. The aim of this article is to develop a new theory of space modeling of network structures according to six value aggregation paths: minimum and maximum value difference, minimum and maximum value decrease, and minimum and maximum value increase. The authors show how values presenting (describing) various phenomena or states in urban space can be designed as network structures. The dynamic development of spatial structures entails looking for new methods of spatial analysis. This study analyzes these networks in terms of their nature: random or scale-free. The results show that the paths of minimum and maximum value differences reveal one stage of the aggregation of those values. They generate many small network structures with a random nature. Next four value aggregation paths lead to the emergence of several levels of value aggregation and to the creation of scale-free hierarchical network structures. The models developed according to described theory present the quality of urban areas in various versions. The theory of six paths of value combination includes new measuring tools and methods which can impact quality of life and minimize costs of bad designs or space destructions. They are the proper tools for the sustainable development of urban areas.

Traffic-driven epidemic spreading in multiplex networks

Recent progress on multiplex networks has provided a powerful way to abstract the diverse interaction of a network system with multiple layers. In this paper, we show that a multiplex structure can greatly affect the spread of an epidemic driven by traffic dynamics. One of the interesting findings is that the multiplex structure could suppress the outbreak of an epidemic, which is different from the typical finding of spread dynamics in multiplex networks. In particular, one layer with dense connections can attract more traffic flow and eventually suppress the epidemic outbreak in other layers. Therefore, the epidemic threshold will be larger than the minimal threshold of the layers. With a mean-field approximation, we provide explicit expressions for the epidemic threshold and for the onset of suppressing epidemic spreading in multiplex networks. We also provide the probability of obtaining a multiplex configuration that suppresses the epidemic spreading when the multiplex is composed of: (i) two Erdős-Rényi layers and (ii) two scale-free layers. Therefore, compared to the situation of an isolated network in which a disease may be able to propagate, a larger epidemic threshold can be found in multiplex structures.

Coordinating dynamical routes with statistical physics on space-time networks

Coordination of dynamical routes can alleviate traffic congestion and is essential for the coming era of autonomous self-driving cars. However, dynamical route coordination is difficult and many existing routing protocols are either static or without intervehicle coordination. In this paper, we first apply the cavity approach in statistical physics to derive the theoretical behavior and an optimization algorithm for dynamical route coordination, but they become computationally intractable as the number of time segments increases. We therefore map static spatial networks to space-time networks to derive a computational feasible message-passing algorithm compatible with arbitrary system parameters; it agrees well with the analytical and algorithmic results of the conventional cavity approach and outperforms multistart greedy search in saving total travel time by as much as 15% in simulations. The study sheds light on the design of dynamical route coordination protocols and the solution to other dynamical problems via static analytical approaches on space-time networks.

Multiple random walks on complex networks: A harmonic law predicts search time

We investigate multiple random walks traversing independently and concurrently on complex networks and introduce the concept of mean first parallel passage time (MFPPT) to quantify their search efficiency. The mean first parallel passage time represents the expected time required to find a given target by one or some of the multiple walkers. We develop a general theory that allows us to calculate the MFPPT analytically. Interestingly, we find that the global MFPPT follows a harmonic law with respect to the global mean first passage times of the associated walkers. Remarkably, when the properties of multiple walkers are identical, the global MFPPT decays in a power law manner with an exponent of unity, irrespective of network structure. These findings are confirmed by numerical and theoretical results on various synthetic and real networks. The harmonic law reveals a universal principle governing multiple random walks on networks that uncovers the contribution and role of the combined walkers in a target search. Our paradigm is also applicable to a broad range of random search processes.

Efficient path routing strategy for flows with multiple priorities on scale-free networks

In real networks, traffic flows are different in amount as well as their priorities. However, the latter priority has rarely been examined in routing strategy studies. In this paper, a novel routing algorithm, which is based on the efficient path routing strategy (EP), is proposed to overcome network congestion problem caused by large amount of traffic flows with different priorities. In this scheme, traffic flows with different priorities are transmitted through different routing paths, which are based on EP with different parameters. Simulation results show that the traffic capacity for flows with different priorities can be enhanced by 12% with this method, compared with EP. In addition, the new method contributes to more balanced network traffic load distribution and reduces average transmission jump and delay of packets.

Traffic congestion and the lifetime of networks with moving nodes

For many power-limited networks, such as wireless sensor networks and mobile ad hoc networks, maximizing the network lifetime is the first concern in the related designing and maintaining activities. We study the network lifetime from the perspective of network science. In our model, nodes are initially assigned a fixed amount of energy moving in a square area and consume the energy when delivering packets. We obtain four different traffic regimes: no, slow, fast, and absolute congestion regimes, which are basically dependent on the packet generation rate. We derive the network lifetime by considering the specific regime of the traffic flow. We find that traffic congestion inversely affects network lifetime in the sense that high traffic congestion results in short network lifetime. We also discuss the impacts of factors such as communication radius, node moving speed, routing strategy, etc., on network lifetime and traffic congestion.

Transportation dynamics on coupled networks with limited bandwidth

The communication networks in real world often couple with each other to save costs, which results in any network does not have a stand-alone function and efficiency. To investigate this, in this paper we propose a transportation model on two coupled networks with bandwidth sharing. We find that the free-flow state and the congestion state can coexist in the two coupled networks, and the free-flow path and congestion path can coexist in each network. Considering three bandwidth-sharing mechanisms, random, assortative and disassortative couplings, we also find that the transportation capacity of the network only depends on the coupling mechanism, and the fraction of coupled links only affects the performance of the system in the congestion state, such as the traveling time. In addition, with assortative coupling, the transportation capacity of the system will decrease significantly. However, the disassortative coupling has little influence on the transportation capacity of the system, which provides a good strategy to save bandwidth. Furthermore, a theoretical method is developed to obtain the bandwidth usage of each link, based on which we can obtain the congestion transition point exactly.

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.

Advanced Algorithms for Local Routing Strategy on Complex Networks

Despite the significant improvement on network performance provided by global routing strategies, their applications are still limited to small-scale networks, due to the need for acquiring global information of the network which grows and changes rapidly with time. Local routing strategies, however, need much less local information, though their transmission efficiency and network capacity are much lower than that of global routing strategies. In view of this, three algorithms are proposed and a thorough investigation is conducted in this paper. These algorithms include a node duplication avoidance algorithm, a next-nearest-neighbor algorithm and a restrictive queue length algorithm. After applying them to typical local routing strategies, the critical generation rate of information packets R_c increases by over ten-fold and the average transmission time 〈T〉 decreases by 70–90 percent, both of which are key physical quantities to assess the efficiency of routing strategies on complex networks. More importantly, in comparison with global routing strategies, the improved local routing strategies can yield better network performance under certain circumstances. This is a revolutionary leap for communication networks, because local routing strategy enjoys great superiority over global routing strategy not only in terms of the reduction of computational expense, but also in terms of the flexibility of implementation, especially for large-scale networks.

Physics of transportation: Towards optimal capacity using the multilayer network framework

Because of the critical role of transportation in modern times, one of the most successful application areas of statistical physics of complex networks is the study of traffic dynamics. However, the vast majority of works treat transportation networks as an isolated system, which is inconsistent with the fact that many complex networks are interrelated in a nontrivial way. To mimic a realistic scenario, we use the framework of multilayer networks to construct a two-layered traffic model, whereby the upper layer provides higher transport speed than the lower layer. Moreover, passengers are guided to travel along the path of minimal travelling time and with the additional cost they can transfer from one layer to another to avoid congestion and/or reach the final destination faster. By means of numerical simulations, we show that a degree distribution-based strategy, although facilitating the cooperation between both layers, can be further improved by enhancing the critical generating rate of passengers using a particle swarm optimisation (PSO) algorithm. If initialised with the prior knowledge from the degree distribution-based strategy, the PSO algorithm converges considerably faster. Our work exemplifies how statistical physics of complex networks can positively affect daily life.

Enhancing speed of pinning synchronizability: low-degree nodes with high feedback gains

Controlling complex networks is of paramount importance in science and engineering. Despite recent efforts to improve controllability and synchronous strength, little attention has been paid to the speed of pinning synchronizability (rate of convergence in pinning control) and the corresponding pinning node selection. To address this issue, we propose a hypothesis to restrict the control cost, then build a linear matrix inequality related to the speed of pinning controllability. By solving the inequality, we obtain both the speed of pinning controllability and optimal control strength (feedback gains in pinning control) for all nodes. Interestingly, some low-degree nodes are able to achieve large feedback gains, which suggests that they have high influence on controlling system. In addition, when choosing nodes with high feedback gains as pinning nodes, the controlling speed of real systems is remarkably enhanced compared to that of traditional large-degree and large-betweenness selections. Thus, the proposed approach provides a novel way to investigate the speed of pinning controllability and can evoke other effective heuristic pinning node selections for large-scale systems.

Traffic-driven epidemic spreading in correlated networks

In spite of the extensive previous efforts on traffic dynamics and epidemic spreading in complex networks, the problem of traffic-driven epidemic spreading on correlated networks has not been addressed. Interestingly, we find that the epidemic threshold, a fundamental quantity underlying the spreading dynamics, exhibits a nonmonotonic behavior in that it can be minimized for some critical value of the assortativity coefficient, a parameter characterizing the network correlation. To understand this phenomenon, we use the degree-based mean-field theory to calculate the traffic-driven epidemic threshold for correlated networks. The theory predicts that the threshold is inversely proportional to the packet-generation rate and the largest eigenvalue of the betweenness matrix. We obtain consistency between theory and numerics. Our results may provide insights into the important problem of controlling and/or harnessing real-world epidemic spreading dynamics driven by traffic flows.

Unveiling robustness and heterogeneity through percolation triggered by random-link breakdown

It has been commonly recognized that heterogeneously connected networks are robust against random decays but vulnerable to malicious attacks. However, little is known about measures of heterogeneity geared towards robustness of complex networks. Here, we propose two types of percolation on general networks triggered by random-link errors, where occupied links support the nodes to be alive. Rich resilience behaviors are observed in terms of the percolation threshold and the (integrated) fraction of giant cluster. The discrepancy unraveled between the two models allows us to dynamically define compact measures that have acute discrimination in gauging network heterogeneity. The results provide a connection between network performance, structure, and dynamics.

Optimal transport on weighted networks for different node delivery capability schemes

Many real networks can be best described by weighted networks with a diversity of interactions between nodes measured by the weights of the edges. It is of great importance to improve the overall capacity of these real-world networks. In this paper, the traffic capacity of weighted network is investigated based on three different node delivery capability schemes: the delivery capacity of each node is constant in the first scheme while in the second and third schemes it is proportional to its node degree and node strength. It is shown by simulations that the network transfer capacity depends strongly on the tunable parameter. And different tunable parameter is suitable for different node delivery capability.

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.

Random walk with priorities in communicationlike networks

We study a model for a random walk of two classes of particles (A and B). Where both species are present in the same site, the motion of A's takes precedence over that of B's. The model was originally proposed and analyzed in Maragakis et al. [Phys. Rev. E 77, 020103(R) (2008)]; here we provide additional results. We solve analytically the diffusion coefficients of the two species in lattices for a number of protocols. In networks, we find that the probability of a B particle to be free decreases exponentially with the node degree. In scale-free networks, this leads to localization of the B's at the hubs and arrest of their motion. To remedy this, we investigate several strategies to avoid trapping of the B's, including moving an A instead of the hindered B, allowing a trapped B to hop with a small probability, biased walk toward non-hub nodes, and limiting the capacity of nodes. We obtain analytic results for lattices and networks, and we discuss the advantages and shortcomings of the possible strategies.

Anomalous biased diffusion in networks

We study diffusion with a bias toward a target node in networks. This problem is relevant to efficient routing strategies in emerging communication networks like optical networks. Bias is represented by a probability p of the packet or particle to travel at every hop toward a site that is along the shortest path to the target node. We investigate the scaling of the mean first passage time (MFPT) with the size of the network. We find by using theoretical analysis and computer simulations that for random regular (RR) and Erdős-Rényi networks, there exists a threshold probability, p(th), such that for p<p(th) the MFPT scales anomalously as N(α), where N is the number of nodes, and α depends on p. For p>p(th), the MFPT scales logarithmically with N. The threshold value p(th) of the bias parameter for which the regime transition occurs is found to depend only on the mean degree of the nodes. An exact solution for every value of p is given for the scaling of the MFPT in RR networks. The regime transition is also observed for the second moment of the probability distribution function, the standard deviation. For the case of scale-free (SF) networks, we present analytical bounds and simulations results showing that the MFPT scales at most as lnN to a positive power for any finite bias, which means that in SF networks even a very small bias is considerably more efficient in comparison to unbiased walk.

Noise enhances information transfer in hierarchical networks

We study the influence of noise on information transmission in the form of packages shipped between nodes of hierarchical networks. Numerical simulations are performed for artificial tree networks, scale-free Ravasz-Barabási networks as well for a real network formed by email addresses of former Enron employees. Two types of noise are considered. One is related to packet dynamics and is responsible for a random part of packets paths. The second one originates from random changes in initial network topology. We find that the information transfer can be enhanced by the noise. The system possesses optimal performance when both kinds of noise are tuned to specific values, this corresponds to the Stochastic Resonance phenomenon. There is a non-trivial synergy present for both noisy components. We found also that hierarchical networks built of nodes of various degrees are more efficient in information transfer than trees with a fixed branching factor.

Universality of flux-fluctuation law in complex dynamical systems

Recent work has revealed a law governing flux fluctuation and the average flux in complex dynamical systems. We establish the universality of this flux-fluctuation law through the following steps: (i) We derive the law in a more general setting, showing that it depends on a single parameter characterizing the external driving; (ii) we conduct extensive numerical computations using distinct external driving, different network topologies, and multiple traffic routing strategies; and (iii) we analyze data from an actual vehicle traffic system in a major city in China to lend more credence to the universality of the flux-fluctuation law. Additional factors considered include flux fluctuation on links, window size effect, and hidden topological structures such as nodal degree correlation. Besides its fundamental importance in complex systems, the flux-fluctuation law can be used to infer certain intrinsic property of the system for potential applications such as control of complex systems for improved performance.

Traffic-driven epidemic outbreak on complex networks: how long does it take?

Recent studies have suggested the necessity to incorporate traffic dynamics into the process of epidemic spreading on complex networks, as the former provides support for the latter in many real-world situations. While there are results on the asymptotic scope of the spreading dynamics, the issue of how fast an epidemic outbreak can occur remains outstanding. We observe numerically that the density of the infected nodes exhibits an exponential increase with time initially, rendering definable a characteristic time for the outbreak. We then derive a formula for scale-free networks, which relates this time to parameters characterizing the traffic dynamics and the network structure such as packet-generation rate and betweenness distribution. The validity of the formula is tested numerically. Our study indicates that increasing the average degree and/or inducing traffic congestion can slow down the spreading process significantly.

Competition for shortest paths on sparse graphs

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised.

Extreme events and event size fluctuations in biased random walks on networks

Random walk on discrete lattice models is important to understand various types of transport processes. The extreme events, defined as exceedences of the flux of walkers above a prescribed threshold, have been studied recently in the context of complex networks. This was motivated by the occurrence of rare events such as traffic jams, floods, and power blackouts which take place on networks. In this work, we study extreme events in a generalized random walk model in which the walk is preferentially biased by the network topology. The walkers preferentially choose to hop toward the hubs or small degree nodes. In this setting, we show that extremely large fluctuations in event sizes are possible on small degree nodes when the walkers are biased toward the hubs. In particular, we obtain the distribution of event sizes on the network. Further, the probability for the occurrence of extreme events on any node in the network depends on its "generalized strength," a measure of the ability of a node to attract walkers. The generalized strength is a function of the degree of the node and that of its nearest neighbors. We obtain analytical and simulation results for the probability of occurrence of extreme events on the nodes of a network using a generalized random walk model. The result reveals that the nodes with a larger value of generalized strength, on average, display lower probability for the occurrence of extreme events compared to the nodes with lower values of generalized strength.

Reciprocal interactions out of congestion-free adaptive networks

In this paper we study the jamming transition in complex adaptive networks. We introduce an adaptation mechanism that modifies the weight of the communication channels in order to delay the congestion onset. Adaptivity takes place locally as it is driven by each node of the network. Surprisingly, regardless of the structural properties of the backbone topology, e.g., its degree distribution, the adaptive network can reach optimal functioning provided it allows a reciprocal distribution of the weights. Under this condition, the optimal functioning is achieved through an extensive network reshaping ending up in a highly reciprocal weighted network whose critical onset of congestion is delayed up to its maximum possible value. We also show that, for a given network, the reciprocal weighting obtained from adaptation produce optimal static configurations.

Control of epidemic spreading on complex networks by local traffic dynamics

Despite extensive work on traffic dynamics and epidemic spreading on complex networks, the interplay between these two types of dynamical processes has not received adequate attention. We study the effect of local-routing-based traffic dynamics on epidemic spreading. For the case of unbounded node-delivery capacity, where the traffic is free of congestion, we obtain analytic and numerical results indicating that the epidemic threshold can be maximized by an optimal routing protocol. This means that epidemic spreading can be effectively controlled by local traffic dynamics. For the case of bounded delivery capacity, numerical results and qualitative arguments suggest that traffic congestion can suppress epidemic spreading. Our results provide quantitative insight into the nontrivial role of traffic dynamics associated with a local-routing scheme in the epidemic spreading.

Efficient routing strategies in scale-free networks with limited bandwidth

We study the traffic dynamics in complex networks where each link is assigned a limited and identical bandwidth. Although the first-in-first-out (FIFO) queuing rule is widely applied in the routing protocol of information packets, here we argue that if we drop this rule, the overall throughput of the network can be remarkably enhanced. We propose some efficient routing strategies that do not strictly obey the FIFO rule. Compared to the routine shortest-path strategy, throughput for both Barabási-Albert (BA) networks and the Internet can be improved by a factor of more than five. We calculate the theoretical limitation of the throughput. In BA networks, our proposed strategy can achieve 88% of the theoretical optimum, yet for the Internet, it is about 12%, implying that we still have a huge space to further improve the routing strategy for the Internet. Finally, we discuss possibly promising ways to design more efficient routing strategies for the Internet.

Flow graphs: interweaving dynamics and structure

The behavior of complex systems is determined not only by the topological organization of their interconnections but also by the dynamical processes taking place among their constituents. A faithful modeling of the dynamics is essential because different dynamical processes may be affected very differently by network topology. A full characterization of such systems thus requires a formalization that encompasses both aspects simultaneously, rather than relying only on the topological adjacency matrix. To achieve this, we introduce the concept of flow graphs, namely weighted networks where dynamical flows are embedded into the link weights. Flow graphs provide an integrated representation of the structure and dynamics of the system, which can then be analyzed with standard tools from network theory. Conversely, a structural network feature of our choice can also be used as the basis for the construction of a flow graph that will then encompass a dynamics biased by such a feature. We illustrate the ideas by focusing on the mathematical properties of generic linear processes on complex networks that can be represented as biased random walks and their dual consensus dynamics, and show how our framework improves our understanding of these processes.

Information filtering via preferential diffusion

Recommender systems have shown great potential in addressing the information overload problem, namely helping users in finding interesting and relevant objects within a huge information space. Some physical dynamics, including the heat conduction process and mass or energy diffusion on networks, have recently found applications in personalized recommendation. Most of the previous studies focus overwhelmingly on recommendation accuracy as the only important factor, while overlooking the significance of diversity and novelty that indeed provide the vitality of the system. In this paper, we propose a recommendation algorithm based on the preferential diffusion process on a user-object bipartite network. Numerical analyses on two benchmark data sets, MovieLens and Netflix, indicate that our method outperforms the state-of-the-art methods. Specifically, it can not only provide more accurate recommendations, but also generate more diverse and novel recommendations by accurately recommending unpopular objects.

Transportation dynamics on networks of mobile agents

Most existing works on transportation dynamics focus on networks of a fixed structure, but networks whose nodes are mobile have become widespread, such as cell-phone networks. We introduce a model to explore the basic physics of transportation on mobile networks. Of particular interest is the dependence of the throughput on the speed of agent movement and the communication range. Our computations reveal a hierarchical dependence for the former, while an algebraic power law is found between the throughput and the communication range with the exponent determined by the speed. We develop a physical theory based on the Fokker-Planck equation to explain these phenomena. Our findings provide insights into complex transportation dynamics arising commonly in natural and engineering systems.

Local empathy provides global minimization of congestion in communication networks

We present a mechanism to avoid congestion in complex networks based on a local knowledge of traffic conditions and the ability of routers to self-coordinate their dynamical behavior. In particular, routers make use of local information about traffic conditions to either reject or accept information packets from their neighbors. We show that when nodes are only aware of their own congestion state they self-organize into a hierarchical configuration that delays remarkably the onset of congestion although leading to a sharp first-order-like congestion transition. We also consider the case when nodes are aware of the congestion state of their neighbors. In this case, we show that empathy between nodes is strongly beneficial to the overall performance of the system and it is possible to achieve larger values for the critical load together with a smooth, second-order-like, transition. Finally, we show how local empathy minimize the impact of congestion as much as global minimization. Therefore, here we present an outstanding example of how local dynamical rules can optimize the system's functioning up to the levels reached using global knowledge.

Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network

In this paper, we propose an efficient strategy to enhance traffic capacity via the process of nodes and links increment. We show that by adding shortcut links to the existing networks, packets are avoided flowing through hub nodes. We investigate the performances of our proposed strategy under the shortest path routing strategy and the local routing strategy. Our obtained results show that using the proposed strategy, the traffic capacity can be effectively enhanced under the shortest path routing strategy. Under the local routing strategy, the obtained results show that the proposed strategy is efficient only when packets are more likely to be forwarded to low-degree nodes in their routing paths. Compared with other strategies, the obtained results indicate that our proposed strategy of adding nodes and links is the most effective in enhancing the traffic capacity, i.e., the traffic capacity can be maximally enhanced with the least number of additional nodes and links.

Coverage-maximization in networks under resource constraints

Efficient coverage algorithms are essential for information search or dispersal in all kinds of networks. We define an extended coverage problem which accounts for constrained resources of consumed bandwidth B and time T . Our solution to the network challenge is here studied for regular grids only. Using methods from statistical mechanics, we develop a coverage algorithm with proliferating message packets and temporally modulated proliferation rate. The algorithm performs as efficiently as a single random walker but O(B(d-2)/d) times faster, resulting in significant service speed-up on a regular grid of dimension d . The algorithm is numerically compared to a class of generalized proliferating random walk strategies and on regular grids shown to perform best in terms of the product metric of speed and efficiency.

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.

Investigation of both local and global topological ingredients on transport efficiency in scale-free networks

This paper investigates the combined effect of local and global topological ingredients for routing packets on transport efficiency in scale-free networks with different degree exponents. Four different transport efficiency measurements, namely, the critical packet generation rate, the average number of overall packet loads, the relative variance of packet number on each node, and the relative variance of transport time from source to destination, are investigated in this paper. The combined effects of global and local ingredients on four measurements are presented and analyzed. We also investigate the effect of degree exponent on four measurements. Based on the results we obtained, we propose an improved routing strategy with memory information. Simulation results show that the critical packet generation rate can be efficiently improved by using the improved routing strategy with memory information, especially when packets are showing strong inclination of being forwarded to low-degree or high-degree nodes in scale-free networks with small degree exponents.

Abrupt transition to complete congestion on complex networks and control

Previous works on traffic-flow dynamics on complex networks have mostly focused on continuous phase transition from a free-flow state to a locally congested state as a parameter, such as the packet-generating rate, is increased through a critical value. Above the transition point congestion occurs on a small subset of nodes. Utilizing a conventional traffic-flow model based on the packet birth-death process and more importantly, taking into account the fact that in realistic networks nodes have only finite buffers, we find an abrupt transition from free flow to complete congestion. Slightly below the transition point, the network can support the maximum amount of traffic for some optimal value of the routing parameter. We develop a mean-field theory to explain the surprising transition phenomenon and provide numerical support. Furthermore, we propose a control strategy based on the idea of random packet dropping to prevent/break complete congestion. Our finding provides insights into realistic communication networks where complete congestion can occur directly from a free-flow state without any apparent precursor, and our control strategy can be effective to restore traffic flow once complete congestion has occurred.

Self-adjusting routing schemes for time-varying traffic in scale-free networks

We consider the effects of time-varying packet generation rates in the performance of communication networks. The time variations could be a result of the patterns in human activities. As a model, we study the effects of a degree-dependent packet generation rate that includes a sinusoidal term. Applying a modified traffic awareness protocol (TAP) previously proposed for static packet generation rates to the present situation leads to an altered value of the optimization parameter, when compared to that obtained in the static case. To enhance the performance and to cope with the time-varying effects better, we propose a class of self-adjusting traffic awareness protocols that makes use of instantaneous traffic information beyond that included in the modified TAP. Two special cases that make use of global and local information, respectively, are studied. Comparing results of our proposal schemes with the modified TAP, it is shown that the present self-adjusting schemes perform more effectively.

Biased random walks in complex networks: the role of local navigation rules

We study the biased random-walk process in random uncorrelated networks with arbitrary degree distributions. In our model, the bias is defined by the preferential transition probability, which, in recent years, has been commonly used to study the efficiency of different routing protocols in communication networks. We derive exact expressions for the stationary occupation probability and for the mean transit time between two nodes. The effect of the cyclic search on transit times is also explored. Results presented in this paper provide the basis for a theoretical treatment of transport-related problems in complex networks, including quantitative estimation of the critical value of the packet generation rate.

Flow-pattern identification and nonlinear dynamics of gas-liquid two-phase flow in complex networks

The identification of flow pattern is a basic and important issue in multiphase systems. Because of the complexity of phase interaction in gas-liquid two-phase flow, it is difficult to discern its flow pattern objectively. In this paper, we make a systematic study on the vertical upward gas-liquid two-phase flow using complex network. Three unique network construction methods are proposed to build three types of networks, i.e., flow pattern complex network (FPCN), fluid dynamic complex network (FDCN), and fluid structure complex network (FSCN). Through detecting the community structure of FPCN by the community-detection algorithm based on K -mean clustering, useful and interesting results are found which can be used for identifying five vertical upward gas-liquid two-phase flow patterns. To investigate the dynamic characteristics of gas-liquid two-phase flow, we construct 50 FDCNs under different flow conditions, and find that the power-law exponent and the network information entropy, which are sensitive to the flow pattern transition, can both characterize the nonlinear dynamics of gas-liquid two-phase flow. Furthermore, we construct FSCN and demonstrate how network statistic can be used to reveal the fluid structure of gas-liquid two-phase flow. In this paper, from a different perspective, we not only introduce complex network theory to the study of gas-liquid two-phase flow but also indicate that complex network may be a powerful tool for exploring nonlinear time series in practice.

Queue-length synchronization in communication networks

We study the synchronization in the context of network traffic on a 2-d communication network with local clustering and geographic separations. The network consists of nodes and randomly distributed hubs where the top five hubs ranked according to their coefficient of betweenness centrality (CBC) are connected by random assortative and gradient mechanisms. For multiple message traffic, messages can trap at the high CBC hubs, and congestion can build up on the network with long queues at the congested hubs. The queue lengths are seen to synchronize in the congested phase. Both complete and phase synchronization are seen, between pairs of hubs. In the decongested phase, the pairs start clearing and synchronization is lost. A cascading master-slave relation is seen between the hubs, with the slower hubs (which are slow to decongest) driving the faster ones. These are usually the hubs of high CBC. Similar results are seen for traffic of constant density. Total synchronization between the hubs of high CBC is also seen in the congested regime. Similar behavior is seen for traffic on a network constructed using the Waxman random topology generator. We also demonstrate the existence of phase synchronization in real internet traffic data.

Optimal weighting scheme for suppressing cascades and traffic congestion in complex networks

This paper is motivated by the following two related problems in complex networks: (i) control of cascading failures and (ii) mitigation of traffic congestion. Both problems are of significant recent interest as they address, respectively, the security of and efficient information transmission on complex networks. Taking into account typical features of load distribution and weights in real-world networks, we have discovered an optimal solution to both problems. In particular, we shall provide numerical evidence and theoretical analysis that, by choosing a proper weighting parameter, a maximum level of robustness against cascades and traffic congestion can be achieved, which practically rids the network of occurrences of the catastrophic dynamics.

Optimal contact process on complex networks

Contact processes on complex networks are a recent subject of study in nonequilibrium statistical physics and they are also important to applied fields such as epidemiology and computer and communication networks. A basic issue concerns finding an optimal strategy for spreading. We provide a universal strategy that, when a basic quantity in the contact process dynamics, the contact probability determined by a generic function of its degree W(k) , is chosen to be inversely proportional to the node degree, i.e., W(k) approximately k;{-1} , spreading can be maximized. Computation results on both model and real-world networks verify our theoretical prediction. Our result suggests the determining role played by small-degree nodes in optimizing spreading, in contrast to the intuition that hub nodes are important for spreading dynamics on complex networks.

Gradient mechanism in a communication network

We study the efficiency of the gradient mechanism of message transfer in a two-dimensional communication network of regular nodes and randomly distributed hubs. Each hub on the network is assigned some randomly chosen capacity and hubs with lower capacities are connected to the hubs with maximum capacity. The average travel times of single messages traveling on the lattice decrease rapidly as the number of hubs increase. The functional dependence of the average travel times on the hub density shows q-exponential behavior with a power-law tail. We also study the relaxation behavior of the network when a large number of messages are created simultaneously at random locations and travel on the network toward their designated destinations. For this situation, in the absence of the gradient mechanism, the network can show congestion effects due to the formation of transport traps. We show that if hubs of high betweenness centrality are connected by the gradient mechanism, efficient decongestion can be achieved. The gradient mechanism is less prone to the formation of traps than other decongestion schemes. We also study the spatial configurations of transport traps and propose minimal strategies for their elimination.

Method to enhance traffic capacity for scale-free networks

In this paper, a method is proposed to enhance the traffic handling capacity of scale-free networks by closing or cutting some links between some large-degree nodes, for both local routing strategy and global shortest-path routing strategy. The traffic capacity of networks is found to be considerably improved after applying the link-closing strategy, especially in the case of global routing. Due to the strongly improved network capacity, easy realization on networks, and low cost, the strategy may be useful for modern communication networks.

Nature-inspired interconnects for self-assembled large-scale network-on-chip designs

Future nanoscale electronics built up from an Avogadro number of components need efficient, highly scalable, and robust means of communication in order to be competitive with traditional silicon approaches. In recent years, the networks-on-chip (NoC) paradigm emerged as a promising solution to interconnect challenges in silicon-based electronics. Current NoC architectures are either highly regular or fully customized, both of which represent implausible assumptions for emerging bottom-up self-assembled molecular electronics that are generally assumed to have a high degree of irregularity and imperfection. Here, we pragmatically and experimentally investigate important design tradeoffs and properties of an irregular, abstract, yet physically plausible three-dimensional (3D) small-world interconnect fabric that is inspired by modern network-on-chip paradigms. We vary the framework's key parameters, such as the connectivity, number of switch nodes, and distribution of long- versus short-range connections, and measure the network's relevant communication characteristics. We further explore the robustness against link failures and the ability and efficiency to solve a simple toy problem, the synchronization task. The results confirm that (1) computation in irregular assemblies is a promising and disruptive computing paradigm for self-assembled nanoscale electronics and (2) that 3D small-world interconnect fabrics with a power-law decaying distribution of shortcut lengths are physically plausible and have major advantages over local two-dimensional and 3D regular topologies.

Phase transition and hysteresis in scale-free network traffic

We model information traffic on scale-free networks by introducing the node queue length L proportional to the node degree and its delivering ability C proportional to L . The simulation gives the overall capacity of the traffic system, which is quantified by a phase transition from free flow to congestion. It is found that the maximal capacity of the system results from the case of the local routing coefficient phi slightly larger than zero, and we provide an analysis for the optimal value of phi. In addition, we report for the first time the fundamental diagram of flow against density, in which hysteresis is found, and thus we can classify the traffic flow with four states: free flow, saturated flow, bistable, and jammed.