PaperlayerView exact revision on arXiv

Source-linked AI summary

Random walks and diffusion on networks

Naoki Masuda, Mason A. Porter, Renaud Lambiotte

arXiv:1612.03281v3physics.soc-phcond-mat.dis-nncs.SI

TL;DR

Random walks connect network architecture with diffusion and provide tools for uncovering structural properties. This review brings together these interconnections and applications, while noting that passive edge-centric continuous-time analyses may be approximate.

  • Problem

    The review addresses how network architecture and differing random-walk definitions shape diffusion and network-structure analysis.

  • Method

    The paper surveys interconnections between random walks and networks, including diffusion, structural analysis, and applications such as respondent-driven sampling.

  • Results

    Random walks support applications in node sampling, centrality analysis, community detection, and diffusion-based methods that can be more robust to noise.

  • Takeaways & Limitations

    Network structure can motivate different natural random-walk definitions and enables flow-based methods for examining centralities and community structure.

  • Takeaways & Limitations

    Passive edge-centric continuous-time random-walk master equations are approximate because prior edge traversals violate independence, except for Poissonian processes.

Abstract

from arXiv · show

Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.

1 Introduction

This review connects random walks with network structure, surveying how network architecture affects diffusion and how random walks support structural analysis and applications. It focuses on selected standard, single-walker processes and their applications rather than attempting comprehensive coverage.

  • The review brings together random walks and networks to examine their interconnections, diffusion dynamics, and applications.
  • Network finiteness, degree heterogeneity, and community structure can make diffusion quantitatively and qualitatively different from diffusion on regular or infinite lattices.
  • The review relates network structure to dynamical properties including stationary distributions and mean first-passage times.
  • It distinguishes discrete-time walks from node-centric and edge-centric continuous-time walks, which correspond to different propagators on heterogeneous-degree networks.
  • Random-walk trajectories support algorithms for identifying central nodes, edges, communities, and other network structures, including PageRank and eigenvector centrality.
  • The review restricts attention mainly to standard single, non-adaptive, conservative diffusive processes and selected physical-insight applications.

2. Random walks on the line

The paper develops discrete- and continuous-time random walks on the infinite line, using Fourier and Laplace methods to connect move count with physical time. It shows Gaussian diffusion under finite-moment conditions and highlights how renewal-time randomness changes observed trajectories.

  • 2.1. Discrete time: A discrete-time walker on the line makes independent random moves whose lengths and directions follow a normalized distribution f(r).
  • 2.1. Discrete time: Fourier transforms convert the discrete-time master equation’s convolution into a product, enabling solutions and moment calculations from the characteristic function.
  • 2.1. Discrete time: With finite first two moments, the long-time solution approaches a Gaussian profile and the position variance grows linearly with time.
  • 2.2. Continuous time: A continuous-time random walk inserts independent waiting times drawn from ψ(τ) between moves, reducing to the discrete-time model when τ = 1 with probability 1.
  • 2.2. Continuous time: The CTRW distinguishes physical-time position p(x; t) from event-time position p(x; n) by averaging over the probability p(n, t) of making n moves by time t.
  • 2.2. Continuous time: On average, the number of moves grows linearly with physical time regardless of ψ(τ), while realized move counts remain random and produce heterogeneous trajectory lengths.
  • 2.2. Continuous time: Fourier–Laplace analysis yields a central CTRW relation whose inverse transform gives p(x; t) and supports large-time analysis.

3.1. Notation

The review assumes mostly finite, unsigned networks and treats heterogeneous-degree structures, while imposing connectivity conditions to analyze walks within relevant components.

  • The review primarily considers finite networks, sometimes examining the N →∞ limit to estimate scaling with node count.
  • Networks may contain self-edges and multiedges, with nonnegative edge weights and ordinary graph structure before multilayer and temporal extensions.
  • The review emphasizes heterogeneous degree distributions because they commonly occur in empirical networks, contrasting with regular networks where all nodes share the same degree.
  • Undirected networks are assumed connected and directed networks weakly connected, so walkers remain within the component where they start without teleportation.

3.2. Discrete time

