Traffic of particles in complex networks

First-passage time for many-particle diffusion in space-time random environments

The first-passage time for a single diffusing particle has been studied extensively, but the first-passage time of a system of many diffusing particles, as is often the case in physical systems, has received little attention until recently. We consider two models for many-particle diffusion-one treats each particle as independent simple random walkers while the other treats them as coupled to a common space-time random forcing field that biases particles nearby in space and time in similar ways. The first-passage time of a single diffusing particle under both models shows the same statistics and scaling behavior. However, for many-particle diffusions, the first-passage time among all particles (the extreme first-passage time) is very different between the two models, effected in the latter case by the randomness of the common forcing field. We develop an asymptotic (in the number of particles and location where first passage is being probed) theoretical framework to separate the impact of the random environment with that of the sampling trajectories within it. We identify a power law describing the impact of the environment on the variance of the extreme first-passage time. Through numerical simulations, we verify that the predictions from this asymptotic theory hold even for systems with widely varying numbers of particles, all the way down to 100 particles. This shows that measurements of the extreme first-passage time for many-particle diffusions provide an indirect measurement of the underlying environment in which the diffusion is occurring.

Extended-range percolation in complex networks

Classical percolation theory underlies many processes of information transfer along the links of a network. In these standard situations, the requirement for two nodes to be able to communicate is the presence of at least one uninterrupted path of nodes between them. In a variety of more recent data transmission protocols, such as the communication of noisy data via error-correcting repeaters, both in classical and quantum networks, the requirement of an uninterrupted path is too strict: two nodes may be able to communicate even if all paths between them have interruptions or gaps consisting of nodes that may corrupt the message. In such a case a different approach is needed. We develop the theoretical framework for extended-range percolation in networks, describing the fundamental connectivity properties relevant to such models of information transfer. We obtain exact results, for any range R, for infinite random uncorrelated networks and we provide a message-passing formulation that works well in sparse real-world networks. The interplay of the extended range and heterogeneity leads to novel critical behavior in scale-free networks.

Structure, Function, and Propagation of Information across Living Two, Four, and Eight Node Degree Topologies

In this study, we created four network topologies composed of living cortical neurons and compared resultant structural-functional dynamics including the nature and quality of information transmission. Each living network was composed of living cortical neurons and were created using microstamping of adhesion promoting molecules and each was "designed" with different levels of convergence embedded within each structure. Networks were cultured over a grid of electrodes that permitted detailed measurements of neural activity at each node in the network. Of the topologies we tested, the "Random" networks in which neurons connect based on their own intrinsic properties transmitted information embedded within their spike trains with higher fidelity relative to any other topology we tested. Within our patterned topologies in which we explicitly manipulated structure, the effect of convergence on fidelity was dependent on both topology and time-scale (rate vs. temporal coding). A more detailed examination using tools from network analysis revealed that these changes in fidelity were also associated with a number of other structural properties including a node's degree, degree-degree correlations, path length, and clustering coefficients. Whereas information transmission was apparent among nodes with few connections, the greatest transmission fidelity was achieved among the few nodes possessing the highest number of connections (high degree nodes or putative hubs). These results provide a unique view into the relationship between structure and its affect on transmission fidelity, at least within these small neural populations with defined network topology. They also highlight the potential role of tools such as microstamp printing and microelectrode array recordings to construct and record from arbitrary network topologies to provide a new direction in which to advance the study of structure-function relationships.

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.

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.

Transmission of packets on a hierarchical network: statistics and explosive percolation

We analyze an idealized model for the transmission or flow of particles, or discrete packets of information, in a weight bearing branching hierarchical two dimensional network and its variants. The capacities add hierarchically down the clusters. Each node can accommodate a limited number of packets, depending on its capacity, and the packets hop from node to node, following the links between the nodes. The statistical properties of this system are given by the Maxwell-Boltzmann distribution. We obtain analytical expressions for the mean occupation numbers as functions of capacity, for different network topologies. The analytical results are shown to be in agreement with the numerical simulations. The traffic flow in these models can be represented by the site percolation problem. It is seen that the percolation transitions in the 2D model and in its variant lattices are continuous transitions, whereas the transition is found to be explosive (discontinuous) for the V lattice, the critical case of the 2D lattice. The scaling behavior of the second-order percolation case is studied in detail. We discuss the implications of our analysis.

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.

