Journal articles: 'Random walks on network'

1

LI, KEQIN. "PERFORMANCE ANALYSIS AND EVALUATION OF RANDOM WALK ALGORITHMS ON WIRELESS NETWORKS." International Journal of Foundations of Computer Science 23, no. 04 (June 2012): 779–802. http://dx.doi.org/10.1142/s0129054112400369.

Full text

Abstract:

We propose a model of dynamically evolving random networks and give an analytical result of the cover time of the simple random walk algorithm on a dynamic random symmetric planar point graph. Our dynamic network model considers random node distribution and random node mobility. We analyze the cover time of the parallel random walk algorithm on a complete network and show by numerical data that k parallel random walks reduce the cover time by almost a factor of k. We present simulation results for four random walk algorithms on random asymmetric planar point graphs. These algorithms include the simple random walk algorithm, the intelligent random walk algorithm, the parallel random walk algorithm, and the parallel intelligent random walk algorithm. Our random network model considers random node distribution and random battery transmission power. Performance measures include normalized cover time, probability distribution of the length of random walks, and load distribution.

APA, Harvard, Vancouver, ISO, and other styles

2

Ma, Qi, Anders Johansson, Atsushi Tero, Toshiyuki Nakagaki, and David J. T. Sumpter. "Current-reinforced random walks for constructing transport networks." Journal of The Royal Society Interface 10, no. 80 (March 6, 2013): 20120864. http://dx.doi.org/10.1098/rsif.2012.0864.

Full text

Abstract:

Biological systems that build transport networks, such as trail-laying ants and the slime mould Physarum , can be described in terms of reinforced random walks. In a reinforced random walk, the route taken by ‘walking’ particles depends on the previous routes of other particles. Here, we present a novel form of random walk in which the flow of particles provides this reinforcement. Starting from an analogy between electrical networks and random walks, we show how to include current reinforcement. We demonstrate that current-reinforcement results in particles converging on the optimal solution of shortest path transport problems, and avoids the self-reinforcing loops seen in standard density-based reinforcement models. We further develop a variant of the model that is biologically realistic, in the sense that the particles can be identified as ants and their measured density corresponds to those observed in maze-solving experiments on Argentine ants. For network formation, we identify the importance of nonlinear current reinforcement in producing networks that optimize both network maintenance and travel times. Other than ant trail formation, these random walks are also closely related to other biological systems, such as blood vessels and neuronal networks, which involve the transport of materials or information. We argue that current reinforcement is likely to be a common mechanism in a range of systems where network construction is observed.

APA, Harvard, Vancouver, ISO, and other styles

3

Wang, Yan, Ding Juan Wu, Fang Lv, and Meng Long Su. "Exploring activity-driven network with biased walks." International Journal of Modern Physics C 28, no. 09 (September 2017): 1750111. http://dx.doi.org/10.1142/s012918311750111x.

Full text

Abstract:

We investigate the concurrent dynamics of biased random walks and the activity-driven network, where the preferential transition probability is in terms of the edge-weighting parameter. We also obtain the analytical expressions for stationary distribution and the coverage function in directed and undirected networks, all of which depend on the weight parameter. Appropriately adjusting this parameter, more effective search strategy can be obtained when compared with the unbiased random walk, whether in directed or undirected networks. Since network weights play a significant role in the diffusion process.

APA, Harvard, Vancouver, ISO, and other styles

4

Kalikova, A. "Statistical analysis of random walks on network." Scientific Journal of Astana IT University, no. 5 (July 27, 2021): 77–83. http://dx.doi.org/10.37943/aitu.2021.99.34.007.

Full text

Abstract:

This paper describes an investigation of analytical formulas for parameters in random walks. Random walks are used to model situations in which an object moves in a sequence of steps in randomly chosen directions. Given a graph and a starting point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at random, and move to it etc. It is a fundamental dynamic process that arise in many models in mathematics, physics, informatics and can be used to model random processes inherent to many important applications. Different aspects of the theory of random walks on graphs are surveyed. In particular, estimates on the important parameters of hitting time, commute time, cover time are discussed in various works. In some papers, authors have derived an analytical expression for the distribution of the cover time for a random walk over an arbitrary graph that was tested for small values of n. However, this work will show the simplified analytical expressions for distribution of hitting time, commute time, cover time for bigger values of n. Moreover, this work will present the probability mass function and the cumulative distribution function for hitting time, commute time.

APA, Harvard, Vancouver, ISO, and other styles

5

Gannon, M., E. Pechersky, Y. Suhov, and A. Yambartsev. "Random walks in a queueing network environment." Journal of Applied Probability 53, no. 2 (June 2016): 448–62. http://dx.doi.org/10.1017/jpr.2016.12.

Full text

Abstract:

Abstract We propose a class of models of random walks in a random environment where an exact solution can be given for a stationary distribution. The environment is cast in terms of a Jackson/Gordon–Newell network although alternative interpretations are possible. The main tool is the detailed balance equations. The difference compared to earlier works is that the position of the random walk influences the transition intensities of the network environment and vice versa, creating strong correlations. The form of the stationary distribution is closely related to the well-known product formula.

APA, Harvard, Vancouver, ISO, and other styles

6

Zheng, Zhongtuan, Hanxing Wang, Shengguo Gao, and Guoqiang Wang. "Comparison of Multiple Random Walks Strategies for Searching Networks." Mathematical Problems in Engineering 2013 (2013): 1–12. http://dx.doi.org/10.1155/2013/734630.