Discrete-time random walks on networks are analyzed through stationary densities, eigenmodes, relaxation, and first-passage behavior. Network structure determines both convergence and traversal times, with distinct scaling across network families.

  • Stationary density: The stationary density is the left eigenvector of T with eigenvalue 1; for undirected networks it is determined solely by node strength, or degree in unweighted networks.For undirected networks, p_i^* = k_i/(2M).
  • Stationary density: Strength-biased walks make p_i^* uniform when α = −1, while high-strength nodes tend to have larger stationary density when α > −1.The unweighted case α = 0 is included in the latter regime.
  • Eigenmodes and relaxation: The graph Fourier transform maps node-state probabilities to eigenmode amplitudes, with transition-matrix eigenvectors serving as Fourier modes.The stationary density is the mode with eigenvalue 1, while modes with −1 < λℓ < 1 decay to zero.
  • Eigenmodes and relaxation: The second-largest eigenvalue governs relaxation, and a small spectral gap indicates slower convergence.The spectral gap is 1 − λ2, with relaxation speed determined by the ratio between |λ2| and λmax = 1.
  • Stationary-density computation: The power method estimates a directed network’s stationary density by repeatedly left-multiplying a suitable initial vector by T.The initial vector must not be orthogonal to the stationary density.
  • First-passage and recurrence times: Mean first-passage times vary strongly by network family: they scale as N^3/2 in sparse Erdős–Rényi giant components, superlinearly on fractals, and at most N ln N on pseudo-fractal scale-free networks.For fractals, the review relates scaling to N^2/ds = N^dw/df; pseudo-fractal networks mostly exhibit sublinear scaling.

3.3. Continuous-time random walks (CTRWs)

Continuous-time random walks separate movement trajectories from event timing, with node-centric and edge-centric mechanisms producing different temporal behavior and stationary densities. The section also contrasts active and passive walks, showing how network structure, waiting-time distributions, and memory shape relaxation, recurrence, and diffusion.

  • CTRW framework: CTRW dynamics combine a walker's step-by-step trajectory with the times at which moves occur.These components jointly determine the probability of visiting a specified node at a specified time.
  • Node-centric versus edge-centric random walks: Node-centric CTRWs activate nodes and choose destinations with probability proportional to edge weight, whereas edge-centric CTRWs activate edges independently.For node-centric walks, the transition rate on each edge is determined by the node's activation and out-degree; edge-centric walks assign rates to edges.
  • Node-centric versus edge-centric random walks: Node-centric, edge-centric, and discrete-time walks can share statistically identical trajectories while differing in temporal properties and stationary densities.For Poisson processes, all three have the same move-index master equations, but node-centric and edge-centric CTRWs distribute event times differently.
  • Active versus passive random walks: Relaxation time is governed mainly by network bottlenecks when the spectral gap is small, but by the waiting-time distribution when the gap is larger or events are bursty.Weakly connected communities provide one example of structural bottlenecks.
  • Active versus passive random walks: For general inter-event distributions, node-centric CTRWs retain the discrete-time stationary density, and recurrence and first-passage times scale by the mean waiting time.This follows from statistical independence between inter-event times and the number of moves.
  • Active versus passive random walks: Passive edge-centric CTRWs have approximate master equations and memory effects, while heavy-tailed waiting times can promote backtracking and slow diffusion.A walker's next move can depend on the edge used to arrive, and heavy-tailed renewal processes can produce long waiting times.

4. Random walks on generalized networks

