K-Hop All

Overview

The K-Hop All algorithm identifies the neighborhood of each node within a graph. This algorithm finds extensive application in various scenarios, including relationship discovery, impact prediction, and friend suggestion.

The K-Hop All algorithm can be considered as the batch execution of the UQL K-Hop Query.

Considerations

Although the K-Hop All algorithm is optimized for high concurrency performance, it is important to note that this algorithm may require significant computational resources when dealing with large graphs (those with tens of millions of nodes or edges), or graphs containing many super nodes. To optimize performance, it is advisable to avoid performing K-Hop All calculation that is excessively deep, considering the specific characteristics and size of the graph being analyzed.

NOTE

In graph G = (V, E), if |V|/|E|=100, querying the 5-hop neighbors of a node requires a theoretical computational complexity of 10⁵ (equivalent to 10 billion computations), which would take approximately 100ms. Extrapolating from this, completing such a query in a graph with 10 million nodes would require 1 million seconds (equivalent to around 12 days). It's important to consider the computational demands and time requirements when working with graphs of this scale.

Syntax

• Command: algo(khop_all)
• Parameters:

Examples

The example is a transaction network between bank cards:

File Writeback

UQL
algo(khop_all).params({
  ids: ['card1', 'card7'],
  k_start: 2,
  k_end: 3,
  direction: 'out',
  node_property: ['@card.level', '@card.balance'],
  aggregate_opt: ['max', 'mean']
}).write({
  file:{
    filename_ids: 'neighbors',
    filename: 'aggregations'
  }
})

Results: Files neighbors, aggregations

File: neighbors
card1,card7
card1,card3
card1,card4
card7,card4

File: aggregations
card1,4.000000,3174.103333,3.000000,
card7,2.000000,4768.800000,1.000000,

Property Writeback

UQL
algo(khop_all).params({ 
  k_start: 2,
  k_end: 2
}).write({
  db:{ 
    property: 'khop2'
  }
})

Results: The number of 2-hop neighbors of each node is written to a new property named khop2

Direct Return

UQL
algo(khop_all).params({
  ids: ['card1', 'card7'],
  k_start: 2,
  k_end: 3,
  node_property: ['@card.level', '@card.balance'],
  aggregate_opt: ['max', 'mean']
}) as r
return r

Results: r

Stream Return

UQL
algo(khop_all).params({
   uuids: [2],
   k_start: 2,
   k_end: 2,
   node_property: '@card.balance',
   aggregate_opt: 'max'
}).stream() as results 
return results

Results: results