算法设计：从大边列表中查找包含特定节点的 CC

Question

给定： 大型边列表，大约有 90-1 亿条边，200 万个节点。这些边组成了一个包含数千个连接组件的巨型图。

我还有一个感兴趣的节点列表。我只想提取包含这些节点的 CC 的边缘。

例如，这是一个小例子：考虑一个内部有 3 个 CC 的小图。

edge_list = [(1,2), (3,2), (1,1), (4,5), (5,6), (4,6), (7,8), (8,9), (9,7)] #three CCs
## Below commands for visualization sake
G = nx.Graph() 
G.add_edges_from(edges)
nx.draw(G, with_labels=True)

我有感兴趣的节点：NOI = [1,5]

我想要一个执行以下操作的函数：

CC_list = find_ccs(edge_list, NOI)
print(CC_list)
#output: [[(1,2), (3,2), (1,1)],
#          [(4,5), (5,6), (4,6)]]

请注意，仅返回包含 NOI 的两个 CC 的边缘。我想大规模地做这个。

我愿意接受任何使用 Networkx、StellarGraph 或 PySpark 的解决方案。我可以使用 pyspark 读取边缘列表，一旦我有了过滤后的边缘列表，我就可以使用任何库将它转换为 CC。

注意：整个图表本身太大，无法完全使用 networkx 或 stellargraph 构建。因此，我必须接受边缘列表并只提取我想要的 ccs。上面的 networkx 示例仅用于可视化目的。

Answer 1

选择一个感兴趣的节点。运行 BFS 从中寻找包含它的连通分量。每次将节点添加到 CC 时，检查它是否是感兴趣的节点并将其从集合中删除以检查是否是。重复直到找到所有包含感兴趣节点的 CC。

运行宁时间是 O(V+E)，其中 V 和 E 是包含感兴趣节点的 CC 的节点和边，而不是更大的图。

算法设计：从大边列表中查找包含特定节点的 CC

Algorithm design: Find CCs containing specific nodes from a large edge list

python

algorithm

networkx

pyspark

stellargraph