dokimes.py 文件源码

def random_walk(G, steps):
    def walk(G, node, prev_node, steps):
        if steps == 0:
            return 0
        steps -= 1
        neighs = G.neighbors(node)
        neighs_attrs = nx.get_node_attributes(G.subgraph(neighs), 'label')
        neighs_attrs = list(neighs_attrs.values())
        if prev_node is not None:
            neighs_attrs[neighs.index(prev_node)] = 0  # we don't want to return to the previous node
        choice = np.random.choice(a=len(neighs), p=neighs_attrs / np.sum(neighs_attrs))
        val = walk(G, node=neighs[choice], prev_node=node, steps=steps)
        return neighs_attrs[choice] + val

    kernel_value = 0
    for node_attr in G.nodes(data=True):
        node, attr = node_attr
        num_nodes = G.number_of_nodes(), G.number_of_nodes()
        for step in range(steps):
            neighs = G.neighbors(node)
            kernel_value += (step / steps) * walk(G, node=neighs[0], prev_node=None, steps=steps)
    return kernel_value