时间戳

首页 > 解决方案 > 图工具有投影二分图的方法吗？

python - 图工具有投影二分图的方法吗？

问题描述

我正在尝试将二分图投影到两个单模式图中。

我想使用双投影方法分析二分图。我一直在使用 NetworkX，但我想尝试一下 graph-tool，因为它声称效率更高。我的图表有可能很快变得非常大，所以我想使用最有效的方法/包。包 graph-tool 声称效率更高，我想尝试一下，但我找不到使用它来投影二分图的方法。有谁知道这是否可以使用图形工具？我发现的唯一信息是创建者要求提出类似问题的人创建一张票，以便他/他们可以开始处理它，但它是从 2014 年开始的。

标签： pythongraph-theoryprojectionbipartitegraph-tool

解决方案

我遇到了同样的问题并得到了解决方案。我已经让它在多达 500 万个节点的图表上工作。

它遵循三个主要步骤：

  1. 使用 is_bipartite 函数生成一个布尔数组，每个顶点所属的集合。
  2. 在要删除的集合上循环，在所有邻居组合之间添加边。
  3. 使用 GraphView 通过仅保留感兴趣集的节点来生成新图形。
g = gt.lattice([5,5])
is_biparitite, part = gt.is_bipartite(g, partition=True)
gt.graph_draw(g, vertex_fill_color=part)  # to view the full graph coloured by set

from itertools import combinations

g_temp = g.copy()  # this is a deepcopy

for v, bipartite_label in enumerate(part):
    if bipartite_label == 0:
        neighbours = list(g.vertex(v).all_neighbours())

        for s, t in combinations(neighbours, 2):
            g_temp.add_edge(s, t)

g_projected = gt.Graph(gt.GraphView(g_temp, vfilt=part.a==1), prune=True)

gt.graph_draw(g_projected)

推荐阅读