Full text

Abstract:

We investigate diverse random-walk strategies for searching networks, especially multiple random walks (MRW). We use random walks on weighted networks to establish various models of single random walks and take the order statistics approach to study corresponding MRW, which can be a general framework for understanding random walks on networks. Multiple preferential random walks (MPRW) and multiple simple random walks (MSRW) are two special types of MRW. As search strategies, MPRW prefers high-degree nodes while MSRW searches for low-degree nodes more efficiently. We analyze the first passage time (FPT) of wandering walkers of MRW and give the corresponding formulas of probability distributions and moments, and the mean first passage time (MFPT) is included. We show the convergence of the MFPT of the first arriving walker and find the MFPT of the last arriving walker closely related with the mean cover time. Simulations confirm analytical predictions and deepen discussions. We use a small random network to test the FPT properties from different aspects. We also explore some practical search-related issues by MRW, such as detecting unknown shortest paths and avoiding poor routings on networks. Our results are of practical significance for realizing optimal routing and performing efficient search on complex networks.

APA, Harvard, Vancouver, ISO, and other styles

7

Asztalos, A., and Z. Toroczkai. "Network discovery by generalized random walks." EPL (Europhysics Letters) 92, no. 5 (December 1, 2010): 50008. http://dx.doi.org/10.1209/0295-5075/92/50008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Toth, Christian, Denis Helic, and Bernhard C. Geiger. "Synwalk: community detection via random walk modelling." Data Mining and Knowledge Discovery 36, no. 2 (January 10, 2022): 739–80. http://dx.doi.org/10.1007/s10618-021-00809-w.

Full text

Abstract:

AbstractComplex systems, abstractly represented as networks, are ubiquitous in everyday life. Analyzing and understanding these systems requires, among others, tools for community detection. As no single best community detection algorithm can exist, robustness across a wide variety of problem settings is desirable. In this work, we present Synwalk, a random walk-based community detection method. Synwalk builds upon a solid theoretical basis and detects communities by synthesizing the random walk induced by the given network from a class of candidate random walks. We thoroughly validate the effectiveness of our approach on synthetic and empirical networks, respectively, and compare Synwalk’s performance with the performance of Infomap and Walktrap (also random walk-based), Louvain (based on modularity maximization) and stochastic block model inference. Our results indicate that Synwalk performs robustly on networks with varying mixing parameters and degree distributions. We outperform Infomap on networks with high mixing parameter, and Infomap and Walktrap on networks with many small communities and low average degree. Our work has a potential to inspire further development of community detection via synthesis of random walks and we provide concrete ideas for future research.

APA, Harvard, Vancouver, ISO, and other styles

9

XING, CHANGMING, LIN YANG, and LEI GUO. "RANDOM WALKS WITH A TRAP IN SCALE-FREE FRACTAL HIERARCHICAL LATTICES." Fractals 25, no. 06 (November 21, 2017): 1750058. http://dx.doi.org/10.1142/s0218348x1750058x.

Full text

Abstract:

In this paper, we study two kinds of random walks with a trap in a class of scale-free fractal hierarchical lattices. One is standard random walks belonging to unbiased random walks, while the other one named mixed random walks is biased. The structural properties of these hierarchical lattices are controlled by a parameter [Formula: see text]. We derive exact solutions of the average trapping time (ATT) for the two trapping issue, respectively. The results show that in large networks, both of the ATT grow asymptotically as a power-law function of network size with the exponent related to the parameter [Formula: see text]. It indicates that network structure has a substantial effect on the efficiency of trapping processes performed in scale-free networks. Comparing the results obtained for the two different random walks, we find that changes of the walking rule have no effect on the leading exponent of the ATT, but could modify the coefficient of the formula for the ATT. The findings are helpful for better understanding the influence factor of random walks in complex systems.

APA, Harvard, Vancouver, ISO, and other styles

10

Ikeda, N. "Network formed by traces of random walks." Physica A: Statistical Mechanics and its Applications 379, no. 2 (June 2007): 701–13. http://dx.doi.org/10.1016/j.physa.2007.01.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

JEUB, LUCAS G. S., MICHAEL W. MAHONEY, PETER J. MUCHA, and MASON A. PORTER. "A local perspective on community structure in multilayer networks." Network Science 5, no. 2 (January 12, 2017): 144–63. http://dx.doi.org/10.1017/nws.2016.22.

Full text

Abstract:

AbstractThe analysis of multilayer networks is among the most active areas of network science, and there are several methods to detect dense “communities” of nodes in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on multiplex networks (which are multilayer networks in which different layers correspond to different types of edges) and show that they have very different bottlenecks, which correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks.

APA, Harvard, Vancouver, ISO, and other styles

12

Li, Jianxin, Cheng Ji, Hao Peng, Yu He, Yangqiu Song, Xinmiao Zhang, and Fanzhang Peng. "RWNE: A Scalable Random-Walk based Network Embedding Framework with Personalized Higher-order Proximity Preserved." Journal of Artificial Intelligence Research 71 (June 18, 2021): 237–63. http://dx.doi.org/10.1613/jair.1.12567.

Full text

Abstract:

