Overview

Random Walk, as the name suggests, refers to starting from a certain node (any or all) in the graph, traversing one of the adjacent edges randomly to reach another node, and repeating this process until all accessible nodes are reached or the limit of the defined depth or time for the traversal is met. The concept of 'random walk' was formally proposed by the British mathematician and biostatistician Karl Pearson in 1905:

• K. Pearson, The Problem of the Random Walk (1905)

Basic Concept

Random Walk

Random walk (RW) is a mathematical model. Each random walk produces a path, each path in the repeated random walks is formed randomly. It is used to represent irregular forms of change, like a random process record formed by a person's drunken steps.

An elementary random walk is performed on the 1-dimensional space: A node starts from the origin of the number line and moves up or down one unit at a time with equal probability, the path of a 10-step random walk is as follows:

Perfrom this random walk multiple times, each time with 100 steps, the paths are illustarted below:

Random Walk in Graph

In the graph, a random walk refers to the process of forming a path by starting from a node and continuously passing through neighbor nodes, the process is regulated by the walk depth (i.e. the number of nodes to be visited) and some filtering conditions (generally, one or multiple properties of edge). Assuming there are 8 nodes in the graph, after performing 300 30-step random walks, 2,400 paths will be produced, and each path contains 30 nodes the maximum.

Ultipa's Random Walk algorithm performs the classic random walk: by default, each edge has the same weight (equals to 1) so that the probability being traversed is the same; when specifying edge weight, the probability of passing through these edges is proportional to the edge weight. In fact, there are many forms of random walks, such as Node2Vec walks, Struc2Vec walks, and GraphSAGE sampling.

Special Case

Lonely Node, Disconnected Graph

Lonely node has no adjacent node, hence it cannot walk to other nodes; lonely node can only walk along its self-loop edge if there is one. The walk paths of non-lonely nodes will not have any lonely node.

Node only walks within its own connected component.

Self-loop Edge

Node may walk along its self-loop edge.

Directed Edge

The direction of edge is ignored when performing random walks.

Results and Statistics

Perform random walk in the whole graph below for 2 times with a depth of 6, each edge weight is 1:

Algorithm results: There are 11 nodes in the graph, thus 11*2 = 22 node arrays are contained in the returned walks

Algorithm statistics: N/A

Command and Configuration

• Command：algo(random_walk)
• Configurations for the parameter params():

Example: Select nodes with UUID = 1,2,...,10 to perform random walk for 2 times with a depth of 6

algo(random_walk).params({
  uuids: [1,2,3,4,5,6,7,8,9,10],
  walk_length: 6,
  walk_num: 2
}) as walks 
return walks

Algorithm Execution

Task Writeback

1. File Writeback

Example: Select nodes with UUID = 1,2,...,10 to perform random walk for 2 times with a depth of 6, write the algorithm results back to file named path

algo(random_walk).params({
  uuids: [1,2,3,4,5,6,7,8,9,10],
  walk_length: 6,
  walk_num: 2
}).write({
  file:{
    filename: "path"
}})

2. Property Writeback

Not supported by this algorithm.

3. Statistics Writeback

This algorithm has no statistics.

Direct Return

Example: Perform random walk in the whole graph for 3 times with a depth of 5, define algorithm results as alias named path, and return the results

algo(random_walk).params({
  walk_length: 5,
  walk_num: 3
}).write({
  file:{
    filename: "path"
}})

Streaming Return

Example: Perform random walk in the whole graph for 3 times with a depth of 5, and specify edge weight locates on property @follow.level, return the results that walked less than 5 steps

algo(random_walk).params({
  walk_length: 5,
  walk_num: 3,
  edge_schema_property: @follow.level
}).stream() as walk 
where size(walk) < 5 
return walk

Real-time Statistics

This algorithm has no statistics.