The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
arXiv:1603.06613 · doi:10.1088/1751-8113/49/28/285002
Abstract
We present an analytical and numerical study of the paths of self avoiding walks (SAWs) on random networks. Since these walks do not retrace their paths, they effectively delete the nodes they visit, together with their links, thus pruning the network. The walkers hop between neighboring nodes, until they reach a dead-end node from which they cannot proceed. Focusing on Erdős-Rényi networks we show that the pruned networks maintain a Poisson degree distribution, , with an average degree, , that decreases linearly in time. We enumerate the SAW paths of any given length and find that the number of paths, , increases dramatically as a function of . We also obtain analytical results for the path-length distribution, , of the SAW paths which are actually pursued, starting from a random initial node. It turns out that follows the Gompertz distribution, which means that the termination probability of an SAW path increases with its length.
arXiv comment24 pages, 11 figures
References in corpus (13)
- Epidemic spreading in scale-free networks
- Diffusion with Stochastic Resetting
- Percolation of localized attack on complex networks
- First Passage Properties of the Erdos-Renyi Random Graph
- Exploring Complex Networks through Random Walks
- Self-avoiding walks on scale-free networks
- New Lower Bounds on the Self-Avoiding-Walk Connective Constant
- Analytical results for the distribution of shortest path lengths in random networks
- How Many Nodes are Effectively Accessed in Complex Networks?
- Self-avoiding walks and connective constants in small-world networks
- Kinetic growth walks on complex networks
- Kinetic-growth self-avoiding walks on small-world networks
- Random Walks on Complex Networks
Cited by in corpus (11)
- Knowledge Acquisition: A Complex Networks Approach
- Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
- The distribution of first hitting times of random walks on Erdős-Rényi networks
- The distribution of first hitting times of random walks on directed Erdős-Rényi networks
- Analytical results for the distribution of cover times of random walks on random regular graphs
- Self-avoiding walks and connective constants in clustered scale-free networks
- The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
- Efficient network exploration by means of resetting self-avoiding random walkers
- The Compression method and applications
- Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
- The effect of preferential node deletion on the structure of networks that evolve via preferential attachment