标签: bipartite

我的一般问题是,当使用iGraph生成图形时,我松开了顶点名称/标签(这里不确定正确的单词).

我有一个二分网络的边缘列表IC_edge_sub,如下所示:

  new_individualID new_companyID
1             <NA>     10024354c
3        10069415i      2020225c
4        10069415i     16020347c
5        10069272i      2020225c
6        10069272i     16020347c
7        10069274i      2020225c

然后我创建一个图元素:

IC_projected_graphs <- bipartite.projection(IC_twomode, types = 
                         is.bipartite(IC_twomode)$type)

然后折叠它以仅识别companyID之间的连接

IC_projected_graphs <- bipartite.projection(IC_twomode, types =   
                         is.bipartite(IC_twomode)$type)

然后得到邻接矩阵:

CC_matrix_IC_based <- get.adjacency(CC_graph_IC_based); CC_matrix_IC_based

在iGraph中,节点编号从零开始,因此矩阵命名也从零开始.但是,我现在需要在最终的CC_matrix_IC_based矩阵中的edgelist的第二列中指定的"new_companyID".

你能帮助我如何使用原始边缘列表中的信息在最终的邻接矩阵中放入rownames和colnames吗？

我用Google搜索并搜索了堆栈流,但无法找到合适的答案.非常感谢你的帮助

我一直试图理解二分图.据我所知,它是一个图G,可以分为两个子图U和V.So U和V的交集是一个空集,并且union是图G.我试图找到一个图是否是二分或不使用BFS .我还不清楚我们怎么能用BFS找到它.

我们假设我们的图表定义如下.

a:e,f
b:e
c:e,f,h
d:g,h
e:a,b,c
f:a,c,g
g:f,d
h:c,d

我需要的是逐步解释这个图是如何使用BFS的二分图.

我在编程竞赛(安德鲁·斯坦克维奇竞赛21)中遇到一个关于如下游戏的问题时遇到了困难:

尼克和彼得喜欢玩以下游戏[...].他们在一张纸上绘制一个无向二分图G,并将一个标记放在其顶点之一上.之后他们轮流行动.尼克先行动.

移动包括沿着图形边缘移动令牌.之后,在移动之前令牌所在的顶点以及与其相关的所有边缘都将从图形中移除.没有有效动作的玩家输掉游戏.

给出了图表,现在的任务是找到给定的起始节点,如果两个玩家都以最佳方式玩,则起始玩家是赢还是输.总结一下

• 二分图
• 我们给出了起始节点(比如在左侧)
• 我们轮流移动,移动包括跟随边缘,但我们无法访问已经访问过的节点
• 无法移动的球员输球

由于图表是二分图,Nick(第一个玩家)将始终从左侧移除一个节点,Peter将始终从右侧移除一个节点.

图表最多可以有1000个节点(最多500每侧)和50000个边缘,所以需要一个很好的多项式时间算法(这里的时间限制为2秒解决所有首发位置,但我认为我们可以分享很多不同起始位置之间的信息).

我很确定这可以简化为某种顶点覆盖或打包问题,因为图是二分的,但我找不到与这些相关的策略.

我知道一个特殊情况的解决方案:假设两侧分别有n ₁和n ₂个顶点.如果匹配大小为min(n ₁,n ₂)并且如果较小侧的玩家开始,则存在获胜策略:他只需跟随匹配的边缘并自动获胜.

有任何想法吗？

B.add_nodes_from(a, bipartite=1)
B.add_nodes_from(b, bipartite=0)
nx.draw(B, with_labels = True)  
plt.savefig("graph.png")

我得到下图.如何让它看起来像一个合适的二分图？

在绘制不相关的图形时,我遇到了以下算法问题:

我们有一个二分图的平面绘图,其中不相交的集合按列排列,如图所示.我们如何重新排列每列中的节点,以便最小化边缘交叉的数量？我知道这个问题对于一般图形(链接)来说是NP难的,但考虑到图形是二分的,是否存在一些技巧？

作为后续,如果有第三列w,只有v的边缘怎么办？还是进一步？

我想知道是否有一种简单的方法来绘制R中有向二分图形式的2个列表之间元素位置的变化.例如,列表1和2是字符串的向量,不一定包含相同的字符串.内容:

list.1 <- c("a","b","c","d","e","f","g")

list.2 <- c("b","x","e","c","z","d","a")

我想生成类似于:

我在使用igraph包时有轻微的抨击,但不能轻易地构建我想要的东西,我想象并希望不应该太难.

干杯.

如何在R中绘制二分类型的网络？与此类似:

我有类似的数据,但基因和疾病和SARS的权重.这个网络就是一个例子.我有不同的属性.我在这里关注了一个链接.但是由于我对这个主题的了解不多,我无法从中得到很多.在此先感谢您的帮助.

UPDATE

到目前为止,一些答案建议使用邻接列表.在Java中,邻接列表如何？...没有指针正确:)

我正在尝试用Java实现一个Bipartite Graph,从文件中分成两组信息.我找到了这个例子,它实际上完成了这项工作:

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

但是,我想实现我自己的版本......如果你看一下我以前的帖子,你就会明白我为什么要这样做.

所以我必须读取一个文件,我可以从中轻松获得顶点数,但边数不是那么容易.一个示例行是"PersonA PersonB",可以读作"PersonA说PersonB".所以阅读这些内容......

"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"

...产生这种分组:

{A,D,C} and {B,E}.

我将如何实施这个二分图？什么是这项任务的好资源？在创建BipartiteGraph类时,我应该考虑和思考什么(算法)......也许是遍历/排序算法？

我有以下数据框:

structure(list(X1 = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 3L, 3L, 3L, 3L, 4L, 4L, 
4L, 4L, 4L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 6L, 6L, 6L
), .Label = c("1", "2", "3", "4", "5", "6"), class = "factor"), 
    X2 = structure(c(1L, 6L, 8L, 10L, 12L, 13L, 3L, 4L, 1L, 6L, 
    7L, 9L, 10L, 12L, 13L, 3L, 4L, 5L, 10L, 12L, 13L, 4L, 1L, …

有人可以推荐一个库或代码来可视化C#中的二分图吗？

图#似乎不直接支持这种图形(但有一些支持解开顶点).

我想创建一些像这个二分图的图形,节点中有一些文本.宽度和高度相同的节点将是理想的.

WPF控件是完美的,因为它存在于图#中.甚至可能存在XAML定义？作为一个替代方案:报告窗口也可以非常好.

可能在Graph#中有更多经验的人可以提供有关如何利用Graph#进行此操作的提示.

尝试使用NodeXL,但这似乎不是一个完美的解决方案,因为节点似乎没那么多可修改.也许有人可以提供更好的解决方案.玩过Soroush提供的NetworkView.目前,这最接近我想要的.

-update- 尝试了Soroush Falahati共享的NetworkView.这似乎是一个很好的基础,但在我需要的时候还不够灵活.我有些问题,相信没有可以开箱即用的库.(NetworkView具有很好的功能,可以在控件中设置连接/边缘,从而为NodeXL提供额外的提升).也许Graph#可以做得更多,但目前我只是试过这两个.