对缺乏准确的术语表示歉意。不确定这是图形复制、粗化、覆盖还是完全不同的东西。这个问题的目标是（1）用正确的术语正式定义这个问题；(2) 确定它与什么图论问题同构；(3) 希望对问题使用现成的算法（或线性规划公式）。

问题是取一个未加权的二分图，识别左侧的节点，它们都与右侧有相同的连接，并生成一个新的图，将它们全部合并到一个节点中（并跟踪该数字组合为该节点的某种“质量”）。这是针对识别的统计问题，因此找到所有这些匹配项很重要。很高兴使用关联矩阵、图拉普拉斯算子、LP 公式等。

举个简单的例子，把左边标注为 1、2、3、4 的节点，右边标注为 A、B、C 的节点作为二分图，边分别为：

• 节点 1 -> A, B
• 节点 2 -> A, B
• 节点 3 -> A、B、C
• 节点 4 -> C 我们可以说所有节点的“质量”都为 1。

我们想要获取这张图，然后将节点 1 和 2 组合起来，因为它们连接到所有相同的事物。节点 3 不能合并，因为即使它连接到 A 和 B，它也连接到 C。

然后输出将摆脱节点 1 和 2，并创建一个新节点 5：

• 节点 5 -> A, B
• 节点 3 -> A、B、C
• 节点 4 -> C 现在我们有一个非平凡的“质量”分布；
• 节点 5：质量 2
• 节点 3：质量 1
• 节点 4：质量 1

要在图片中看到这一点，之前是：

之后是：

右边没有组合任何东西，也会有很多超过 2 的例子。

那么回到问题上来：

1. 描述这个项目的正确方式是什么？它与什么同构？
2. 有没有实现这个问题的算法（甚至软件）？LP 公式很好，如果有帮助，我们可以安装商业 LP 求解器等。

• 真实数据将有一个巨大且极其稀疏的网络（左右两侧都有数百万，但其中任何一个的连接数量都非常少。
• 为了了解稀疏性，左边可能有 100 万个节点，平均每个节点有 3 个连接，并且可能在算法运行后这些节点会崩溃到 25 万个节点。类似的东西。