如何从图中隔离子网络，包括深度为n的节点和边？

Question

我正在尝试写一个脚本，让我可以通过命令行来处理一些大的网络文件。我的目标之一是根据节点标签的匹配来从一个大网络中提取出一个子网络。

简单来说，我会有一个networkx图，里面可能有7000个节点和相应的边，每个节点都有不同的标签。然后，我会把一个字符串，比如“Smith”，和这些节点进行匹配。这样我可能会找到大约30个节点（标签可能是：“John Smith”，“Peter Smith”等等）。接下来，我想创建一个新的networkx网络，里面包含这30个节点，以及它们之间的边，还有这些边连接到的节点，深度可以设定为n，或者选择一直找到所有的节点和边。

我现在的代码写得很糟糕，所以我想试着写一些伪代码：

for node in networkx_network: 
    if searched_string in node:
        new_network.add(node.subnetwork(depth=n))

我花了好几天在网上搜索解决方案，也许subgraph、neighbors或者connected_components是正确的方法，但我就是搞不懂该怎么做。

Answer 1

试试雪球采样吧？

首先，从你已经搜索过的节点中找到包含你关键词的那些节点。

然后，查看这些节点的所有邻居，把它们也加入到你的集合中。

接着，再查看这些邻居的邻居，把新的节点也加入到集合里。

重复这个过程n次。

最后，你会得到一个包含所有你想要的节点的集合，然后用子图功能来获取这个集合中所有节点的子图。

这可能不是最有效的解决方案，但应该能奏效。

Answer 2

single_source_shortest_path 这个函数有一个可选的参数叫做 cutoff。使用这个参数，你可以告诉 networkx 去找某个节点周围一定距离内的其他节点。其实这个功能有点多余，因为在这些路径中还有很多你不需要的信息。如果你只提取出这些路径的键，就能得到所有在这个距离内可以到达的节点，而 networkx 也有方法可以找到包含这些节点及其之间连接的图。

如果你查看这个函数的源代码，并去掉追踪实际路径的部分，就可以让它运行得更高效。不过现在这样用也是可以的：

import networkx as nx
G=nx.fast_gnp_random_graph(100000,0.00002) #sample graph.
base = range(3) #arbitrarily choose to start from nodes 0, 1, and 2
depth = 3  #look for those within length 3.
foundset = {key for source in base for key in nx.single_source_shortest_path(G,source,cutoff=depth).keys()}
H=G.subgraph(foundset)
nx.draw_networkx(H)
import pylab as py
py.savefig('tmp.png')