docstr: Reference:
  KnightKing: A Fast Distributed Graph Random Walk Engine
  http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf
docstr_tok: ["Reference",":","KnightKing",":","A","Fast","Distributed","Graph","Random","Walk","Engine","http",":","\/\/madsys.cs.tsinghua.edu.cn\/publications\/SOSP19-yang.pdf"]
code: def node2vec_walk2(self, walk_length, start_node):
      """
      Reference:
      KnightKing: A Fast Distributed Graph Random Walk Engine
      http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf
      """
  
      def rejection_sample(inv_p, inv_q, nbrs_num):
          upper_bound = max(1.0, max(inv_p, inv_q))
          lower_bound = min(1.0, min(inv_p, inv_q))
          shatter = 0
          second_upper_bound = max(1.0, inv_q)
          if inv_p > second_upper_bound:
              shatter = second_upper_bound / nbrs_num
              upper_bound = second_upper_bound + shatter
          return upper_bound, lower_bound, shatter
  
      G = self.G
      alias_nodes = self.alias_nodes
      inv_p = 1.0 / self.p
      inv_q = 1.0 / self.q
      walk = [start_node]
      while len(walk) < walk_length:
          cur = walk[-1]
          cur_nbrs = list(G.neighbors(cur))
          if len(cur_nbrs) > 0:
              if len(walk) == 1:
                  walk.append(
                      cur_nbrs[
                          alias_sample(
                              alias_nodes[cur][0], alias_nodes[cur][1]
                          )
                      ]
                  )
              else:
                  upper_bound, lower_bound, shatter = rejection_sample(
                      inv_p, inv_q, len(cur_nbrs)
                  )
                  prev = walk[-2]
                  prev_nbrs = set(G.neighbors(prev))
                  while True:
                      prob = random.random() * upper_bound
                      if prob + shatter >= upper_bound:
                          next_node = prev
                          break
                      next_node = cur_nbrs[
                          alias_sample(
                              alias_nodes[cur][0], alias_nodes[cur][1]
                          )
                      ]
                      if prob < lower_bound:
                          break
                      if prob < inv_p and next_node == prev:
                          break
                      _prob = 1.0 if next_node in prev_nbrs else inv_q
                      if prob < _prob:
                          break
                  walk.append(next_node)
          else:
              break
      return walk
  
imports: import itertools
  import math
  import random
  import pandas
  from joblib import Parallel, delayed
  from .alias import alias_sample, create_alias_table
  from .utils import partition_num
label_desc: Use image node_id 4 for calling the RandomWalker obj's underlying member method code with example usage: obj.node2vec_walk2(walk_length, start_node) and returns: walk, upper_bound,  lower_bound,  shatter