Generalized networks make random-walk dynamics depend on multilayer structure, temporal activity, and memory. These extensions change diffusion, stationary behavior, relaxation, community structure, and trajectory interpretation.

  • 4.1. Multilayer networks: Multilayer networks represent multiple subsystems or tie types by coupling corresponding entities across layers.With ℓmax layers, the system can be represented as a network with ℓmaxN nodes.
  • 4.1. Multilayer networks: Small interlayer diffusion makes interlayer hopping the bottleneck controlling relaxation across a multilayer network.In this regime, the spectral gap satisfies λ2 = 2Dx.
  • 4.1. Multilayer networks: For sufficiently large interlayer diffusion, the spectral gap is governed by the slower effective intralayer mode, λs/2.In the Dx →∞ limit, 2Dx diverges while λs/2 has N copies as an eigenvalue.
  • 4.2.1. Activity-driven model: Activity-driven temporal networks generate independent sparse snapshots from node activity potentials and can temporarily trap walkers at isolated nodes.This trapping distinguishes temporal dynamics from an aggregated time-independent network, where edges remain present.
  • 4.2.1. Activity-driven model: Sparse empirical temporal networks can make nominally random-walk trajectories partly deterministic, including a walker that always reaches v4 after three steps in Fig. 6.A node with one neighbor forces movement, while an isolated node prevents movement at that time.
  • 4.2.2. Memory networks: Higher-order memory models may improve accuracy but require exponentially more data and often provide only marginal gains beyond second order.This creates a practical boundary on using higher-order Markov representations.
  • 4.2.2. Memory networks: Second-order memory networks encode transitions between directed edges, allowing movement probabilities to depend on the previous node.Empirical H2 < H1 indicates that first-order models can overestimate available neighbors and neglect memory effects.
  • 4.2.2. Memory networks: Memory effects alter random-walk relaxation and can reveal edge-based communities that first-order models cannot detect.Temporal correlations can increase or decrease the second-largest eigenvalue magnitude, changing confinement and relaxation.

5.1. Search on networks

Random walks support decentralized search when network structure is unknown or only local information is available. Search performance trades off against the overhead and concentration risks created by forwarding queries.

  • 5.1. Search on networks: Random walks provide a viable search strategy when network structure is unknown or only local neighbor information is available.In decentralized peer-to-peer networks, multiple packets independently wander until finding an item or reaching a lifetime limit.
  • 5.1. Search on networks: Search overhead is measured by Nrwnmax, creating a trade-off between the number and lifetime of walkers and the probability of finding an item.Larger Nrwnmax is expected to improve search efficiency while increasing overhead.
  • 5.1. Search on networks: Forwarding queries toward high-degree neighbors can improve search efficiency when neighbor degrees are known.The main limitation is that hubs may receive most queries and become overloaded, depending on their capacity.

5.2. Ranking

Random walks support many network-ranking measures, with PageRank using teleportation to ensure a unique stationary density and random-walk betweenness capturing passage through nodes along walks.

  • Centrality measures: Network centralities rank nodes or edges by relative importance, and many such measures derive from eigenvectors of matrices associated with random walks.Examples include Katz centrality, eigenvector centrality, PageRank, hubs and authorities, and non-backtracking centrality.
  • PageRank: PageRank modifies a network with teleportation so the altered walk is ergodic and has a unique stationary density.Teleportation addresses transient nodes and nonunique stationary densities in empirical directed networks.
  • PageRank: Power iteration converges at a rate proportional to 1/α, while smaller α accelerates convergence but dilutes the original network structure.A popular setting is α = 0.85 with uniform teleportation; personalized PageRank localizes the preference vector for applications such as community detection.
  • PageRank: As α increases, PageRank becomes more heterogeneous and gives more credit to long walks; its stationary density can change drastically with α.For small α, the leading contribution makes the PageRank vector uniform across nodes.
  • Random-walk betweenness centrality: Random-walk betweenness counts visits to a node before a specified target, avoiding the strict shortest-path restriction that can assign zero importance to connecting nodes.In the example, v3 has zero shortest-path betweenness despite potentially connecting different network parts.
  • Discrete-choice models: PCMC estimates transition parameters by maximum likelihood and achieves better predictive performance than benchmark discrete-choice models on two empirical data sets.The CTRW connection also produced multinomial-logit inference algorithms that were faster and more accurate on several data sets.

5.3. Community detection