Higher-order proximity preserved network embedding has attracted increasing attention. In particular, due to the superior scalability, random-walk-based network embedding has also been well developed, which could efficiently explore higher-order neighborhoods via multi-hop random walks. However, despite the success of current random-walk-based methods, most of them are usually not expressive enough to preserve the personalized higher-order proximity and lack a straightforward objective to theoretically articulate what and how network proximity is preserved. In this paper, to address the above issues, we present a general scalable random-walk-based network embedding framework, in which random walk is explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity. Further, we introduce the random walk with restart process into the framework to naturally and effectively achieve personalized-weighted preservation of proximities of different orders. We conduct extensive experiments on several real-world networks and demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods.

APA, Harvard, Vancouver, ISO, and other styles

13

LEE, SANG B. "CORRECTION-TO-SCALING OF RANDOM WALKS IN DISORDERED MEDIA." International Journal of Modern Physics B 17, no. 27 (October 30, 2003): 4867–81. http://dx.doi.org/10.1142/s0217979203022787.

Full text

Abstract:

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 Rt=At1/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.

APA, Harvard, Vancouver, ISO, and other styles

14

Zhang, Yujian, and Hechen Zhang. "Application of Random Walks in Data Processing." Highlights in Science, Engineering and Technology 31 (February 10, 2023): 263–67. http://dx.doi.org/10.54097/hset.v31i.5152.

Full text

Abstract:

A random walk is known as a process that a random walker makes consecutive steps in space at equal intervals of time and the length and direction of each step is determined independently. It is an example of Markov processes, meaning that future movements of the random walker are independent of the past. The applications of random walks are quite popular in the field of mathematics, probability and computer science. Random walk related models can be used in different areas such as prediction, recommendation algorithm to recent supervised learning and networks. It is noticeable that there are few reviews about randoms for the beginners and how random walks are used nowadays in distinctive areas. Hence, the aim of the article is to provide a brief review of classical random walks, including basic concepts and models of the algorithm and then some applications in the field of computer science for the beginners to understand the significance and future of random walks.

APA, Harvard, Vancouver, ISO, and other styles

15

XU, BAOMIN, TINGLIN XIN, YUNFENG WANG, and YANPIN ZHAO. "LOCAL RANDOM WALK WITH DISTANCE MEASURE." Modern Physics Letters B 27, no. 08 (March 13, 2013): 1350055. http://dx.doi.org/10.1142/s0217984913500553.

Full text

Abstract:

Link prediction based on random walks has been widely used. The existing random walk algorithms ignore the probability of a walker visit from the initial node to the destination node for the first time, which makes a major contribution to establish links in some networks. To deal with the problem, we develop a link prediction method named Local Random Walk with Distance (LRWD) based on local random walk and the shortest distance of node pairs. In LRWD, walkers walk with their own steps rather than uniform steps. To evaluate the performance of the LRWD algorithm, we present the concept of distance distribution. The experimental results show that LRWD can improve the prediction accuracy when the distance distribution of the network is relatively concentrated.

APA, Harvard, Vancouver, ISO, and other styles

16

Jing, Xing-Li, Xiang Ling, Jiancheng Long, Qing Shi, and Mao-Bin Hu. "Mean first return time for random walks on weighted networks." International Journal of Modern Physics C 26, no. 06 (March 25, 2015): 1550068. http://dx.doi.org/10.1142/s0129183115500680.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

Wong, Thomas G. "Unstructured search by random and quantum walk." Quantum Information and Computation 22, no. 1&2 (January 2022): 53–85. http://dx.doi.org/10.26421/qic22.1-2-4.

Full text

Abstract:

The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$. In contrast, the discrete-time quantum walk asymptotically takes $\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a success probability of $1$.

APA, Harvard, Vancouver, ISO, and other styles

18

IDE, YUSUKE, and NORIO KONNO. "Continuous-time quantum walks on the threshold network model." Mathematical Structures in Computer Science 20, no. 6 (November 8, 2010): 1079–90. http://dx.doi.org/10.1017/s0960129510000381.

Full text

Abstract:

It is well known that many real world networks have a power-law degree distribution (the scale-free property). However, there are no rigorous results for continuous-time quantum walks on such realistic graphs. In this paper, we analyse the space–time behaviour of continuous-time quantum walks and random walks on the threshold network model, which is a reasonable candidate model having the scale-free property. We show that the quantum walker exhibits localisation at the starting point, although the random walker tends to spread uniformly.

APA, Harvard, Vancouver, ISO, and other styles

19

Wang, Shuai, Weigang Sun, and Song Zheng. "Calculations of first passage time of delayed tree-like networks." International Journal of Modern Physics B 29, no. 28 (October 29, 2015): 1550200. http://dx.doi.org/10.1142/s0217979215502008.

Full text

Abstract:

In this paper, we study random walks in a family of delayed tree-like networks controlled by two network parameters, where an immobile trap is located at the initial node. The novel feature of this family of networks is that the existing nodes have a time delay to give birth to new nodes. By the self-similar network structure, we obtain exact solutions of three types of first passage time (FPT) measuring the efficiency of random walks, which includes the mean receiving time (MRT), mean sending time (MST) and mean first passage time (MFPT). The obtained results show that the MRT, MST and MFPT increase with the network parameters. We further show that the values of MRT, MST and MFPT are much shorter than the nondelayed counterpart, implying that the efficiency of random walks in delayed trees is much higher.

APA, Harvard, Vancouver, ISO, and other styles

20

Zheng, Zhongtuan, Gaoxi Xiao, Guoqiang Wang, Guanglin Zhang, and Kaizhong Jiang. "Mean First Passage Time of Preferential Random Walks on Complex Networks with Applications." Mathematical Problems in Engineering 2017 (2017): 1–14. http://dx.doi.org/10.1155/2017/8217361.

