图形工具是否有投影二部图的方法? [英] Does graph-tool have a way of projecting bipartite graphs?
问题描述
我正在尝试将二部图投影到两个单模图中.
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.
它遵循三个主要步骤:
- 使用 is_bipartite 函数生成一个布尔数组,其中每个顶点所属的集合.
- 遍历要移除的集合,在所有邻居组合之间添加边.
- 使用 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屋!