Narrow Results

We propose a novel approach for shortest path routing in wireless mobile networks. The approach makes use of n mobile agents initially launched from n mobile nodes forming the network. The agents move randomly from node to node and update routing information as they go. The approach is presented in this paper with two protocols. Both of them exhibit good performance in terms of the network and computing resource consumptions. The first protocol relies on independent mobile agents and imposes a minimum bandwidth requirement on individual mobile agents. Each agent carries the link state of its creator and this information remains unchanged except when the mobile agent returns to the home node. The second protocol is a refinement of the first protocol, with some form of interaction between the mobile agents. Each agent maintains the routing table of its creator instead of link state. The randomly walking agents spread the update information and compute the shortest paths via exchanging network state information between the routing tables they carry and the routing tables at the nodes they traverse. The correctness of the protocols is proven. Our analysis shows that the agent cooperation improves the system performance when dealing with topology and link cost changes.

In this paper, we present a fully distributed random walk based clustering algorithm intended to work on dynamic networks of arbitrary topologies.

A bounded-size core is built through a random walks based procedure. Its neighboring nodes that do not belong to any cluster are recruited by the core as ordinary nodes. Using cores allow us to formulate constraints on the clustering and fulfill them on any topology.

The correctness and termination of our algorithm are proven. We also prove that when two clusters are adjacent, at least one of them has a complete core (i.e. a core with the maximum size allowed by the parameter).

One of the important advantages of our mobility-adaptive algorithm is that the re-clustering is local: the management of the connections or disconnections of links and reorganization of nodes affect only the clusters in which they are, possibly adjacent clusters, and at worst, the ordinary nodes of the clusters adjacent to the neighboring clusters. This allows us to bound the diameter of the portion of the network that is affected by a topological change.

Magnetic resonance imaging allows acquiring functional and structural connectivity data from which high-density whole-brain networks can be derived to carry out connectome-wide analyses in normal and clinical populations. Graph theory has been widely applied to investigate the modular structure of brain connections by using centrality measures to identify the “hub” of human connectomes, and community detection methods to delineate subnetworks associated with diverse cognitive and sensorimotor functions. These analyses typically rely on a preprocessing step (pruning) to reduce computational complexity and remove the weakest edges that are most likely affected by experimental noise. However, weak links may contain relevant information about brain connectivity, therefore, the identification of the optimal trade-off between retained and discarded edges is a subject of active research. We introduce a pruning algorithm to identify edges that carry the highest information content. The algorithm selects both strong edges (i.e. edges belonging to shortest paths) and weak edges that are topologically relevant in weakly connected subnetworks. The newly developed “strong–weak” pruning (SWP) algorithm was validated on simulated networks that mimic the structure of human brain networks. It was then applied for the analysis of a real dataset of subjects affected by amyotrophic lateral sclerosis (ALS), both at the early (ALS2) and late (ALS3) stage of the disease, and of healthy control subjects. SWP preprocessing allowed identifying statistically significant differences in the path length of networks between patients and healthy subjects. ALS patients showed a decrease of connectivity between frontal cortex to temporal cortex and parietal cortex and between temporal and occipital cortex. Moreover, degree of centrality measures revealed significantly different hub and centrality scores between patient subgroups. These findings suggest a widespread alteration of network topology in ALS associated with disease progression.

We study the cut-off phenomenon for random walks on free unitary quantum groups coming from quantum conjugacy classes of classical reflections. We obtain in particular a quantum analogue of the result of U. Porod concerning certain mixtures of reflections. We also study random walks on quantum reflection groups and more generally on free wreath products of finite groups by quantum permutation groups.

An asexual set of primitive bacteria is simulated with a bit-string Penna model with a Fermi function for survival. A recent hypothesis by Jan, Stauffer, and Moseley on the evolution of sex from asexual cells as a strategy for trying to escape the effects of deleterious mutations is checked. This strategy is found to provide a successful scenario for the evolution of a stable macroscopic sexual population.

Using in silico experiments, we isolate the effects of geometry on the efficiency of passive diffusion transport, P_S, of viral cargos to the nuclear region. We model the cell as an elliptical 2D structure (eccentricity e) containing a circular nucleus with radii R (semi-minor) and r, respectively. The cargos move in isotropic random walk inside the cell. P_S is estimated as the ratio of the number of cargos that reach the nuclear region and of cargos released. We show that P_S decreases with the total distance traveled but increases with r/R. Shifting the nuclear position inside circular cells (e = 0) produce probability distribution functions of total distance traveled that shifts to shorter modes as one side becomes closer to the cell membrane. On the contrary, cargos in more elongated cells (e = 0) have preserved P_S-values even for longer distances of travel inside the cell. Finally, an optimum r/R exists due to a trade-off between increased efficiency of transport to the nucleus and high cytoplasmic area. This work could contribute in elucidating the reason why some viruses induce asymmetry in their host cells.