Full text

Abstract:

This paper investigates, both theoretically and numerically, preferential random walks (PRW) on weighted complex networks. By using two different analytical methods, two exact expressions are derived for the mean first passage time (MFPT) between two nodes. On one hand, the MFPT is got explicitly in terms of the eigenvalues and eigenvectors of a matrix associated with the transition matrix of PRW. On the other hand, the center-product-degree (CPD) is introduced as one measure of node strength and it plays a main role in determining the scaling of the MFPT for the PRW. Comparative studies are also performed on PRW and simple random walks (SRW). Numerical simulations of random walks on paradigmatic network models confirm analytical predictions and deepen discussions in different aspects. The work may provide a comprehensive approach for exploring random walks on complex networks, especially biased random walks, which may also help to better understand and tackle some practical problems such as search and routing on networks.

APA, Harvard, Vancouver, ISO, and other styles

21

Chen, Xiao, Tong Hao, Li Han, Meng Leng, Jing Chen, and Jingfeng Guo. "Heterogeneous Network Embedding Based on Random Walks of Type and Inner Constraint." Mathematics 10, no. 15 (July 27, 2022): 2623. http://dx.doi.org/10.3390/math10152623.

Full text

Abstract:

In heterogeneous networks, random walks based on meta-paths require prior knowledge and lack flexibility. On the other hand, random walks based on non-meta-paths only consider the number of node types, but not the influence of schema and topology between node types in real networks. To solve these problems, this paper proposes a novel model HNE-RWTIC (Heterogeneous Network Embedding Based on Random Walks of Type and Inner Constraint). Firstly, to realize flexible walks, we design a Type strategy, which is a node type selection strategy based on the co-occurrence probability of node types. Secondly, to achieve the uniformity of node sampling, we design an Inner strategy, which is a node selection strategy based on the adjacency relationship between nodes. The Type and Inner strategy can realize the random walks based on meta-paths, the flexibility of the walks, and can sample the node types and nodes uniformly in proportion. Thirdly, based on the above strategy, a transition probability model is constructed; then, we obtain the nodes’ embedding based on the random walks and Skip-Gram. Finally, in the classification and clustering tasks, we conducted a thorough empirical evaluation of our method on three real heterogeneous networks. Experimental results show that HNE-RWTIC outperforms state-of-the-art approaches. In the classification task, in DBLP, AMiner-Top, and Yelp, the values of Micro-F1 and Macro-F1 of HNE-RWTIC are the highest: 2.25% and 2.43%, 0.85% and 0.99%, 3.77% and 5.02% higher than those of five other algorithms, respectively. In the clustering task, in DBLP, AMiner-Top, and Yelp networks, the NMI value is increased by 19.12%, 6.91%, and 0.04% at most, respectively.

APA, Harvard, Vancouver, ISO, and other styles

22

Meng, Lingqi, and Naoki Masuda. "Analysis of node2vec random walks on networks." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 476, no. 2243 (November 2020): 20200447. http://dx.doi.org/10.1098/rspa.2020.0447.

Full text

Abstract:

Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyse random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyse the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both backtracking and visiting a neighbour of the previously visited node but do not avoid them completely.

APA, Harvard, Vancouver, ISO, and other styles

23

Fuentes, Emilio Aced, and Simone Santini. "Network navigation with non-Lèvy superdiffusive random walks." Physica A: Statistical Mechanics and its Applications 580 (October 2021): 126158. http://dx.doi.org/10.1016/j.physa.2021.126158.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Tizghadam, Ali, and Alberto Leon-Garcia. "On random walks in direction-aware network problems." ACM SIGMETRICS Performance Evaluation Review 38, no. 2 (October 15, 2010): 9–11. http://dx.doi.org/10.1145/1870178.1870182.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Piccardi, Carlo, Massimo Riccaboni, Lucia Tajoli, and Zhen Zhu. "Random walks on the world input–output network." Journal of Complex Networks 6, no. 2 (October 12, 2017): 187–205. http://dx.doi.org/10.1093/comnet/cnx036.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Volchenkov, Dimitri, and C. Steve Suh. "Statistical Mechanics of Long Walks in Dynamic Complex Networks: Statistical Arguments for Diversifying Selection." Dynamics 2, no. 3 (August 12, 2022): 252–69. http://dx.doi.org/10.3390/dynamics2030013.

Full text

Abstract:

We study the thermodynamic limit of very long walks on finite, connected, non-random graphs subject to possible random modifications and transportation capacity noise. As walks might represent the chains of interactions between system units, statistical mechanics of very long walks may be used to quantify the structural properties important for the dynamics of processes defined in networks. Networks open to random structural modifications are characterized by a Fermi–Dirac distribution of node’s fugacity in the framework of grand canonical ensemble of walks. The same distribution appears as the unique stationary solution of a discrete Fokker–Planck equation describing the time evolution of probability distribution of stochastic processes in networks. Nodes of inferior centrality are the most likely candidates for the future structural changes in the network.

APA, Harvard, Vancouver, ISO, and other styles

27

Lancaster, David. "Random walks between leaves of random networks." Physica A: Statistical Mechanics and its Applications 395 (February 2014): 511–22. http://dx.doi.org/10.1016/j.physa.2013.10.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Su, Jing, Xiaomin Wang, and Bing Yao. "Mean Hitting Time for Random Walks on a Class of Sparse Networks." Entropy 24, no. 1 (December 24, 2021): 34. http://dx.doi.org/10.3390/e24010034.

