Random walk

As explained in Graph Algorithms for Data Science

A random walk is a stochastic graph traversal that repeatedly moves from the current node to a neighboring node according to transition probabilities.

A random walk traverses a graph by repeatedly moving from the current node to a neighboring node. In node2vec, these walks become sentences for the word2vec skip-gram model, turning graph structure into training data for node embeddings. section 9.3.2

A practical random-walk workflow follows these ideas:

• Choose a walk length; each visited node becomes a word, and each walk becomes a sentence. section 9.3.2
• Start walks from every node so the generated sentences can capture the whole graph. section 9.3.2
• Use first-order transitions when the next step depends only on the current node; node2vec instead uses second-order walks that also consider the previous step. section 9.3.2
• For weighted graphs, calculate a connection’s traversal chance as its weight divided by the sum of neighboring weights. section 9.3.2

Turning a walk into a sentence

A walk might start at node A and reach node H through C, B, and F. The sequence A–C–B–F–H becomes a sentence-like training example for the skip-gram model. section 9.3.2

Figure 9.10 Using random walks to produce sentences

Use the figure to follow how a graph traversal becomes a sentence for node embedding training. section 9.3.2

How Graph Algorithms for Data Science covers it

How deep it goes

Explains walk length, first- and second-order transitions, and weighted probabilities without developing advanced probability or implementation details.

Examples

Uses a traversal from A through C, B, and F to H, plus unweighted and weighted neighbor transitions.

What you can do after

Apply it via node2vec to generate sentence-like walks for training node embeddings.

How it connects

Connects random walks to node2vec, word2vec, skip-gram models, node embeddings, and node classification.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Graph Neural Networks in ActionA random walk is a stochastic traversal of a graph that repeatedly moves from a node to one of its connected neighbors according to transition probabilities.
• 

  liveBookmanning.com
  Investing for ProgrammersA random walk is a stochastic process whose successive movements are determined by random variation rather than a predictable directional pattern.

Compare how 3 books explain random walk →

Related concepts

• Node2Vecused by · Node2Vec is a graph representation-learning algorithm that learns node embeddings from biased random walks and their context relationships.
• corpusproduces · A corpus is an organized collection of documents, texts, or other language data assembled for processing, retrieval, analysis, training, or evaluation.
• encoder-decoder architectureimplements · An encoder-decoder architecture is a model design in which an encoder transforms input into an intermediate representation and a decoder uses that representation to produce output.
• second-order biased random walkincludes · A second-order biased random walk chooses its next node using both the current node and the node visited immediately before it.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.