About 45000 years ago, symbolic and technological complexity of human artefacts increased drastically. Computer simulations of Powell, Shennan and Thomas (2009) explained it through an increase of the population density, facilitating the spread of information about useful innovations. We simplify this demographic model and make it more similar to standard physics models. For this purpose, we assume that bands (extended families) of stone-age humans were distributed randomly on a square lattice such that each lattice site is randomly occupied with probability p and empty with probability 1 - p. Information spreads randomly from an occupied site to one of its occupied neighbors. If we wait long enough, information spreads from one side of the lattice to the opposite site if and only if p is larger than the percolation threshold; this process was called "ant in the labyrinth" by de Gennes 1976. We modify it by giving the diffusing information a finite lifetime, which shifts the threshold upwards.

In this paper, we obtain exact scalings of mean first-passage time (MFPT) of random walks on a family of small-world treelike networks formed by two parameters, which includes three kinds. First, we determine the MFPT for a trapping problem with an immobile trap located at the initial node, which is defined as the average of the first-passage times (FPTs) to the trap node over all possible starting nodes, and it scales linearly with network size N in large networks. We then analytically obtain the partial MFPT (PMFPT) which is the mean of FPTs from the trap node to all other nodes and show that it increases with N as N ln N. Finally we establish the global MFPT (GMFPT), which is the average of FPTs over all pairs of nodes. It also grows with N as N ln N in the large limit of N. For these three kinds of random walks, we all obtain the analytical expressions of the MFPT and they all increase with network parameters. In addition, our method for calculating the MFPT is based on the self-similar structure of the considered networks and avoids the calculations of the Laplacian spectra.

Random walks on complex networks are of great importance to understand various types of phenomena in real world. In this paper, two types of biased random walks on nonassortative weighted networks are studied: edge-weight-based random walks and node-strength-based random walks, both of which are extended from the normal random walk model. Exact expressions for stationary distribution and mean first return time (MFRT) are derived and examined by simulation. The results will be helpful for understanding the influences of weights on the behavior of random walks.

In this paper, we investigate the random walks on metro systems in 28 cities from worldwide via the Laplacian spectrum to realize the trapping process on real systems. The average trapping time is a primary description to response the trapping process. Firstly, we calculate the mean trapping time to each target station and to each entire system, respectively. Moreover, we also compare the average trapping time with the strength (the weighted degree) and average shortest path length for each station, separately. It is noted that the average trapping time has a close inverse relation with the station’s strength but rough positive correlation with the average shortest path length. And we also catch the information that the mean trapping time to each metro system approximately positively correlates with the system’s size. Finally, the trapping process on weighted and unweighted metro systems is compared to each other for better understanding the influence of weights on trapping process on metro networks. Numerical results show that the weights have no significant impact on the trapping performance on metro networks.

From the stock markets of six countries with high GDP, we study the stock indices, S&P 500 (NYSE, USA), SSE Composite (SSE, China), Nikkei (TSE, Japan), DAX (FSE, Germany), FTSE 100 (LSE, Britain) and NIFTY (NSE, India). The daily mean growth of the stock values is exponential. The daily price fluctuations about the mean growth are Gaussian, but with a nonzero asymptotic convergence. The growth of the monthly average of stock values is statistically self-similar to their daily growth. The monthly fluctuations of the price follow a Wiener process, with a decline of the volatility. The mean growth of the daily volume of trade is exponential. These observations are globally applicable and underline regularities across global stock markets.

One dominant aspect of cities is transport and massive passenger mobilization which remains a challenge with the increasing demand on the public as cities grow. In addition, public transport infrastructure suffers from traffic congestion and deterioration, reducing its efficiency. In this paper, we study the capacity of transport in 33 worldwide metro systems under the accumulation of damage. We explore the gradual reduction of functionality in these systems associated with damage that occurs stochastically. The global transport of each network is modeled as the diffusive movement of Markovian random walkers on networks considering the capacity of transport of each link, where these links are susceptible to damage. Monte Carlo simulations of this process in metro networks show the evolution of the functionality of the system under damage considering all the complexity in the transportation structure. This information allows us to compare and classify the effect of damage in metro systems. Our findings provide a general framework for the characterization of the capacity to maintain the transport under failure in different systems described by networks.