Full text

Abstract:

For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.

APA, Harvard, Vancouver, ISO, and other styles

29

Papadias, Serafeim, Zoi Kaoudi, Jorge-Arnulfo Quiané-Ruiz, and Volker Markl. "Space-efficient random walks on streaming graphs." Proceedings of the VLDB Endowment 16, no. 2 (October 2022): 356–68. http://dx.doi.org/10.14778/3565816.3565835.

Full text

Abstract:

Graphs in many applications, such as social networks and IoT, are inherently streaming, involving continuous additions and deletions of vertices and edges at high rates. Constructing random walks in a graph, i.e., sequences of vertices selected with a specific probability distribution, is a prominent task in many of these graph applications as well as machine learning (ML) on graph-structured data. In a streaming scenario, random walks need to constantly keep up with the graph updates to avoid stale walks and thus, performance degradation in the downstream tasks. We present Wharf, a system that efficiently stores and updates random walks on streaming graphs. It avoids a potential size explosion by maintaining a compressed, high-throughput, and low-latency data structure. It achieves (i) the succinct representation by coupling compressed purely functional binary trees and pairing functions for storing the walks, and (ii) efficient walk updates by effectively pruning the walk search space. We evaluate Wharf, with real and synthetic graphs, in terms of throughput and latency when updating random walks. The results show the high superiority of Wharf over inverted index- and tree-based baselines.

APA, Harvard, Vancouver, ISO, and other styles

30

Malmros, Jens, Naoki Masuda, and Tom Britton. "Random Walks on Directed Networks: Inference and Respondent-Driven Sampling." Journal of Official Statistics 32, no. 2 (June 1, 2016): 433–59. http://dx.doi.org/10.1515/jos-2016-0023.

Full text

Abstract:

Abstract Respondent-driven sampling (RDS) is often used to estimate population properties (e.g., sexual risk behavior) in hard-to-reach populations. In RDS, already sampled individuals recruit population members to the sample from their social contacts in an efficient snowball-like sampling procedure. By assuming a Markov model for the recruitment of individuals, asymptotically unbiased estimates of population characteristics can be obtained. Current RDS estimation methodology assumes that the social network is undirected, that is, all edges are reciprocal. However, empirical social networks in general also include a substantial number of nonreciprocal edges. In this article, we develop an estimation method for RDS in populations connected by social networks that include reciprocal and nonreciprocal edges. We derive estimators of the selection probabilities of individuals as a function of the number of outgoing edges of sampled individuals. The proposed estimators are evaluated on artificial and empirical networks and are shown to generally perform better than existing estimators. This is the case in particular when the fraction of directed edges in the network is large.

APA, Harvard, Vancouver, ISO, and other styles

31

Zhang, Huai, and Hongjuan Zhang. "Effect of heterogeneous weights on the average trapping time and two types of random walks in weighted directed networks." International Journal of Modern Physics B 33, no. 05 (February 20, 2019): 1950023. http://dx.doi.org/10.1142/s0217979219500231.

Full text

Abstract:

In this paper, we define a class of weighted directed networks with the weight of its edge dominated by a weight parameter w. According to the construction of the networks, we study two types of random walks in the weighted directed networks with a trap fixed on the central node, i.e., standard random walks and mixed random walks. For the standard random walks, the trapping process is controlled by a weight parameter w which changes the transition probability of random walks. For the mixed random walks including nonnearest-neighbor hopping, the trapping process is steered by a stochastic parameter [Formula: see text], where [Formula: see text] changes the walking rule. For the above two techniques, we derive both analytically the average trapping time (ATT) as the measure of trapping efficiency, and the obtained analytical expressions are in good agreement with the corresponding numerical solutions for different values of w and [Formula: see text]. The obtained results indicate that ATT scales superlinearly with network size Nn and the weight parameter w changes simultaneously the prefactor and the leading scalings of ATT, while the stochastic parameter [Formula: see text] can only alter the prefactor of ATT and leave the leading scalings of ATT unchanged. This work may help in paving the way for understanding the effects of the link weight and nonnearest-neighbor hopping in real complex systems.

APA, Harvard, Vancouver, ISO, and other styles

32

Sotero, Roberto C., Lazaro M. Sanchez-Rodriguez, Narges Moradi, and Mehdy Dousty. "Estimation of global and local complexities of brain networks: A random walks approach." Network Neuroscience 4, no. 3 (January 2020): 575–94. http://dx.doi.org/10.1162/netn_a_00138.

Full text

Abstract:

The complexity of brain activity has been observed at many spatial scales and has been proposed to differentiate between mental states and disorders. Here we introduced a new measure of (global) network complexity, constructed as the sum of the complexities of its nodes (i.e., local complexity). The complexity of each node is obtained by comparing the sample entropy of the time series generated by the movement of a random walker on the network resulting from removing the node and its connections, with the sample entropy of the time series obtained from a regular lattice (ordered state) and a random network (disordered state). We studied the complexity of fMRI-based resting-state networks. We found that positively correlated (pos) networks comprising only the positive functional connections have higher complexity than anticorrelation (neg) networks (comprising the negative connections) and the network consisting of the absolute value of all connections (abs). We also observed a significant correlation between complexity and the strength of functional connectivity in the pos network. Our results suggest that the pos network is related to the information processing in the brain and that functional connectivity studies should analyze pos and neg networks separately instead of the abs network, as is commonly done.

