Active network monitoring based on Boolean network tomography is a promising technique to localize link failures instantly in transport networks. However, the required set of monitoring trails must be recomputed after each link failure has occurred to handle succeeding link failures. Existing heuristic methods cannot compute the required monitoring trails in a sufficiently short time when multiple-link failures must be localized in the whole of large-scale managed networks. This paper proposes an approach for computing the required monitoring trails within an allowable expected period specified beforehand. A random walk-based analysis estimates the number of monitoring trails to be computed in the proposed approach. The estimated number of monitoring trails are computed by a lightweight method that only guarantees partial localization within restricted areas. The lightweight method is repeatedly executed until a successful set of monitoring trails achieving unambiguous localization in the entire managed networks can be obtained. This paper demonstrates that the proposed approach can compute a small number of monitoring trails for localizing all independent dual-link failures in managed networks made up of thousands of links within a given expected short period.

Various graph algorithms have been developed with multiple random walks, the movement of several independent random walkers on a graph. Designing an efficient graph algorithm based on multiple random walks requires investigating multiple random walks theoretically to attain a deep understanding of their characteristics. The first meeting time is one of the important metrics for multiple random walks. The first meeting time on a graph is defined by the time it takes for multiple random walkers to meet at the same node in a graph. This time is closely related to the rendezvous problem, a fundamental problem in computer science. The first meeting time of multiple random walks has been analyzed previously, but many of these analyses focused on regular graphs. In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs and clarify the effects of graph structures on expected values. First, we derive the spectral formula of the expected first meeting time on the basis of spectral graph theory. Then, we examine the principal component of the expected first meeting time using the derived spectral formula. The clarified principal component reveals that (a) the expected first meeting time is almost dominated by $n/(1+d_{ m std}^2/d_{ mavg}^2)$ and (b) the expected first meeting time is independent of the starting nodes of random walkers, where n is the number of nodes of the graph. davg and dstd are the average and the standard deviation of weighted node degrees, respectively. Characteristic (a) is useful for understanding the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the variance of the coefficient dstd/davg (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

It is of great importance to recommend collaborators for scholars in academic social networks, which can benefit more scientific research results. Facing the problem of data sparsity of co-author recommendation in academic social networks, a novel recommendation algorithm named HeteroRWR (Heterogeneous Random Walk with Restart) is proposed. Different from the basic Random Walk with Restart (RWR) model which only walks in homogeneous networks, HeteroRWR implements multiple random walks in a heterogeneous network which integrates a citation network and a co-authorship network to mine the k mostly valuable co-authors for target users. By introducing the citation network, HeteroRWR algorithm can find more suitable candidate authors when the co-authorship network is extremely sparse. Candidate recommenders will not only have high topic similarities with target users, but also have good community centralities. Analyses on the convergence and time efficiency of the proposed approach are presented. Extensive experiments have been conducted on DBLP and CiteSeerX datasets. Experimental results demonstrate that HeteroRWR outperforms state-of-the-art baseline methods in terms of precision and recall rate even in the case of incorporating an incomplete citation dataset.

Focusing on the defects of famous defogging algorithms for fog images based on the atmosphere scattering model, we find that it is necessary to obtain accurate transmission map that can reflect the real depths both in large depth and close range. And it is hard to tackle this with just one prior because of the differences between the large depth and close range in foggy images. Hence, we propose a novel prior that simplifies the solution of transmission map by transferring coefficient, called saturation prior. Then, under the Random Walk model, we constrain the transferring coefficient with the color attenuation prior that can obtain good transmission map in large depth regions. More importantly, we design a regularization weight to balance the influences of saturation prior and color attenuation prior to the transferring coefficient. Experimental results demonstrate that the proposed defogging method outperforms the state-of-art image defogging methods based on single prior in terms of details restoring and color preserving.

With the surge of social media platform, users' profile information become treasure to enhance social network services. However, attributes information of most users are not complete, thus it is important to infer latent attributes of users. Contemporary attribute inference methods have a basic assumption that there are enough labeled data to train a model. However, in social media, it is very expensive and difficult to label a large amount of data. In this paper, we study the latent attribute inference problem with very small labeled data and propose the SRW-COND solution. In order to solve the difficulty of small labeled data, SRW-COND firstly extends labeled data with a simple but effective greedy algorithm. Then SRW-COND employs a supervised random walk process to effectively utilize the known attributes information and link structure of users. Experiments on two real datasets illustrate the effectiveness of SRW-COND.

Nowadays, with the development of online social networks (OSN), a mass of online social information has been generated in OSN, which has triggered research on social recommendation. Collaborative filtering, as one of the most popular techniques in social recommendation, faces several challenges, such as data sparsity, cold-start users and prediction quality. The motivation of our work is to deal with the above challenges by effectively combining collaborative filtering technology with social information. The trust relationship has been identified as a useful means of using social information to improve the quality of recommendation. In this paper, we propose a trust-based recommendation approach which uses GlobalTrust (GT) to represent the trust value among users as neighboring nodes. A matrix factorization based on singular value decomposition is used to get a trust network built on the GT value. The recommendation results are obtained through a modified random walk algorithm called GlobalTrustWalker. Through experiments on a real-world sparser dataset, we demonstrate that the proposed approach can better utilize users' social trust information and improve the recommendation accuracy on cold-start users.

In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.

Collective motion stems from the coordinated behaviors among individuals of crowds, and has attracted growing interest from the physics and computer vision communities. Collectiveness is a metric of the degree to which the state of crowd motion is ordered or synchronized. In this letter, we present a scheme to measure collectiveness via link prediction. Toward this aim, we propose a similarity index called superposed random walk with restarts (SRWR) and construct a novel collectiveness descriptor using the SRWR index and the Laplacian spectrum of a network. Experiments show that our approach gives promising results in real-world crowd scenes, and performs better than the state-of-the-art methods.

In the design of distributed systems, defending against Sybil attack is an important issue. Recently, OSN (Online Social Network)-based Sybil defending approaches, which use the fast mixing property of a social network graph with sufficient length of random walks and provide Sybil-resistant trust values, have been proposed. However, because of the probabilistic property of the previous approaches, some honest (non-Sybil) identities obtain low trust value and they are mistakenly considered as Sybil identities. A simple solution of boosting the trust value of honest identities is using longer random walks, but this direct boosting method also increases trust values of Sybil identities significantly. In this paper, a two-step boosting method is proposed to increase the Sybil-resistant trust value of honest identities reasonably and to prevent Sybil identities from having high trust values. The proposed boosting method is composed of two steps: initializing the trust value with a reasonably long random walks and boosting the trust value by using much longer random walks than the first step. The proposed method is evaluated by using sampled social network graphs of Facebook, and it is observed that the proposed method reduces the portion of honest identities mistakenly considered as Sybil identities substantially (from 30% to 1.3%) and keeps the low trust values of Sybil identities.

Many deterministic small-world network models have been proposed so far, and they have been proven useful in describing some real-life networks which have fixed interconnections. Search efficiency is an important property to characterize small-world networks. This paper tries to clarify how the search procedure behaves when random walks are performed on small-world networks, including the classic WS small-world network and three deterministic small-world network models: the deterministic small-world network created by edge iterations, the tree-structured deterministic small-world network, and the small-world network derived from the deterministic uniform recursive tree. Detailed experiments are carried out to test the search efficiency of various small-world networks with regard to three different types of random walks. From the results, we conclude that the stochastic model outperforms the deterministic ones in terms of average search steps.

The expected write deficiency of the index-less indexed flash codes (ILIFC) is studied. ILIFC is a coding scheme for flash memory, and consists of two stages with different coding techniques. This study investigates the write deficiency of the first stage of ILIFC, and shows that omitting the second stage of ILIFC can be a practical option for realizing flash codes with good average performance. To discuss the expected write deficiency of ILIFC, a random walk model is introduced as a formalization of the behavior of ILIFC. Based on the random walk model, two different techniques are developed to estimate the expected write deficiency. One technique requires some computation, but gives very precise estimation of the write deficiency. The other technique gives a closed-form formula of the write deficiency under a certain asymptotic scenario.

When a graph can be decomposed into components of well-connected subgraphs, it is possible to speed up random walks by taking advantage of topology of the graph. In this paper, a modified Metropolis random walk scheme is introduced and conditions are given when it performs better than the original Metropolis algorithm.

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

Distributed systems desire to construct a random overlay graph for robustness, efficient information dissemination and load balancing. A random walk-based overlay construction is a promising alternative to generate an ideal random scale free overlay in distributed systems. However, a simple random walk-based overlay construction can be affected by node churn. Especially, the number of edges increases and the degree distribution is skewed. This inappropriate distortion can be exploited by malicious nodes. In this paper, we propose a modified random walk-based overlay construction supported by a logistic/trial based decision function to compensate the impact of node churn. Through event-driven simulations, we show that the decision function helps an overlay maintain the proper degree distribution, low diameter and low clustering coefficient with shorter random walks.

Several task forces have been working on how to design the future Internet in a clean slate manner and mobility management is one of the key issues to be considered. However, mobility management in the future Internet is still being designed in an “all-in-one” way where all management functions are tightly kept at a single location and this results in cost inefficiency that can be an obstruction to constructing flexible systems. In this paper, we propose a new function-distributed mobility management architecture that can enable more flexible future Internet construction. Furthermore, we show the effectiveness of our proposed system via a cost analysis and computer simulation with a random walk mobility model.

For realistic scale-free networks, we investigate the traffic properties of stochastic routing inspired by a zero-range process known in statistical physics. By parameters α and δ, this model controls degree-dependent hopping of packets and forwarding of packets with higher performance at more busy nodes. Through a theoretical analysis and numerical simulations, we derive the condition for the concentration of packets at a few hubs. In particular, we show that the optimal α and δ are involved in the trade-off between a detour path for α < 0 and long wait at hubs for α > 0; In the low-performance regime at a small δ, the wandering path for α < 0 better reduces the mean travel time of a packet with high reachability. Although, in the high-performance regime at a large δ, the difference between α > 0 and α < 0 is small, neither the wandering long path with short wait trapped at nodes (α = -1), nor the short hopping path with long wait trapped at hubs (α = 1) is advisable. A uniformly random walk (α = 0) yields slightly better performance. We also discuss the congestion phenomena in a more complicated situation with packet generation at each time step.

Model-based movement patterns play a crucial role in evaluating the performance of mobility-dependent Personal Communication Service (PCS) strategies. This study proposes a new normal walk model to represent more closely the daily movement patterns of a mobile station (MS) in PCS networks than a conventional random walk model. A drift angle θ in this model is applied to determine the relative direction in which an MS handoffs in the next one step, based on the concepts that most real trips follow the shortest path and the directions of daily motion are mostly symmetric. Hence, θ is assumed to approach the normal distribution with the parameters: µ is set to 0and σ is in the range of 5to 90. Varying σ thus redistributes the probabilities associated with θ to make the normal mobility patterns more realistic than the random ones. Experimental results verify that the proposed normal walk is correct and valid for modeling an n-layer mesh cluster of PCS networks. Moreover, when σ = 79.5, a normal walk can almost represent, and even replace, a random walk.

This paper proposes a new simulation algorithm for analyzing large power distribution networks, modeled as linear RLC circuits, based on a novel partial random walk concept. The random walk simulation method has been shown to be an efficient way to solve for voltages of small number of nodes in a large power distribution network, but the algorithm becomes expensive to solve for voltages of nodes that are more than a few with high accuracy. In this paper, we combine direct methods like LU factorization with the random walk concept to solve power distribution networks when voltage waveforms from a large number of nodes are required. We extend the random walk algorithm to deal with general RLC networks and show that Norton companion models for capacitors and self-inductors are more amenable for transient analysis by using random walks than Thevenin companion models. We also show that by nodal analysis (NA) formulation for all the voltage sources, LU-based direct simulations of subcircuits can be speeded up. Experimental results demonstrate that the resulting algorithm, called partial random walk (PRW), has significant advantages over the existing random walk method especially when the VDD/GND nodes are sparse and accuracy requirement is high.

In this study, we consider movement-based registration (MBR), improved MBR (IMBR) and distance-based registration (DBR). Analytical models based on 2-dimensional random walk in hexagonal cell configuration are considered to analyze the performance of MBR/IMBR and DBR. Especially, we focus on the derivation of the registration cost of DBR scheme by using analytical method and then show that DBR always outperforms not only MBR but also IMBR.

The rapid growth of state space in a two-dimensional (2D) random walk model imposes heavy computational load on mobility analysis of personal communication services (PCS) networks. This letter presents a novel random walk model with a compact state space by exploiting the symmetry of cellular patterns in a K-layer cluster of cells. The size of the state space is reduced to (K+1)/2(K/2+1)+1, with an asymptotic compression ratio of 12.