Random walks reveal community structure through confinement, similarity, coding efficiency, and multiscale persistence, while modularity and related methods have important resolution limitations.

  • Motivation: Dense internal edges and sparse intercommunity connections trap random walkers, so short observations reveal local structure whereas long observations reveal global structure.This confinement motivates random-walk-based community-detection methods.
  • Modularity: Modularity compares within-community edges against a null network, but its resolution limit can hide dense communities below a certain scale.It also favors community sizes that depend on the entire network, not only on internal structure.
  • Markov stability: Markov stability measures the probability that an equilibrium continuous-time walker occupies the same community at times 0 and t.Its exponential term combines walks of various lengths, allowing t to act as a resolution parameter.
  • Markov stability: Large t weights long walks more heavily and yields fewer communities; as t →∞, optimization gives the Fiedler-vector bipartition when the eigenvalue is nondegenerate.A linear approximation e^-tL′ ≈ I − tL′ is used because calculating the matrix exponential is expensive for large networks.
  • Walktrap: Walktrap defines node similarity from DTRW visitation probabilities and hierarchically clusters pairs whose walk-based distance is small.The number of steps must be large enough for travel across the network but not so large that all distances approach zero.
  • InfoMap: InfoMap optimizes the theoretical minimum code length for encoding a random walk using a partition and a two-layer Huffman scheme.Strong community structure makes within-community steps common, so local code words can reduce mean code length despite extra entry and exit words.
  • Other methods: Nibble finds a set with low conductance that is neither too small nor too large and can support network-partitioning algorithms running in O(M) time.Markov stability can also be generalized to multilayer and temporal networks to derive modularity functions.

5.4. Core–periphery structure

Random-walk core–periphery detection seeks sets whose walkers remain unlikely to transition among peripheral nodes, using persistence probability and greedy expansion.

  • Structure: Core–periphery structure consists of densely interconnected core nodes and sparsely connected peripheral nodes that primarily attach to the core.The decomposition may contain one or more cores alongside peripheral nodes.
  • Random-walk criterion: If a walker is at a peripheral node, it is unlikely to visit another peripheral node in the next DTRW step.This motivates measuring a set’s persistence probability.
  • Random-walk criterion: The persistence probability αS is the steady-state probability that a DTRW starting in S remains in S at the next step.For undirected networks, the expression uses stationary densities and transition probabilities.
  • Greedy algorithm: The greedy algorithm starts from a minimum-strength node and adds nodes that yield the smallest persistence probability, breaking ties uniformly at random.The ideal target is αS = 0 for sets containing only peripheral nodes, although this becomes harder as S grows.

5.5. Diffusion maps

Diffusion maps reduce data dimensionality by embedding similarity-weighted networks using random-walk diffusion distances, with parameters controlling retained dimension and geometric scale.

  • Overview: Diffusion maps are random-walk-based dimension-reduction methods designed to preserve quantities such as pairwise distances in a low-dimensional space.They are useful in data mining, image processing, visualization, and related applications.
  • Diffusion distance: A similarity-weighted undirected network represents data points as nodes, with edge weight Aij equal to the similarity between points i and j.The diffusion distance compares the distributions of walks of length n from two nodes.
  • Diffusion distance: Diffusion distance is more robust to noise than directly using the data-derived similarity or distance measure because it aggregates walks of length n.The measure is the same as Walktrap’s distance apart from normalization.
  • Embedding: The diffusion-map embedding retains eigenmodes satisfying |λℓ′|^n > δ|λ2|^n, and Euclidean distance in the resulting space matches diffusion distance within tolerance δ.Each retained component is a diffusion coordinate.
  • Parameter effects: Larger δ retains fewer coordinates and produces greater dimension reduction, while larger n captures geometry on a more global scale.Diffusion maps at different n values can describe multiscale geometric properties.

5.6. Respondent-driven sampling

Respondent-driven sampling uses network recruitment, but degree-dependent visitation requires weighted estimators and remains vulnerable to structural and reporting limitations.

  • Sampling procedure: Respondent-driven sampling recruits participants through successive neighbor referrals beginning from a seed individual.Participants pass coupons to unrecruited neighbors and may receive rewards for participation.
  • Estimation: Degree-dependent recruitment probabilities require a weighted mean rather than an unweighted sample average.The RDS II estimator discounts each sampled node by its degree because stationary visitation probability is proportional to degree.
  • Estimation: The estimator targets means of node quantities and can also estimate proportions by assigning binary indicators to nodes.The sampled set S contains N_S observations used to estimate the population quantity.
  • Limitations: Accurate estimation is difficult when respondents cannot report degrees reliably, and estimator bias persists in networks with communities or multiple components.Directed networks require different techniques because stationary density is not generally proportional to degree.
  • Alternative sampling: Metropolis–Hasting random walks modify edge weights to produce a uniform stationary density for network sampling.The approach has been used in peer-to-peer and online social networks.