APA, Harvard, Vancouver, ISO, and other styles

33

Dou Fei-Ling, Hu Yan-Qing, Li Yong, Fan Ying, and Di Zeng-Ru. "Random walks on spatial networks." Acta Physica Sinica 61, no. 17 (2012): 178901. http://dx.doi.org/10.7498/aps.61.178901.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Stolarksy, Kenneth B., Peter G. Doyle, and J. Laurie Snell. "Random Walks and Electric Networks." American Mathematical Monthly 94, no. 2 (February 1987): 202. http://dx.doi.org/10.2307/2322439.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Malyshev, V., S. Pirogov, and A. Rybko. "Random Walks and Chemical Networks." Moscow Mathematical Journal 4, no. 2 (2004): 441–53. http://dx.doi.org/10.17323/1609-4514-2004-4-2-441-453.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

de la Pena, Victor, Henryk Gzyl, and Patrick McDonald. "Inverse problems for random walks on trees: Network tomography." Statistics & Probability Letters 78, no. 18 (December 2008): 3176–83. http://dx.doi.org/10.1016/j.spl.2008.06.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Liu, Qin, Weigang Sun, and Suyu Liu. "Scalings of first-return time for random walks on generalized and weighted transfractal networks." International Journal of Modern Physics B 33, no. 26 (October 20, 2019): 1950306. http://dx.doi.org/10.1142/s0217979219503065.

Full text

Abstract:

The first-return time (FRT) is an effective measurement of random walks. Presently, it has attracted considerable attention with a focus on its scalings with regard to network size. In this paper, we propose a family of generalized and weighted transfractal networks and obtain the scalings of the FRT for a prescribed initial hub node. By employing the self-similarity of our networks, we calculate the first and second moments of FRT by the probability generating function and obtain the scalings of the mean and variance of FRT with regard to network size. For a large network, the mean FRT scales with the network size at the sublinear rate. Further, the efficiency of random walks relates strongly with the weight factor. The smaller the weight, the better the efficiency bears. Finally, we show that the variance of FRT decreases with more number of initial nodes, implying that our method is more effective for large-scale network size and the estimation of the mean FRT is more reliable.

APA, Harvard, Vancouver, ISO, and other styles

38

Wu, Zikai, and Guangyao Xu. "Mortal random walks on a family of treelike regular fractals with a deep trap." International Journal of Modern Physics B 34, no. 06 (February 24, 2020): 2050031. http://dx.doi.org/10.1142/s0217979220500319.

Full text

Abstract:

Due to the ubiquitous occurrence of evanescence in many physical, chemical and biological scenarios, mortal random walks that incorporate evanescence explicitly have drawn more and more attention. It has been a hot topic to study mortal random walks on distinct network models. In this paper, we study mortal random walks on T fractal and a family of treelike regular fractals with a trap located at central node (i.e., innermost node). First, with self-similar setting composed of T fractal, initial position of the walker and location of trap, the total trapping probability of the mortal walker reduces to a function of walker’s single-step survival parameter [Formula: see text]. In more detail, the total trapping probability is expressed by the [Formula: see text]th iteration of map (scaling function) of [Formula: see text]. Based on the map, the analytical expression of total trapping probability’s dominant behavior, the mean time to trapping (MFPT) and temporal factor are obtained, which are related to random walk dimension. Last, we extend the analysis to a family of treelike regular fractals. On them, the total trapping probability is still expressed as the [Formula: see text]th iteration of the map scaling [Formula: see text]. Accordingly, dominant behavior of total trapping probability, MFPT and temporal factor are determined analytically. Both analytical results obtained on T fractal and more general treelike regular fractals show that the mean time to trapping and desired random walk dimension can be obtained by tuning the survival probability parameter [Formula: see text]. In summary, the work advances the understanding of mortal random walks on more general deterministic networks.

APA, Harvard, Vancouver, ISO, and other styles

39

Dshalalow, Jewgeni H., and Ryan T. White. "Current Trends in Random Walks on Random Lattices." Mathematics 9, no. 10 (May 19, 2021): 1148. http://dx.doi.org/10.3390/math9101148.

Full text

Abstract:

In a classical random walk model, a walker moves through a deterministic d-dimensional integer lattice in one step at a time, without drifting in any direction. In a more advanced setting, a walker randomly moves over a randomly configured (non equidistant) lattice jumping a random number of steps. In some further variants, there is a limited access walker’s moves. That is, the walker’s movements are not available in real time. Instead, the observations are limited to some random epochs resulting in a delayed information about the real-time position of the walker, its escape time, and location outside a bounded subset of the real space. In this case we target the virtual first passage (or escape) time. Thus, unlike standard random walk problems, rather than crossing the boundary, we deal with the walker’s escape location arbitrarily distant from the boundary. In this paper, we give a short historical background on random walk, discuss various directions in the development of random walk theory, and survey most of our results obtained in the last 25–30 years, including the very recent ones dated 2020–21. Among different applications of such random walks, we discuss stock markets, stochastic networks, games, and queueing.

APA, Harvard, Vancouver, ISO, and other styles

40

XING, CHANGMING, YIGONG ZHANG, JUN MA, LIN YANG, and LEI GUO. "EXACT SOLUTIONS FOR AVERAGE TRAPPING TIME OF RANDOM WALKS ON WEIGHTED SCALE-FREE NETWORKS." Fractals 25, no. 02 (April 2017): 1750013. http://dx.doi.org/10.1142/s0218348x1750013x.

