Reference: KnightKing: A Fast Distributed Graph Random Walk Engine http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf
(self, walk_length, start_node)
| 62 | return walk |
| 63 | |
| 64 | def node2vec_walk2(self, walk_length, start_node): |
| 65 | """ |
| 66 | Reference: |
| 67 | KnightKing: A Fast Distributed Graph Random Walk Engine |
| 68 | http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf |
| 69 | """ |
| 70 | |
| 71 | def rejection_sample(inv_p, inv_q, nbrs_num): |
| 72 | upper_bound = max(1.0, max(inv_p, inv_q)) |
| 73 | lower_bound = min(1.0, min(inv_p, inv_q)) |
| 74 | shatter = 0 |
| 75 | second_upper_bound = max(1.0, inv_q) |
| 76 | if (inv_p > second_upper_bound): |
| 77 | shatter = second_upper_bound / nbrs_num |
| 78 | upper_bound = second_upper_bound + shatter |
| 79 | return upper_bound, lower_bound, shatter |
| 80 | |
| 81 | G = self.G |
| 82 | alias_nodes = self.alias_nodes |
| 83 | inv_p = 1.0 / self.p |
| 84 | inv_q = 1.0 / self.q |
| 85 | walk = [start_node] |
| 86 | while len(walk) < walk_length: |
| 87 | cur = walk[-1] |
| 88 | cur_nbrs = list(G.neighbors(cur)) |
| 89 | if len(cur_nbrs) > 0: |
| 90 | if len(walk) == 1: |
| 91 | walk.append( |
| 92 | cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]) |
| 93 | else: |
| 94 | upper_bound, lower_bound, shatter = rejection_sample( |
| 95 | inv_p, inv_q, len(cur_nbrs)) |
| 96 | prev = walk[-2] |
| 97 | prev_nbrs = set(G.neighbors(prev)) |
| 98 | while True: |
| 99 | prob = random.random() * upper_bound |
| 100 | if (prob + shatter >= upper_bound): |
| 101 | next_node = prev |
| 102 | break |
| 103 | next_node = cur_nbrs[alias_sample( |
| 104 | alias_nodes[cur][0], alias_nodes[cur][1])] |
| 105 | if (prob < lower_bound): |
| 106 | break |
| 107 | if (prob < inv_p and next_node == prev): |
| 108 | break |
| 109 | _prob = 1.0 if next_node in prev_nbrs else inv_q |
| 110 | if (prob < _prob): |
| 111 | break |
| 112 | walk.append(next_node) |
| 113 | else: |
| 114 | break |
| 115 | return walk |
| 116 | |
| 117 | def simulate_walks(self, num_walks, walk_length, workers=1, verbose=0): |
| 118 |
no test coverage detected