5.7. Consensus probability and time of voter models

Voter-model consensus probabilities and times can be analyzed through dual random walks, but updating rules produce distinct dynamics on irregular networks.

  • Consensus outcomes: Consensus probability and conditional mean consensus time depend on both the initial opinion configuration and network structure.The consensus probability concerns reaching one specified opinion, while mean time is conditioned on consensus occurring.
  • Duality: Coalescing random walks provide a dual process in which walkers merge upon meeting, linking consensus probabilities to reversed-network stationary densities.Consensus time equals the time required for all walkers to coalesce, and can be approximated using the first meeting time of two walkers.
  • Updating rules: Unless the network is regular, edge dynamics, traditional voter dynamics, and invasion dynamics must be distinguished even on undirected networks.Their different node- or edge-selection mechanisms lead to different consensus analyses.
  • Edge dynamics: Edge dynamics selects directed edges for opinion copying and has a dual Poissonian edge-centric continuous-time random walk on the edge-reversed network.The corresponding walker master equation uses the reversed adjacency and Laplacian operators.
  • Edge dynamics: For undirected networks under edge dynamics, each node’s consensus probability equals 1/N, so the seed node does not affect opinion-propagation likelihood.This follows because the relevant stationary density is uniform.
  • Updating rules: The traditional voter model maps to a discrete-time random walk on the edge-reversed network, while invasion dynamics maps to edge dynamics using a different weighted adjacency matrix.In the invasion process, a uniformly selected node exports its opinion to a uniformly selected out-neighbor.
  • Invasion process: For invasion dynamics, nodes with small strength are effective at disseminating their opinions.The stated approximation assigns consensus probability proportional to inverse strength.

5.8. DeGroot model

The DeGroot model and random walks share matrix structure: stationary densities quantify influence, while the asymptotic opinion state reaches consensus under a positive spectral gap.

  • Discrete-time correspondence: The discrete-time DeGroot model and discrete-time random walks are driven by the same transition matrix up to transposition and multiplication side.Consequently, their eigenvalues and eigenvectors characterize essentially the same dynamics.
  • Discrete-time correspondence: Under a positive spectral gap, the DeGroot model converges to full consensus, represented by x* proportional to (1, . . . , 1)^⊤.The corresponding random-walk stationary density is the left eigenvector for eigenvalue 1.
  • Influence: A node’s initial opinion affects the final consensus value, and nodes whose initial opinions are closer to that value are interpreted as influential.This interpretation is formulated for general initial conditions through conserved weighted averages.
  • Influence: The stationary density of the associated random walk quantifies each node’s influence on the final collective opinion.The model imposes conservation of a weighted opinion sum to identify these influence weights.
  • Continuous-time correspondence: The continuous-time DeGroot model has an asymptotic consensus state linked to the right zero-eigenvalue eigenvector of the reversed-network Laplacian.The corresponding left eigenvector gives the stationary density of the edge-centric continuous-time random walk.

6. Conclusions and outlook

Random walks are central analytical models and network-science tools, with applications spanning diffusion, structural inference, and coupled dynamical systems. The review concludes that substantial theory and application opportunities remain.

  • Conclusions: Random walks provide tractable linear models for conservative diffusion and support analyses using eigenmodes and relaxation times.Their linearity makes linear-algebraic characterization possible.
  • Outlook: The review identifies future work broadly because random walks have been studied extensively but remain open to new theory and applications.The authors describe the proposed directions as non-exhaustive.
  • Outlook: Non-backtracking random walks offer research directions for community detection, centrality, percolation, and immunization in sparse networks.Their spectrum has convenient properties for sparse-network analysis.
  • Applications: Flow-based random-walk algorithms have been used to study centrality, community structure, core–periphery structure, and network embeddings.Related extensions target role similarity, rich clubs, and multipartite structure.
  • Coupled dynamics: Random walks can be coupled with other dynamics, including infection spreading and mobility in multilayer networks.Such combinations support models of diffusion interacting with additional processes.
  • Applications: Variants such as hungry, waddling, and Lévy random walks continue to generate applications in biological diffusion and network sampling.These examples illustrate ongoing expansion beyond conventional random-walk models.
Loading 1612.03281v3…