聽說GNN大有可為,從這篇開始學(xué)以致用

# 代碼來源 # https://github.com/phanein/deepwalk# Random walkwith open(f, 'w') as fout:  for walk in graph.build_deepwalk_corpus_iter(G=G, # 圖                                               num_paths=num_paths, # 路徑數(shù)                                               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為節(jié)點,value為與之相連的節(jié)點  """    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 subgraph
  def 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 self
  def 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 self
  def remove_self_loops(self):    # 自已不會與自己有連接    removed = 0    t0 = time()
    for x in self:      if x in self[x]:         self[x].remove(x)        removed += 1        t1 = time()
    logger.info('remove_self_loops: removed {} loops in {}s'.format(removed, (t1-t0)))    return self
  def check_self_loops(self):    for x in self:      for y in self[x]:        if x == y:          return True        return False
  def has_edge(self, v1, v2):    # 兩個節(jié)點是否有邊    if v2 in self[v1] or v1 in self[v2]:      return True    return False
  def degree(self, nodes=None):    # 節(jié)點的度數(shù)    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):    # 圖中邊的數(shù)量    "Returns the number of nodes in the graph"    return sum([self.degree(x) for x in self.keys()])/2
  def number_of_nodes(self):    # 圖中結(jié)點數(shù)量    "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 = self    if start:      path = [start]    else:      # Sampling is uniform w.r.t V, and not w.r.t E      path = [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])) # 相鄰節(jié)點隨機選        else:          path.append(path[0]) # 有一定概率選擇回到起點      else:        break    return [str(node) for node in path]
# TODO add build_walks in here
def build_deepwalk_corpus(G, num_paths, path_length, alpha=0,                      rand=random.Random(0)):  walks = []
  nodes = list(G.nodes())  # 這里和上面論文算法流程對應(yīng)  for cnt in range(num_paths): # 外循環(huán),相當(dāng)于要迭代多少epoch    rand.shuffle(nodes) # 打亂nodes順序,加速收斂    for node in nodes: # 每個node都會產(chǎn)生一條路徑      walks.append(G.random_walk(path_length, rand=rand, alpha=alpha, start=node))    return walks
def 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-pythondef 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 adjlist
def 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 adjlist
def load_adjacencylist(file_, undirected=False, chunksize=10000, unchecked=True):
  if unchecked:    parse_func = parse_adjacencylist_unchecked    convert_func = from_adjlist_unchecked  else:    parse_func = parse_adjacencylist    convert_func = from_adjlist
  adjlist = []
  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 G

def 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 G

def 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 G

def from_adjlist(adjlist):    G = Graph()        for row in adjlist:        node = row[0]        neighbors = row[1:]        G[node] = list(sorted(set(neighbors)))
    return G

def from_adjlist_unchecked(adjlist):    G = Graph()        for row in adjlist:        node = row[0]        neighbors = row[1:]        G[node] = neighbors
    return G

from gensim.models import Word2Vecfrom gensim.models.word2vec import Vocab
logger = 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 = None
        kwargs["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"] = 1        kwargs["hs"] = 1
        if vocabulary_counts != None:          self.vocabulary_counts = vocabulary_counts
        super(Skipgram, self).__init__(**kwargs)