Full text

Abstract:

In this paper, we present two deterministic weighted scale-free networks controlled by a weight parameter [Formula: see text]. One is fractal network, the other one is non-fractal network, while they have the same weight distribution when the parameter [Formula: see text] is identical. Based on their special network structure, we study random walks on network with a trap located at a fixed node. For each network, we calculate exact solutions for average trapping time (ATT). Analyzing and comparing the obtained solutions, we find that their ATT all grow asymptotically as a power-law function of network order (number of nodes) with the exponent [Formula: see text] dependent on the weight parameter, but their exponent [Formula: see text] are obviously different, one is an increasing function of [Formula: see text], while the other is opposite. Collectively, all the obtained results show that the efficiency of trapping on weighted Scale-free networks has close relation to the weight distribution, but there is no stable positive or negative correlation between the weight distribution and the trapping time on different networks. We hope these results given in this paper could help us get deeper understanding about the weight distribution on the property and dynamics of scale-free networks.

APA, Harvard, Vancouver, ISO, and other styles

41

Celikkanat, Abdulkadir, and Fragkiskos D. Malliaros. "Exponential Family Graph Embeddings." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3357–64. http://dx.doi.org/10.1609/aaai.v34i04.5737.

Full text

Abstract:

Representing networks in a low dimensional latent space is a crucial task with many interesting applications in graph learning problems, such as link prediction and node classification. A widely applied network representation learning paradigm is based on the combination of random walks for sampling context nodes and the traditional Skip-Gram model to capture center-context node relationships. In this paper, we emphasize on exponential family distributions to capture rich interaction patterns between nodes in random walk sequences. We introduce the generic exponential family graph embedding model, that generalizes random walk-based network representation learning techniques to exponential family conditional distributions. We study three particular instances of this model, analyzing their properties and showing their relationship to existing unsupervised learning models. Our experimental evaluation on real-world datasets demonstrates that the proposed techniques outperform well-known baseline methods in two downstream machine learning tasks.

APA, Harvard, Vancouver, ISO, and other styles

42

Wu, Zikai, and Guangyao Xu. "Unveiling the impact of weight heterogeneity on random walks in weighted extended tree-like fractals." Modern Physics Letters B 35, no. 21 (June 11, 2021): 2150369. http://dx.doi.org/10.1142/s0217984921503693.

Full text

Abstract:

In this paper, we put forward a class of weighted extended tree-like fractals and further use them as test bed to unveil the impact of weight heterogeneity on random walks. Specifically, a family of weighted extended tree-like fractals are first proposed, which are parameterized by a growth parameter [Formula: see text] and weight parameter [Formula: see text]. Then, we explore standard weight-dependent walk on the networks by deploying three traps at initial three nodes. To this end, we derive analytically the average trapping time (ATT) to measure the trapping efficiency and the obtained results show that depending on values of [Formula: see text], ATT may grow sub-linearly, linearly and super-linearly with the network size. Besides, it can also quantitatively impact the leading behavior and pre-factor of ATT simultaneously. Finally, more challenging mixed weight-dependent random walk that takes non-nearest-neighbor hopping is addressed. Analytical solutions of ATT derived under this new scenario imply that weight parameter [Formula: see text] still can qualitatively, quantitatively steer leading behavior and quantitatively affect pre-factor of ATT. As to the stochastic parameter [Formula: see text] controlling mixed random walk, it could only impact the pre-factor of ATT and only have negligible effect on the leading behavior of ATT. In summary, this work could further augment our understanding of random walks on networks.

APA, Harvard, Vancouver, ISO, and other styles

43

Mardoukhi, Yousof, Jae-Hyung Jeon, Aleksei V. Chechkin, and Ralf Metzler. "Fluctuations of random walks in critical random environments." Physical Chemistry Chemical Physics 20, no. 31 (2018): 20427–38. http://dx.doi.org/10.1039/c8cp03212b.

Full text

Abstract:

Percolation networks have been widely used in the description of porous media but are now found to be relevant to understand the motion of particles in cellular membranes or the nucleus of biological cells. We here study the influence of the cluster size distribution on diffusion measurements in percolation networks.

APA, Harvard, Vancouver, ISO, and other styles

44

Tetali, Prasad. "An Extension of Foster's Network Theorem." Combinatorics, Probability and Computing 3, no. 3 (September 1994): 421–27. http://dx.doi.org/10.1017/s0963548300001309.

Full text

Abstract:

Consider an electrical network onnnodes with resistorsrijbetween nodesiandj. LetRijdenote theeffective resistancebetween the nodes. Then Foster's Theorem [5] asserts thatwherei∼jdenotesiandjare connected by a finiterij. In [10] this theorem is proved by making use of random walks. The classical connection between electrical networks and reversible random walks implies a corresponding statement for reversible Markov chains. In this paper we prove an elementary identity for ergodic Markov chains, and show that this yields Foster's theorem when the chain is time-reversible.We also prove a generalization of aresistive inverseidentity. This identity was known for resistive networks, but we prove a more general identity for ergodic Markov chains. We show that time-reversibility, once again, yields the known identity. Among other results, this identity also yields an alternative characterization of reversibility of Markov chains (see Remarks 1 and 2 below). This characterization, when interpreted in terms of electrical currents, implies thereciprocity theoremin single-source resistive networks, thus allowing us to establish the equivalence ofreversibilityin Markov chains andreciprocityin electrical networks.

