发现极大图的组成部分

Question

发现极大图的组成部分

7

我有一个非常庞大的图表，用文本文件表示，大小约为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 有没有不需要将整个东西加载到内存中就能完成的方法？

- Simd

1

你有估计涉及多少节点、边和组件吗？此外，你需要完美的精度还是近似值可以接受？ - Laurence Gonsalves

3个回答

2

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

选择一个阈值顶点k。
读取原始文件，并将每个边写入以下3个文件之一：
- 如果其最大编号的顶点小于k，则写入a
- 如果其最小编号的顶点大于或等于k，则写入b
- 否则，写入c（即如果它有一个顶点小于k且一个顶点大于或等于k）
如果a足够小，在内存中解决（使用例如Peter de Rivaz的算法），然后进行解决。解决方案应该是一个文件，其中每行都由两个数字x y组成，并按x排序。每个x是一个顶点编号，y是其代表 - 与x在同一组件中的最低编号顶点。
对于b也做同样的操作。
按其最小编号的端点对c中的边进行排序。
遍历c中的每条边，将a的解决方案中找到。这可以通过使用线性时间合并算法与子问题a的解决方案进行合并来高效完成。将结果文件命名为d。
按其最大编号的端点对d中的边进行排序。（由于已经重命名了最小编号的端点，所以这不会有安全问题，因为重命名永远不会增加顶点的编号。）
遍历d中的每条边，将≥k的端点重命名为其代表，从子问题b的解决方案中找到，使用与之前相同的线性时间合并。将结果文件命名为e。
解决e。（与a和b一样，如果可能，直接在内存中解决，否则递归。如果需要递归，则需要找到另一种分割边的方法，因为e中的所有边都已经“跨越”k。例如，您可以使用顶点编号的随机排列重新编号顶点，递归解决所得到的问题，然后将它们重命名回来。）这一步是必要的，因为可能存在一条边(1, k)，另一条边(2, k+1)和第三条边(2, k)，这将意味着组件1、2、k和k+1中的所有顶点需要合并为单个组件。
遍历子问题a的每一行，使用子问题e的解决方案在必要时更新此顶点的代表。这可以通过使用线性时间合并来高效完成。将新的代表列表（由于我们是从a的解决方案创建的，所以它们已经按顶点编号排序）写入文件f。
对于子问题b的每一行也做同样的操作，创建文件g。
将f和g连接起来以生成最终答案。（为了更好的效率，步
以上使用的所有线性时间合并操作都可以直接从磁盘文件中读取，因为它们只会按递增顺序访问每个列表中的项目（即不需要慢速随机访问）。

- j_random_hacker

1

外部存储器图遍历很难做到高效。我建议不要编写自己的代码，实现细节是几个小时和几个月运行时间之间的差异。您应该考虑使用现有库，例如stxxl。请参见here中使用它计算连接组件的论文。

- adrianN

这是很好的建议，但是我很遗憾没有找到与stxxl相对应的Python接口。 - Simd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · 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

您可以不使用等级数组来节省内存，但可能会增加计算时间的成本。