# 代碼來源
# https://github.com/phanein/deepwalk
#?Random?walk
with?open(f,?'w')?as?fout:for?walk?in?graph.build_deepwalk_corpus_iter(G=G,?#?圖num_paths=num_paths, # 路徑數path_length=path_length, # 路徑長度alpha=alpha,?#rand=rand): #fout.write(u"{}\n".format(u"?".join(v?for?v?in?walk)))class?Graph(defaultdict):"""Efficient?basic?implementation?of?nx這里我們看到,該類繼承defaultdict,圖其實可以簡單的表示為dict,key為節點,value為與之相連的節點"""??def __init__(self):super(Graph, self).__init__(list)def nodes(self):return self.keys()def adjacency_iter(self):return self.iteritems()def subgraph(self, nodes={}):# 提取子圖subgraph = Graph()for n in nodes:if n in self:subgraph[n] = [x for x in self[n] if x in nodes]return subgraphdef make_undirected(self):#因為是無向圖,所以v?in?self[u]并且 u in self[v]t0 = time()for v in list(self):for other in self[v]:if v != other:self[other].append(v)t1 = time()logger.info('make_directed: added missing edges {}s'.format(t1-t0))self.make_consistent()return selfdef make_consistent(self):# 去重t0 = time()for k in iterkeys(self):self[k] = list(sorted(set(self[k])))t1 = time()logger.info('make_consistent: made consistent in {}s'.format(t1-t0))self.remove_self_loops()return selfdef remove_self_loops(self):# 自已不會與自己有連接removed = 0t0 = time()for x in self:if x in self[x]: self[x].remove(x)removed += 1t1 = time()logger.info('remove_self_loops: removed {} loops in {}s'.format(removed, (t1-t0)))return selfdef check_self_loops(self):for x in self:for y in self[x]:if x == y:return Truereturn Falsedef has_edge(self, v1, v2):# 兩個節點是否有邊if v2 in self[v1] or v1 in self[v2]:return Truereturn Falsedef degree(self, nodes=None):#?節點的度數if isinstance(nodes, Iterable):return {v:len(self[v]) for v in nodes}else:return len(self[nodes])def order(self):"Returns the number of nodes in the graph"return len(self) def number_of_edges(self):# 圖中邊的數量"Returns the number of nodes in the graph"return sum([self.degree(x) for x in self.keys()])/2def number_of_nodes(self):# 圖中結點數量"Returns the number of nodes in the graph"return self.order()# 核心代碼def random_walk(self, path_length, alpha=0, rand=random.Random(), start=None):""" Returns a truncated random walk.path_length: Length of the random walk.alpha: probability of restarts.start: the start node of the random walk."""G = selfif start:path = [start]else:# Sampling is uniform w.r.t V, and not w.r.t Epath = [rand.choice(list(G.keys()))]while len(path) < path_length:cur = path[-1]if len(G[cur]) > 0:if rand.random() >= alpha:path.append(rand.choice(G[cur]))?#?相鄰節點隨機選else:path.append(path[0])?#?有一定概率選擇回到起點else:breakreturn [str(node) for node in path]# TODO add build_walks in heredef build_deepwalk_corpus(G, num_paths, path_length, alpha=0,rand=random.Random(0)):walks = []nodes = list(G.nodes())#?這里和上面論文算法流程對應for cnt in range(num_paths): # 外循環,相當于要迭代多少epochrand.shuffle(nodes)?#?打亂nodes順序,加速收斂for node in nodes: # 每個node都會產生一條路徑walks.append(G.random_walk(path_length, rand=rand, alpha=alpha, start=node))return walksdef build_deepwalk_corpus_iter(G, num_paths, path_length, alpha=0,rand=random.Random(0)):# 流式處理用walks = []nodes = list(G.nodes())for cnt in range(num_paths):rand.shuffle(nodes)for node in nodes:yield G.random_walk(path_length, rand=rand, alpha=alpha, start=node)def clique(size):return from_adjlist(permutations(range(1,size+1)))
# http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks-in-python
def grouper(n, iterable, padvalue=None):"grouper(3, 'abcdefg', 'x') --> ('a','b','c'), ('d','e','f'), ('g','x','x')"return zip_longest(*[iter(iterable)]*n, fillvalue=padvalue)def parse_adjacencylist(f):adjlist = []for l in f:if l and l[0] != "#":introw = [int(x) for x in l.strip().split()]row = [introw[0]]row.extend(set(sorted(introw[1:])))adjlist.extend([row])return adjlistdef parse_adjacencylist_unchecked(f):adjlist = []for l in f:if l and l[0] != "#":adjlist.extend([[int(x) for x in l.strip().split()]])return adjlistdef load_adjacencylist(file_, undirected=False, chunksize=10000, unchecked=True):if unchecked:parse_func = parse_adjacencylist_uncheckedconvert_func = from_adjlist_uncheckedelse:parse_func = parse_adjacencylistconvert_func = from_adjlistadjlist = []t0 = time()total = 0 with open(file_) as f:for idx, adj_chunk in enumerate(map(parse_func, grouper(int(chunksize), f))):adjlist.extend(adj_chunk)total += len(adj_chunk)t1 = time()logger.info('Parsed {} edges with {} chunks in {}s'.format(total, idx, t1-t0))t0 = time()G = convert_func(adjlist)t1 = time()logger.info('Converted edges to graph in {}s'.format(t1-t0))if undirected:t0 = time()G = G.make_undirected()t1 = time()logger.info('Made graph undirected in {}s'.format(t1-t0))return G def load_edgelist(file_, undirected=True):G = Graph()with open(file_) as f:for l in f:x, y = l.strip().split()[:2]x = int(x)y = int(y)G[x].append(y)if undirected:G[y].append(x)G.make_consistent()return Gdef load_matfile(file_, variable_name="network", undirected=True):mat_varables = loadmat(file_)mat_matrix = mat_varables[variable_name]return from_numpy(mat_matrix, undirected)def from_networkx(G_input, undirected=True):G = Graph()for idx, x in enumerate(G_input.nodes()):for y in iterkeys(G_input[x]):G[x].append(y)if undirected:G.make_undirected()return Gdef from_numpy(x, undirected=True):G = Graph()if issparse(x):cx = x.tocoo()for i,j,v in zip(cx.row, cx.col, cx.data):G[i].append(j)else:raise Exception("Dense matrices not yet supported.")if undirected:G.make_undirected()G.make_consistent()return Gdef from_adjlist(adjlist):G = Graph()for row in adjlist:node = row[0]neighbors = row[1:]G[node] = list(sorted(set(neighbors)))return Gdef from_adjlist_unchecked(adjlist):G = Graph()for row in adjlist:node = row[0]neighbors = row[1:]G[node] = neighborsreturn G
至于skipgram,大家可以直接用gensim工具即可.
from gensim.models import Word2Vec
from gensim.models.word2vec import Vocablogger = logging.getLogger("deepwalk")class Skipgram(Word2Vec):"""A subclass to allow more customization of the Word2Vec internals."""def __init__(self, vocabulary_counts=None, **kwargs):self.vocabulary_counts = Nonekwargs["min_count"] = kwargs.get("min_count", 0)kwargs["workers"] = kwargs.get("workers", cpu_count())kwargs["size"] = kwargs.get("size", 128)kwargs["sentences"] = kwargs.get("sentences", None)kwargs["window"] = kwargs.get("window", 10)kwargs["sg"] = 1kwargs["hs"] = 1if vocabulary_counts != None:self.vocabulary_counts = vocabulary_countssuper(Skipgram, self).__init__(**kwargs)