APA, Harvard, Vancouver, ISO, and other styles

45

Cai, Wenyu, Gilbert Chen Ye, and Hao Zhou. "Graph Generation and Diffusion using Random Walks." Highlights in Science, Engineering and Technology 16 (November 10, 2022): 490–94. http://dx.doi.org/10.54097/hset.v16i.2628.

Full text

Abstract:

Simulations are often used in the study of metro network systems and the interactions of passengers with such systems in the real life. Graph theory is used to represent such metro systems. Simple random graphs are generated using a random graph generation algorithm revolving around random walks. The goal is to use such graphs to analyze the effects of the topologies of the graph parallel to the events which happen in real metro systems. This is done through random walks on the graphs by Monte Carlo Simulation of those random walkers. The simulations showed that the degree of a node in the graph has a near linear relationship with the number of times a specific node has been visited.

APA, Harvard, Vancouver, ISO, and other styles

46

GOÑI, JOAQUÍN, IÑIGO MARTINCORENA, BERNAT COROMINAS-MURTRA, GONZALO ARRONDO, SERGIO ARDANZA-TREVIJANO, and PABLO VILLOSLADA. "SWITCHER-RANDOM-WALKS: A COGNITIVE-INSPIRED MECHANISM FOR NETWORK EXPLORATION." International Journal of Bifurcation and Chaos 20, no. 03 (March 2010): 913–22. http://dx.doi.org/10.1142/s0218127410026204.

Full text

Abstract:

Semantic memory is the subsystem of human memory that stores knowledge of concepts or meanings, as opposed to life specific experiences. The organization of concepts within semantic memory can be understood as a semantic network, where the concepts (nodes) are associated (linked) to others depending on perceptions, similarities, etc. Lexical access is the complementary part of this system and allows the retrieval of such organized knowledge. While conceptual information is stored under certain underlying organization (and thus gives rise to a specific topology), it is crucial to have an accurate access to any of the information units, e.g. the concepts, for efficiently retrieving semantic information for real-time need. An example of an information retrieval process occurs in verbal fluency tasks, and it is known to involve two different mechanisms: "clustering", or generating words within a subcategory, and, when a subcategory is exhausted, "switching" to a new subcategory. We extended this approach to random-walking on a network (clustering) in combination to jumping (switching) to any node with certain probability and derived its analytical expression based on Markov chains. Results show that this dual mechanism contributes to optimize the exploration of different network models in terms of the mean first passage time. Additionally, this cognitive inspired dual mechanism opens a new framework to better understand and evaluate exploration, propagation and transport phenomena in other complex systems where switching-like phenomena are feasible.

APA, Harvard, Vancouver, ISO, and other styles

47

Zhang, Zhongzhi, Jihong Guan, Wenlei Xie, Yi Qi, and Shuigeng Zhou. "Random walks on the Apollonian network with a single trap." EPL (Europhysics Letters) 86, no. 1 (April 2009): 10006. http://dx.doi.org/10.1209/0295-5075/86/10006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Cooper, Colin, Tomasz Radzik, and Yiannis Siantos. "Fast Low-Cost Estimation of Network Properties Using Random Walks." Internet Mathematics 12, no. 4 (March 24, 2016): 221–38. http://dx.doi.org/10.1080/15427951.2016.1164100.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Randles, M., O. Abu-Rahmeh, P. Johnson, and A. Taleb-Bendiab. "Biased random walks on resource network graphs for load balancing." Journal of Supercomputing 53, no. 1 (November 25, 2009): 138–62. http://dx.doi.org/10.1007/s11227-009-0366-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Zelenkovski, Kiril, Trifce Sandev, Ralf Metzler, Ljupco Kocarev, and Lasko Basnarkov. "Random Walks on Networks with Centrality-Based Stochastic Resetting." Entropy 25, no. 2 (February 4, 2023): 293. http://dx.doi.org/10.3390/e25020293.

Full text

Abstract:

We introduce a refined way to diffusely explore complex networks with stochastic resetting where the resetting site is derived from node centrality measures. This approach differs from previous ones, since it not only allows the random walker with a certain probability to jump from the current node to a deliberately chosen resetting node, rather it enables the walker to jump to the node that can reach all other nodes faster. Following this strategy, we consider the resetting site to be the geometric center, the node that minimizes the average travel time to all the other nodes. Using the established Markov chain theory, we calculate the Global Mean First Passage Time (GMFPT) to determine the search performance of the random walk with resetting for different resetting node candidates individually. Furthermore, we compare which nodes are better resetting node sites by comparing the GMFPT for each node. We study this approach for different topologies of generic and real-life networks. We show that, for directed networks extracted for real-life relationships, this centrality focused resetting can improve the search to a greater extent than for the generated undirected networks. This resetting to the center advocated here can minimize the average travel time to all other nodes in real networks as well. We also present a relationship between the longest shortest path (the diameter), the average node degree and the GMFPT when the starting node is the center. We show that, for undirected scale-free networks, stochastic resetting is effective only for networks that are extremely sparse with tree-like structures as they have larger diameters and smaller average node degrees. For directed networks, the resetting is beneficial even for networks that have loops. The numerical results are confirmed by analytic solutions. Our study demonstrates that the proposed random walk approach with resetting based on centrality measures reduces the memoryless search time for targets in the examined network topologies.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Random walks on network'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles