前言

1.数据导入

import networkx as nx G = nx.les_miserables_graph() 

2.node2vecWalk

2.1 归一化转移概率

2.1.1 原理解析

2.1.2 Alias采样

2.1.3 代码实现

def init_transition_prob(self):
    """ :return:归一化转移概率矩阵 """
    g = self.G
    nodes_info, edges_info = { 
        }, { 
        }
    for node in g.nodes:
        nbs = sorted(g.neighbors(node)) # 当前节点的邻居节点
        probs = [g[node][n]['weight'] for n in nbs] # 概率就是权重
        # 归一化
        norm = sum(probs)  # 求和
        normalized_probs = [float(n) / norm for n in probs]  # 归一化
        nodes_info[node] = self.alias_setup(normalized_probs)  # 利用Alias采样得到Alias和Prob

    for edge in g.edges:
        # 有向图
        if g.is_directed():
            edges_info[edge] = self.get_alias_edge(edge[0], edge[1])
        # 无向图
        else:
            edges_info[edge] = self.get_alias_edge(edge[0], edge[1])
            edges_info[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0])

    self.nodes_info = nodes_info
    self.edges_info = edges_info

其中alias_setup函数就是Alias Sample的具体实现，代码直接参考了网上现成的：

def alias_setup(self, probs):
    """ :probs: v到所有x的概率 :return: Alias数组与Prob数组 """
    K = len(probs)
    q = np.zeros(K)  # 对应Prob数组
    J = np.zeros(K, dtype=np.int)  # 对应Alias数组
    # Sort the data into the outcomes with probabilities
    # that are larger and smaller than 1/K.
    smaller = []  # 存储比1小的列
    larger = []  # 存储比1大的列
    for kk, prob in enumerate(probs):
        q[kk] = K * prob  # 概率
        if q[kk] < 1.0:
            smaller.append(kk)
        else:
            larger.append(kk)

    # Loop though and create little binary mixtures that
    # appropriately allocate the larger outcomes over the
    # overall uniform mixture.

    # 通过拼凑，将各个类别都凑为1
    while len(smaller) > 0 and len(larger) > 0:
        small = smaller.pop()
        large = larger.pop()

        J[small] = large  # 填充Alias数组
        q[large] = q[large] - (1.0 - q[small])  # 将大的分到小的上

        if q[large] < 1.0:
            smaller.append(large)
        else:
            larger.append(large)

    return J, q

对于不是第二次采样的情况，需要利用get_alias_edge来得到一条边 ( t , v ) (t, v) (t,v)中 v v v到其邻居节点转移概率的Alias数组和Prob数组：

def get_alias_edge(self, t, v):
    """ Get the alias edge setup lists for a given edge. """
    g = self.G
    p = self.p
    q = self.q
    unnormalized_probs = []
    for v_nbr in sorted(g.neighbors(v)):
        if v_nbr == t:
            unnormalized_probs.append(g[v][v_nbr]['weight'] / p)
        elif g.has_edge(v_nbr, t):
            unnormalized_probs.append(g[v][v_nbr]['weight'])
        else:
            unnormalized_probs.append(g[v][v_nbr]['weight'] / q)
    norm_const = sum(unnormalized_probs)
    normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]

    return self.alias_setup(normalized_probs)

代码很容易理解：考虑v的邻居节点v_nbr：如果v_nbr就是t，则非归一化转移概率为 1 p × w \frac{1}{p} \times w p1​×w；如果v_nbr与t间有边，也就是图中 x 1 x_1 x1​，则 α p q ( t , x ) = 1 \alpha_{pq}(t, x)=1 αpq​(t,x)=1，即非归一化转移概率为 1 × w 1 \times w 1×w；否则就是图中 x 2 , x 3 x_2,x_3 x2​,x3​这种情况，非归一化转移概率为 1 q × w \frac{1}{q} \times w q1​×w。 w w w是两个节点间边的权重。

有了非归一化转移概率后，我们再进行归一化（除以和），最后再利用alias_setup函数获得Alias数组和Prob数组。

当我们有了各个节点间的转移概率时，我们在真正采样时需要做出决策，在这些相邻结点中选择一个作为下一个被采样的节点：随机取某一列 k k k(即[1,n]的随机整数，n为邻居节点的个数)，再随机产生一个[0-1]的小数 c c c，如果 P r o b [ k ] > c Prob[k] > c Prob[k]>c，那么采样结果就是 k k k，反之则为Alias[k]。该采样函数实现较为简单：

def alias_draw(self, J, q):
    """ 输入: Prob数组和Alias数组 输出: 一次采样结果 """
    K = len(J)
    # Draw from the overall uniform mixture.
    kk = int(np.floor(npr.rand() * K))  # 随机取一列

    # Draw from the binary mixture, either keeping the
    # small one, or choosing the associated larger one.
    if npr.rand() < q[kk]:  # 比较
        return kk
    else:
        return J[kk]

其中kk或者J[kk]就是我们最终采样的结果。

2.2 node2vecWalk的实现

def node2vecWalk(self, u):
    walk = [u]
    g = self.G
    l = self
        标签： vec2r7505qg超级电容
 
锐单商城拥有海量元器件数据手册、
          IC替代型号，打造
          电子元器件IC百科大全！