| 10 | |
| 11 | |
| 12 | class RandomWalker: |
| 13 | def __init__(self, G, p=1, q=1, use_rejection_sampling=False): |
| 14 | """ |
| 15 | :param G: |
| 16 | :param p: Return parameter,controls the likelihood of immediately revisiting a node in the walk. |
| 17 | :param q: In-out parameter,allows the search to differentiate between “inward” and “outward” nodes |
| 18 | :param use_rejection_sampling: Whether to use the rejection sampling strategy in node2vec. |
| 19 | """ |
| 20 | self.G = G |
| 21 | self.p = p |
| 22 | self.q = q |
| 23 | self.use_rejection_sampling = use_rejection_sampling |
| 24 | |
| 25 | def deepwalk_walk(self, walk_length, start_node): |
| 26 | |
| 27 | walk = [start_node] |
| 28 | |
| 29 | while len(walk) < walk_length: |
| 30 | cur = walk[-1] |
| 31 | cur_nbrs = list(self.G.neighbors(cur)) |
| 32 | if len(cur_nbrs) > 0: |
| 33 | walk.append(random.choice(cur_nbrs)) |
| 34 | else: |
| 35 | break |
| 36 | return walk |
| 37 | |
| 38 | def node2vec_walk(self, walk_length, start_node): |
| 39 | |
| 40 | G = self.G |
| 41 | alias_nodes = self.alias_nodes |
| 42 | alias_edges = self.alias_edges |
| 43 | |
| 44 | walk = [start_node] |
| 45 | |
| 46 | while len(walk) < walk_length: |
| 47 | cur = walk[-1] |
| 48 | cur_nbrs = list(G.neighbors(cur)) |
| 49 | if len(cur_nbrs) > 0: |
| 50 | if len(walk) == 1: |
| 51 | walk.append( |
| 52 | cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]) |
| 53 | else: |
| 54 | prev = walk[-2] |
| 55 | edge = (prev, cur) |
| 56 | next_node = cur_nbrs[alias_sample(alias_edges[edge][0], |
| 57 | alias_edges[edge][1])] |
| 58 | walk.append(next_node) |
| 59 | else: |
| 60 | break |
| 61 | |
| 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 | """ |