python - 查找非常大的图的组件

Question

我有一个非常大的图表，用一个大小约为 1TB 的文本文件表示，每条边如下。

From-node to-node

我想把它分成弱连接的组件。如果它更小，我可以将它加载到 networkx 并运行他们的组件查找算法。例如 http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_components

有没有办法在不将整个内容加载到内存的情况下做到这一点？

score 11 · Accepted Answer

如果您有足够少的节点（例如几亿个），那么您可以通过使用存储在内存中的不相交集合森林，通过文本文件单次计算连接的组件。

此数据结构仅存储每个节点的等级和父指针，因此如果您的节点足够少，则应该适合内存。

对于更大数量的节点，您可以尝试相同的想法，但将数据结构存储在磁盘上（并且可能通过使用内存中的缓存来存储经常使用的项目来改进）。

下面是一些 Python 代码，它实现了一个简单的不相交集森林的内存版本：

N=7 # Number of nodes
rank=[0]*N
parent=range(N)

def Find(x):
    """Find representative of connected component"""
    if  parent[x] != x:
        parent[x] = Find(parent[x])
    return parent[x]

def Union(x,y):
    """Merge sets containing elements x and y"""
    x = Find(x)
    y = Find(y)
    if x == y:
        return
    if rank[x]<rank[y]:
        parent[x] = y
    elif rank[x]>rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1

with open("disjointset.txt","r") as fd:
    for line in fd:
        fr,to = map(int,line.split())
        Union(fr,to)

for n in range(N):
    print n,'is in component',Find(n)

如果将其应用于名为 disjointset.txt 的文本文件，其中包含：

它打印

0 is in component 3
1 is in component 1
2 is in component 1
3 is in component 3
4 is in component 3
5 is in component 3
6 is in component 6

您可以通过不使用 rank 数组来节省内存，但可能会增加计算时间。

score 1 · Accepted Answer

外部内存图遍历很难获得高性能。我建议不要编写自己的代码，实现细节会影响几个小时的运行时间和几个月的运行时间。您应该考虑使用现有的库，例如stxxl。有关使用它来计算连接组件的论文，请参见此处。

score 1 · Accepted Answer

如果节点的数量太大而无法放入内存，您可以分而治之并使用外部内存排序来为您完成大部分工作（例如sort，Windows 和 Unix 包含的命令可以对比内存大得多的文件进行排序）：

选择一些阈值顶点 k。
读取原始文件并将其每个边写入 3 个文件之一：
- Toa如果其最大编号的顶点 < k
- 如果b其最小编号的顶点 >= k
- 否则c（即如果它有一个顶点 < k 和一个顶点 >= k）
如果a小到可以在内存中求解（找到连通分量）（使用例如Peter de Rivaz 的算法），那么就这样做，否则递归求解。解决方案应该是一个文件，其每行由两个数字组成，x y并按x. 每个x都是一个顶点编号并且y是它的代表——与相同的组件中编号最小的顶点x。
对b.
c按最小编号的端点对边进行排序。
遍历中的每条边c，将 < k 的端点（记住，必须只有一个这样的端点）重命名为其代表，从子问题的解决方案中找到a。这可以通过使用线性时间合并算法与子问题的解决方案合并来有效地完成a。调用生成的文件d。
d按最大编号的端点对边进行排序。（我们已经重命名了编号最小的端点这一事实并不会使这变得不安全，因为重命名永远不会增加顶点的编号。）
遍历中的每条边d，将 >= k 的端点重命名为其代表，b像以前一样使用线性时间合并从解决方案中找到子问题。调用生成的文件e。
解决e。（与aandb一样，如果可能，直接在内存中执行此操作，否则递归。如果您需要递归，则需要找到一种不同的分割边的方法，因为所有边都e已经“跨越”k。你可以例如使用顶点编号的随机排列重新编号顶点，递归解决产生的问题，然后重命名它们。）这一步是必要的，因为可能有一条边（1，k），另一条边（2，k+1）和一个第三条边 (2, k)，这意味着组件 1、2、k 和 k+1 中的所有顶点都需要组合成一个单独的组件。
遍历子问题解决方案中的每一行，如有必要a，使用子问题的解决方案更新此顶点的代表。e这可以使用线性时间合并有效地完成。将新的代表列表（由于我们是从a的解决方案创建的，它已经按顶点编号排序）写入文件f。
对子问题解决方案中的每一行执行同样的b操作，创建文件g。
连接f并g产生最终答案。（为了提高效率，只需将步骤 11 的结果直接附加到f）。

上面使用的所有线性时间合并操作都可以直接从磁盘文件中读取，因为它们只会按递增顺序访问每个列表中的项目（即不需要慢速随机访问）。

python - 查找非常大的图的组件

3 回答 3

Related

Reference