Topological effects on dynamics in complex pulse-coupled networks of integrate-and-fire type

For a class of integrate-and-fire, pulse-coupled networks with complex topology, we study the dependence of the pulse rate on the underlying architectural connectivity statistics. We derive the distribution of the pulse rate from this dependence and determine when the underlying scale-free architectural connectivity gives rise to a scale-free pulse-rate distribution. We identify the scaling of the pairwise coupling between the dynamical units in this network class that keeps their pulse rates bounded in the infinite-network limit. In the process, we determine the connectivity statistics for a specific scale-free network grown by preferential attachment.

Interarrival times of message propagation on directed networks

One of the challenges in fighting cybercrime is to understand the dynamics of message propagation on botnets, networks of infected computers used to send viruses, unsolicited commercial emails (SPAM) or denial of service attacks. We map this problem to the propagation of multiple random walkers on directed networks and we evaluate the interarrival time distribution between successive walkers arriving at a target. We show that the temporal organization of this process, which models information propagation on unstructured peer to peer networks, has the same features as SPAM reaching a single user. We study the behavior of the message interarrival time distribution on three different network topologies using two different rules for sending messages. In all networks the propagation is not a pure Poisson process. It shows universal features on Poissonian networks and a more complex behavior on scale free networks. Results open the possibility to indirectly learn about the process of sending messages on networks with unknown topologies, by studying interarrival times at any node of the network.

Extreme events on complex networks

A wide spectrum of extreme events ranging from traffic jams to floods take place on networks. Motivated by these, we employ a random walk model for transport and obtain analytical and numerical results for the extreme events on networks. They reveal an unforeseen, and yet a robust, feature: small degree nodes of a network are more likely to encounter extreme events than the hubs. Further, we also study the recurrence time distribution and scaling of the probabilities for extreme events. These results suggest a revision of design principles and can be used as an input for designing the nodes of a network so as to smoothly handle extreme events.

Mixed Bose-Fermi statistics: kinetic equation and navigation through a network

The conventional master equation is generalized to include Bose and Fermi moves. The obtained equation describes the time evolution of a system with mixed Bose-Fermi statistics which are controlled by the fraction of Fermi moves (α) ; the latter plays a role of an exploratory tendency (ET) factor. The theoretical consideration is illustrated with numerical results for navigation through a model scale-free network. Depending on the ET factor and the number of participants involved in the navigation (N(tot)) , a broad variety of the behavior scenarios has been observed. The cases of N(tot)=1 and N(tot)>>1 have been found drastically different. Of particular interest is the case of N(tot)>>1 , when the participants interfere with each other's motion, which is characteristic of many real systems (urban traffic, Internet, epidemic spreading, etc.). It has been found that at α<1 all participants reach a preselected (target) state but an excessive intention to try detour routes (α→1) leads to a critical slowdown in their passage to this state. At the same time, if α=1 (solely Fermi moves, no possibility to return to a previously visited state), only one of the participants attains the target state but it does it much faster than when a single copy navigates through the network (N(tot)=1) , i.e., this one optimizes the way to the target state at the expense of other participants. The procedure used to include Bose and Fermi moves in the master equation offers a framework for derivation of kinetic equations for more complex and general statistics.

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.

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.

Optimal structure of complex networks for minimizing traffic congestion

To design complex networks to minimize traffic congestion, it is necessary to understand how traffic flow depends on network structure. We study data packet flow on complex networks, where the packet delivery capacity of each node is not fixed. The optimal configuration of capacities to minimize traffic congestion is derived and the critical packet generating rate is determined, below which the network is at a free flow state but above which congestion occurs. Our analysis reveals a direct relation between network topology and traffic flow. Optimal network structure, free of traffic congestion, should have two features: uniform distribution of load over all nodes and small network diameter. This finding is confirmed by numerical simulations. Our analysis also makes it possible to theoretically compare the congestion conditions for different types of complex networks. In particular, we find that network with low critical generating rate is more susceptible to congestion. The comparison has been made on the following complex-network topologies: random, scale-free, and regular.

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.