Advanced
Overview
K-Hop Whole Graph algorithm calculates the number of K-hop neighbors for each node and returns those neighbors. The algorithm is widely used in scenarios such as relationship discovery, impact prediction and friend suggestion and so on.
K-Hop Whole Graph can be viewed as the batch execution of UQL command khop()
. Although Ultipa has optimized the K-Hop Whole Graph algorithm for high concurrency performance, massive system resources can still be consumed by the algorithm in large graphs (over tens of millions nodes and edges) or graphs with many super nodes. Therefore, it is recommended to avoid performing K-Hop Whole Graph calculation that is too deep.
In a graph which
nodes/edges = 100
, the theoretical computation amount required to query 5-hop neighbors of a node is 105 (10 billion computational complexity) and it would take 100ms; then 1 million seconds (12 days) are needed to complete such query in a graph of 10 million nodes.
Basic Concept
BFS
BFS is short for Breadth First Search, together with DFS (Depth First Search), are two the most basic traversal principles. K-Hop query follows BFS principle, which means that when traversing the whole graph from one node, it first traverses all the neighbor nodes of the current node that have not arrived yet, and then traverses the neighbor nodes of these neighbor nodes in turns that have not arrived yet.

Starting from the red node and traversing by the BFS principle, the yellow, green, blue nodes are found in succession. Color of these nodes is classified by the distance to the start node, that is, the number of edges of the shortest path(s) from the start node to them. This distance is what the K
means in K-Hop query, which is the K
-hop neighbors of the start node.
Once the start node is given, K values of the other nodes in the graph are also determined. In other words, if a node is the 5th level neighbor of the start node, then it is impossible to appear in the 4th, 6th or other levels.
Direction of K-Hop
K-Hop query in directed graph can be restrained by the direction of the edge where the neighbor is located, this is when some nodes do not have K values and not all nodes are found in the traversal result.

Starting from the red node in the directed graph on the left side, and traversing by the outbound edges and inbound edges; two distinct traversal results are obtained, the purple node does not belong to any level when traversing in the inbound direction and its K value does not exist.
Special Case
Lonely Node, Disconnected Graph
Lonely node will not appear in any K-Hop query result.
For disconnected graph, only nodes belong to the same connected component with the start node are involved in the K-Hop query result, while other nodes cannot be traversed.
Self-loop Edge
Each node is traversed only once in K-Hop query, so the self-loop edge of node can be considered invalid.
Directed Edge
When the K-Hop query is performed without specifying the direction of edges, the direction of edges is ignored, and certain K values are calculated for all nodes in the connected component where that start node is located.
Results and Statistics
Take the graph below as an example, run the K-Hop Whole Graph algorithm against all nodes:

Algorithm results: Calculate 1-Hop neighbor for each node, return _id
, khop_count_1
or _uuid
, khop_count_1
according to the execution method
_uuid | _id | khop_count_1 |
---|---|---|
1 | Card1 | 3 |
2 | Card2 | 3 |
3 | Card3 | 3 |
4 | Card4 | 1 |
5 | Card5 | 2 |
6 | Card6 | 0 |
Algorithm statistics: N/A
Command and Configuration
- Command:
algo(khop_all)
- Configurations for the parameter
params()
:
Name | Type | Default Value | Specification | Description |
---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | IDs or UUIDs of nodes to be calculated; all nodes to be calculated if not set |
depth | int | 1 | >= 1 | Value of K, i.e. the depth |
direction | string | / | in/out, case insensitive | Edge direction in the path; direction ignored if not set |
limit | int | -1 | >=-1 | Number of results to return; return all results if sets to -1 or not set |
order | string | / | ASC/DESC, case insensitive | To sort the returned results; no sorting is applied if not set |
Example: Calculate 2-Hop neighbors in the outbound direction of all nodes
algo(khop_all).params({
depth: 2,
direction: "out"}) as k2
return k2
Algorithm Execution
Task Writeback
1. File Writeback
File Configuration Item | Data in Each Row | Description |
---|---|---|
filename_ids | _id ,_id ,_id ,... |
The first _id is the node that is calculated, the rest _id s represent the neighbor nodes. |
filename_num | _id ,khop_count |
/ |
Example: Calculate 2-Hop neighbors of all nodes, write the algorithm results back to files named ids and num
algo(khop_all).params({
depth: 2
}).write({
file:{
filename_ids: "ids",
filename_num: "num"
}
})
2. Property Writeback
Property Configuration Item | Writeback Content | Property Type | Property Data Type |
---|---|---|---|
property | khop_count |
Node property | uint64 |
Example: Calculate 2-Hop neighbors of all nodes, write the number of neighbors back to node property named khop2
algo(khop_all).params({
depth: 2
}).write({
db:{
property: "khop2"
}
})
3. Statistics Writeback
This algorithm has no statistics.
Direct Return
Alias Ordinal | Type | Description | Column Name |
---|---|---|---|
0 | []perNode | Node and its number of k-Hop neighbors | _uuid , khop_count_<k> |
Example: Calculate 1-Hop neighbors in the outbound direction of all nodes, define algorithm results as alias named kout, and return the results
algo(khop_all).params({
direction: "out"
}) as kout
return kout
Streaming Return
Alias Ordinal | Type | Description | Column Name |
---|---|---|---|
0 | []perNode | Node and its number of k-Hop neighbors | _uuid , khop_count_<k> |
Example: Calculate 2-Hop neighbors all nodes, define algorithm results as alias named k2, and return the results which the count of neighbors is greater than 0
algo(khop_all).params({
depth: 2
}).stream() as k2
where k2.khop_count_2 > 0
return k2
Real-time Statistics
This algorithm has no statistics.