图形工具是否有投影二部图的方法? [英] Does graph-tool have a way of projecting bipartite graphs?

查看:71
本文介绍了图形工具是否有投影二部图的方法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在尝试将二部图投影到两个单模图中.

I'm trying to project a bipartite graph into two single mode graphs.

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

I'm want to analyze a bipartite graph using the dual projection approach. I have been using NetworkX, but I wanted to try graph-tool since it claims to be more efficient. There is a chance that my graph will get very big very quickly, so I want to use the most efficient method/package. The package graph-tool claims to be more efficient, and I would like to try it out, but I cannot find a way to project a bipartite graph using it. Does anybody know if this is possible using graph-tool? The only information I found was the creator asking somebody who asked a similar question to create a ticket so that he/they can start working on it, but it's from 2014.

推荐答案

我遇到了同样的问题,并找到了有效的解决方案.我已经让它处理了多达 500 万个节点的图形.

I had the same problem and got a solution working. I have got it working on graphs up to 5 million nodes.

它遵循三个主要步骤:

  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)

这篇关于图形工具是否有投影二部图的方法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