如何获取相邻节点？

Question

我正在研究复现Ripple Walk Sampler。这是一种从目标图中提取子图的算法。

在这里，我们需要将s和r设置为参数。s是子图的大小，r是扩展比率，即当前步骤中要采样的邻居节点的比率。

对于子图Gk，它将以随机节点vs初始化，然后沿着节点之间的连接进行扩展。

经过多次扩展，将返回一个大小为s的子图。在每次扩展期间，邻居集包含潜在的要采样的节点。

然后将邻居集中的r个节点添加到当前子图中。

以下是原始伪代码和采样过程示例。

这是我的尝试：

import random
import networkx as nx
import numpy as np

m = np.matrix([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 1, 1, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]])
G = nx.from_numpy_matrix(m) #target graph
r = 0.5 #expansion ratio
S = 4 #subgraph size

Gk = nx.DiGraph() #initialize subgraph
Vk = [] #initialize nodes
vs = random.randint(0, G.size()) #randomly select the initial node from G
Gk.add_node(vs) #add vs to Gk

while len(Vk) < S:
    #get neighbor nodes set of Vk
    NS = [n for n in G.neighbors(vs)]
    print(NS)
    #randomly select r of nodes in NS, add them into the Vk
    for nodes in NS:
        if random.random() < r:
            Vk.append(nodes)

我在伪代码的第四行的逻辑上遇到了困难，那部分是获取Vk的邻居集合。 我知道这段代码是错误的，但我应该如何实现这一部分呢？

有人能帮我修复这个问题吗？任何建议都将不胜感激。

- port trum

Answer 1

给你：

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

def RPS(G, r=0.5, S=4):
    # designed for undirected graph
    #initialize subgraph
    Gk = nx.Graph()
    #initialize nodes 
    Vk = [] 
    #randomly select the initial node from G
    vs = np.random.randint(0, G.size()) 
    print(vs)
    #add vs to Gk
    Gk.add_node(vs) 
    Vk.append(vs)

    while len(Vk) < S:
        #get neighbor nodes set of Vk (step 4) (Also appending j just for the purpose of adding edge)
        NS = [(n, j) for j in Vk for n in G.neighbors(j) if n not in Vk]
        # randomly select r of nodes in NS, add them into the Vk
        for node, j in NS:
            if np.random.uniform() < r:
                Vk.append(node)
                Gk.add_edge(j, node)
                if len(Vk) == S:
                    break
    return Gk

if __name__ == '__main__':
    # "Undirected" graph adjacency matrix
    m = np.matrix([
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
        [1, 0, 1, 0, 0, 1, 0, 0, 0, 0], 
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0], 
        [0, 1, 0, 0, 1, 0, 1, 1, 0, 0], 
        [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0, 1, 0, 0, 1, 1], 
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]])

    # G = nx.from_numpy_matrix(m, create_using=nx.MultiDiGraph())
    G =  nx.from_numpy_matrix(m)
    #expansion ratio
    r  = 0.5
    #subgraph size
    S  = 4

    Gk = RPS(G, r, S)

    # VISUALIZATION
    pos = nx.spring_layout(G)
    nx.draw_networkx_nodes(G, pos)
    nx.draw_networkx_nodes(G, pos, nodelist=list(Gk.nodes()), node_color='r')
    nx.draw_networkx_labels(G, pos)
    nx.draw_networkx_edges(G, pos, edge_color='b', width=0.5)
    nx.draw_networkx_edges(G, pos, edgelist=list(Gk.edges()), edge_color='g', width=1)

    plt.axis('off')
    plt.show() 

示例结果：

(r = 0.5, S = 4，红色-子图，蓝色-目标图)

- Girish Hegde