-
Notifications
You must be signed in to change notification settings - Fork 0
/
walk.py
129 lines (107 loc) · 4.43 KB
/
walk.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#!/usr/bin/python
# -*- coding:utf-8 -*-
from __future__ import division
import random
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
def plot_G(G):
nx.draw(G, with_labels=True)
plt.show()
def get_schema(f_name):
schemes = []
with open(f_name, 'r', encoding='utf-8') as f:
for line in f:
line = line.strip('\n').split('\t')
schemes.append(line)
return schemes
class RWGraph():
def __init__(self, nx_G):
self.G = nx_G
def schema_walk(self, walk_length, start, schema, isweighted=True):
# Simulate a random walk starting from start node.
G = self.G
rand = random.Random()
if schema:
assert schema[0] == schema[-1]
walk = [start]
while len(walk) < walk_length:
cur = walk[-1]
if isweighted:
candidates = dict()
for node,attr in G[cur].items():
if G.nodes[node]["type"] == schema[len(walk) % (len(schema) - 1)]:
candidates[node]=attr['weight'] # eg: candidates = {node_j: 4, node_i, 6}
if len(candidates) != 0:
walk.append(self.weighted_choice(candidates))
else:
break
else:
candidates = []
for node in G[cur].keys():
if self.node_type[node] == schema[len(walk) % (len(schema) - 1)]:
candidates.append(node)
if len(candidates) != 0:
walk.append(rand.choice(candidates))
else:
break
return walk
def weighted_choice(self, weighted_dict):
total = sum(weighted_dict.values())
rad = random.uniform(0.0,total)
cur_total = 0.0
node = ""
for k, v in weighted_dict.items():
cur_total += v
if rad<= cur_total:
node = k
break
return node
def simple_walk(self, walk_length, start, isweighted=True):
# Simulate a random walk starting from start node.
G = self.G
rand = random.Random()
walk = [start]
while len(walk) < walk_length:
cur = walk[-1]
if isweighted:
candidates = dict()
for node,attr in G[cur].items(): # TODO: ItemsView(AtlasView({1: {'weight': 0.9975273768433653}, 79: {'weight': 0.9046505351008906}}))
candidates[node]=attr['weight'] # eg: candidates = {node_j: 4, node_i, 6}
if len(candidates) != 0:
# walk.append(rand.choice(candidates))
walk.append(self.weighted_choice(candidates))
else:
break
else:
candidates = dict()
for node,attr in G[cur].items(): # TODO: ItemsView(AtlasView({1: {'weight': 0.9975273768433653}, 79: {'weight': 0.9046505351008906}}))
candidates[node] = 1. # eg: candidates = {node_j: 4, node_i, 6}
if len(candidates) != 0:
walk.append(self.weighted_choice(candidates))
else:
break
return walk
def simulate_walks(self, num_walks, walk_length, schema, isweighted):
G = self.G
walks = []
nodes = list(G.nodes())
if schema:
for walk_iter in range(num_walks):
random.shuffle(nodes)
for node in nodes:
if schema[0] == G.nodes[n]['type']:
walks.append(self.schema_walk(walk_length=walk_length, start=node, schema=schema, isweighted=isweighted))
else:
for walk_iter in range(num_walks):
random.shuffle(nodes)
for node in nodes:
walks.append(self.simple_walk(walk_length=walk_length, start=node, isweighted=isweighted))
print("Finished random walk!")
return walks
def simulate_walks_on_diff_schemas(self, num_walks, walk_length, schemas, isweighted):
walks_on_diff_schemas = []
for schema in schemas:
walks = self.simulate_walks(num_walks, walk_length, schema, isweighted)
walks_on_diff_schemas.append(walks)
return walks_on_diff_schemas