问题标签 [bipartite]

我正在尝试解决以下问题，但我的算法太慢了。那是因为我正在使用Edmonds - Karp 算法来找到最大流量，当应用于二分图时，它也能提供最大匹配。它的运行时间是n^5。我想知道任何更快的算法来解决这个问题（特别是二分图）。我目前正在研究的一种算法是Relabel to Front，即 n^3。

假设您有一个二分图 G = (V, U, E)

v1 连接到 u1、u2 和 u3

v2 连接到 u2 和 u3

v3 连接到 u3。

通过查看图表，我知道最小顶点覆盖是{v1，v2，u3}和{v1，u2，u3}，但我不确定如何使用二分匹配/顶点覆盖算法来找出这个. 这里 和这里

当我手动执行算法时，输出只是微不足道的最小顶点覆盖，所有 V。我做错了什么吗？

编辑：

图的最大匹配是边 (v1, u1)、(v2, u2) 和 (v3, u3)。给定最大匹配，下一步是从不饱和顶点（不是匹配边的端点之一的顶点）开始

但在这种情况下，所有顶点都已饱和，所以我不知道如何进行。

我有具有 1000 个顶点的二分列表（帖子、单词类别），并且想使用快速和贪婪的算法进行社区检测，但我不确定是否必须在二分图或二分投影上运行它。

我的二分列表如下所示：

当我在没有投影的情况下运行它时，我在第二步中遇到了聚类问题：

也许我必须在投影上运行社区检测？但是后来我总是失败，因为投影不是图形对象：

我很乐意提供帮助！

我有一个由一百万行组成的大数据，组成了一个二分网络。网络一侧代表APP，另一侧代表IP。

数据格式为：

我想做的是通过igraph（python接口）编写一些东西来将数据投影到一侧。例如

权重代表1.1.1.1节点共享一个普通APP（1）和普通APP（2）1.2.1.1

我想将重量保存在格式为的文件中txt

我有点困惑如何处理这个问题igraph。

可以igraph处理这个问题吗？

谢谢

考虑一个有向二分图，其中顶点集 A 和 B 都有 m 个加权顶点。边只从 A 到 B，并且 A 中的所有顶点都具有相同的度数，我们用 n 表示。顶点权重的上限是它们的度数。

例如，考虑 m = 4 和 n = 2，所以我们有 A 和 B，每个有 4 个顶点，并且从 A 的每个顶点到 B 的两条边。A 中顶点的所有权重上限为 2。

我有兴趣遍历从 A 到 B 的所有可能的边流，特别是 B 中顶点的结果权重。我想在 C 中尽可能高效地执行此操作，特别是在内存很少的情况下，因为我将使用这作为深度优先搜索中的子程序。

我真的希望你的聪明输入:)

编辑：所有边的容量为 1

这不是家庭作业，而是我在研究过程中遇到的一个问题。我需要知道这个问题是否是 NP 难的。在第一种情况下，我需要一个近似算法，而在后一种情况下，我需要一个有效的算法，为我提供最佳解决方案。

非正式描述：

想象 p 个人使用一些 t 工具。每个人只使用几种工具，但不是全部。有人写下谁使用了哪个工具。问题：如何找到最大的一组人，每个人至少使用了 k 个其他人也使用的工具？【之前的问题描述：和大家一样的工具？】工具数量限制为t'

我对此问题进行了正式描述，这可能会有所帮助：

令 G=(P,T,E) 是一个二分图，其中 P 代表人的集合，T 代表工具的集合。如果该人使用该工具，则在 P 中的节点 p 和 T 中的节点 t 之间存在一条边。目标是找到满足以下条件的集合 P'，T'： 1) 从 P' 中的任何 p'，T' 中的任何 t' 都可以通过一条边到达。2）|P'|，即P'中的节点数最大。

一种低效的方法是获取每个子集 P' 并计算与 P' 中的 p' 相关联的每个 t' 的交集。不幸的是，此类子集的数量呈指数增长，计算很快变得难以处理。

非常感谢！

我想根据给定的用户偏好（用户喜欢的项目）对项目进行排名，该偏好基于在 groovy 中使用 gremlin 在有向二部图上的随机游走。

该图具有以下基本结构：

[User1] ---'喜欢'---> [ItemA] <---'喜欢'--- [User2] ---'喜欢'---> [ItemB]

此后我提出的查询：

但是，此代码没有找到新项目（上面示例中的 [ItemB]），而只找到给定用户喜欢的项目（例如 [ItemA]）。

• 为了继续步行，我需要更改什么以将循环步骤返回到“out（'likes'）”步骤来喂养新用户（例如 [User2]）？

• 一旦这段代码工作，它可以被视为“个性化 PageRank”的实现吗？

这里是运行示例的代码：

和输出：

我有一个相当大的文件（300 万行），每一行都是人与事件的关系。最终，我想将此二分网络投影到单模加权网络上，并将其写入 CSV 文件。我正在使用 NetworkX，并且我在一个小得多的示例数据集上测试了我的代码，并且它可以正常工作。然而，当我扩大到我的实际数据集时，我的计算机只是最大限度地利用内存并旋转和旋转，但没有取得任何进展。

我正在使用具有 32GB 内存的 AWS EC2 机器。

经过一些示例测试后，我很确定在投影图表后的最后一步中事情会被挂起，并且它正在被写入 CSV 文件。我尝试将文件分解成块，但是我遇到了缺少边缘或正确地将边缘权重添加在一起的问题。但我认为更好的解决方案是找到一种方法来加快将投影图写入 CSV 的速度。

有关原始数据的更多信息：一些活动只有 1 人参加，而其他活动有 5,000 人参加。正因为如此，当二分网络折叠到单模网络上时，会产生大量的边（我预测约为 50M）。

使用 NetworkX 来投影二分网络并写入 CSV 的代码

使用 Pandas 编写投影边缘列表，但缺少边缘权重？

我考虑过使用pandas写入name_graphCSV。这是加快写入 CSV 部分过程的好选择吗？

我有一个双边图，一侧有 N 个节点，另一侧有近 100 个节点。现在我需要计算匹配项，以便第一部分中的每个节点都与另一部分中的某个节点有链接，这样第一部分中没有两个节点与第二部分中的相同节点匹配。（就像一个工作可以分配给一个仅限申请人）

现在我知道找到这个计数并不容易，而且是#P-hard 问题（来自链接：https ://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in -一般图）

但是这样做的残酷解决方案是什么？有人可以用一些代码或伪代码解释一下。

假设输入就像我们有 X 对显示 u 连接到 v

如果 N=2 和 X=4 并且对是 (1,1),(1,2),(2,3),(2,4)。

我有一个物种间的相互作用网络，第一行是捕食者身份，第一列是猎物身份。矩阵用 0 或 1 填充，表示存在或不存在交互。我想将此矩阵转换为具有两列的数据框，第一列包含捕食者的身份，第二列包含猎物的身份。因此，每一行将由不同的捕食者-猎物组合定义，代表一种独特的相互作用。这是它的样子：

非常感谢

瓦莱丽