The recent stimulating proposal of a "Gauge Theory of Finance" by Ilinsky et al. is connected here with traditional approaches. First, the derivation of the log-normal distribution is shown to be equivalent both in information and mathematical content to the simpler and well-known derivation, dating back from Bachelier and Samuelson. Similarly, the re-derivation of Black–Scholes equation is shown equivalent to the standard one because the limit of no uncertainty is equivalent to the standard risk-free replication argument. Both re-derivations of the log-normality and Black–Scholes result do not provide a test of the theory because it is not uniquely specified in the limits where these results apply. Third, the choice of the exponential form a la Boltzmann, of the weight of a given market configuration, is a key postulate that requires justification. In addition, the "Gauge Theory of Finance" seems to lead to "virtual" arbitrage opportunities for a pure Markov random walk market when there should be none. These remarks are offered in the hope to improve the formulation of the "Gauge Theory of Finance" into a coherent and useful framework.

Using a recently proposed directed random walk test, we systematically investigate the popular random number generator RANLUX developed by Lüscher and implemented by James. We confirm the good quality of this generator with the recommended luxury level. At a smaller luxury level (for instance equal to 1) resonances are observed in the random walk test. We also find that the lagged Fibonacci and Subtract-with-Carry recipes exhibit similar failures in the random walk test. A revised analysis of the corresponding dynamical systems leads to the observation of resonances in the eigenvalues of Jacobi matrix.

We investigate the long-time behavior of the drift velocity of two-dimensional biased diffusion with varying bias B and percentage p of allowed sites. A phase diagram for the drift/no-drift transition depending on B and p is presented.

A method for analyzing clusters which block the random walk of particles in two-dimensional biased diffusion on percolation lattices above the percolation threshold p_c is presented, focusing on the arising problems and explaining the phase transition. The difficulties in a precise trap definition are illustrated. Different trap definitions result in different trap statistics, more or less capable of capturing the trend of the phase diagram.

Many approaches to a semiclassical description of gravity lead to an integer black hole entropy. In four dimensions this implies that the Schwarzschild radius obeys a formula which describes the distance covered by a Brownian random walk. For the higher-dimensional Schwarzschild–Tangherlini black hole, its radius relates similarly to a fractional Brownian walk. We propose a possible microscopic explanation for these random walk structures based on microscopic chains which fill the interior of the black hole.

Superbubbles are shells in the interstellar medium produced by the simultaneous explosions of many supernova remnants. The solutions of the mathematical diffusion and of the Fourier expansion in 1D, 2D and 3D were deduced in order to describe the diffusion of nucleons from such structures. The mean number of visits in the the case of the Levy flights in 1D was computed with a Monte Carlo simulation. The diffusion of cosmic rays has its physical explanation in the relativistic Larmor gyro-radius which is energy dependent. The mathematical solution of the diffusion equation in 1D with variable diffusion coefficient was computed. Variable diffusion coefficient means magnetic field variable with the altitude from the Galactic plane. The analytical solutions allow us to calibrate the code that describes the Monte Carlo diffusion. The maximum energy that can be extracted from the superbubbles is deduced. The concentration of cosmic rays is a function of the distance from the nearest superbubble and the selected energy. The interaction of the cosmic rays on the target material allows us to trace the theoretical map of the diffuse Galactic continuum gamma-rays. The streaming of the cosmic rays from the Gould Belts that contains the sun at its internal was described by a Monte Carlo simulation. Ten new formulas are derived.

Studies in spin dynamics of disordered media and multiple ultra-small angle neutron scattering are considered. The experiments were carried out on unique installations designed in ITEP laboratory of neutron physics: beta-NMR spectrometer and universal neutron diffractometer. The main attention is paid to random walks in disordered systems and ultra-small angle neutron scattering (USANS) on objects with space correlations in positions of scatterers. Synthesis of concentration expansion, semi-phenomenological theory and numerical simulations produced satisfactory description of the nuclear polarization transfer within disordered ⁸Li–⁶Li spin subsystem in LiF single crystal. The theory of USANS starts from eikonal approximation for the scattering amplitude, which (a) reproduces the phenomenological Moliere–Bethe theory for the observable neutron angular distributions for uncorrelated random positions of scatterers, and (b) gives a possibility to take into account their spatial correlations.

We study the correction to scaling of the rms displacements of random walks in disordered media consisted of connected networks of the lattice percolation in two, three, and four dimensions. The two types of ensemble averages, i.e. an infinite-network average of random walks starting from an infinite network and an all-cluster average starting from any occupied site, are investigated using both the myoptic ants and the blind ants models. We find that the rms displacements exhibit strong nonanalytic corrections in all dimensions. The correction exponent δ defined by the rms displacement of t-step random walks via R_t=At^1/d_w (1+Bt^-δ+Ct^-1+⋯) was found as δ≃0.39, 0.27, and 0.27 for, respectively, two, three, and four dimensions for an infinite-network average, and δ≃0.37, 0.28, and 0.24 for an all-cluster average.