问题标签 [clique]

我想利用 Pregel/spark-pregel 实现来查找使用 Scala 的无向图的派系。任何建议或算法都将受到高度赞赏。

子图同构

我们有图 G_1=(V_1,E_1), G_2=(V_2,E_2)。

问题：图 G_1 是否同构于 G_2 的子图？

（即是否存在 G_2 的顶点子集 V ⊆ V_2 和 G_2 的边子集 E ⊆ E_2 使得 |V|=|V_1| 和 |E|=|E_1| 并且存在一对一G_1 的顶点在 G_2 的顶点 V 的子集上的一次匹配，f:V_1 -> V 使得 {u,v} ∈ E_1 <=> { f(u),f(v) } ∈ E)

• 证明问题子图同构属于 NP。
• 证明问题是 NP 完全的，将问题 Clique 简化为它。（提示：认为图 G_1 是完整的）

我尝试了以下方法：

• 非确定性图灵机首先“猜测”节点 V 的子集和 G_2 的边 E 的子集，然后验证 |V|=|V_1| 和 |E|=|E_1| 并且存在一一对应的 f: V_1 -> V 使得 {u,v} ∈ E_1 <=> { f(u), f(v) } ∈ E 。

由于存在 O(|V_2|^2) 对不同的顶点对，因此检查需要多项式时间。所以问题属于NP。

• 让 (G,k) 为团问题的任意实例，其中 k 是团的顶点数。

我们可以在多项式时间内构造一个子图同构问题的实例，如下所示： G_2 是 n 个顶点上的图。

G_1 是关于 k 个顶点的完整图，对于某些 k <= n。令 G=G_2。问题子图同构有一个解决方案，当且仅当存在 G_2 的具有 k 个顶点的完整子图，即，如果图 G 具有具有 k 个顶点的完整子图。

因此，如果问题 Clique 的初始实例有解，则子图同构问题的实例有解。

因此，子图同构问题是 NP 完全的。

你能告诉我它是否正确，或者我是否可以改进一些东西？

给定一个布尔值的二维数组，我想找到包含至少 2 列和至少 2 行的所有模式。这个问题有点接近于在图中找到派系。

在下面的示例中，绿色单元格代表“真”位，灰色单元格代表“假”。模式 1 包含第 1、3、4 和 5 列以及第 1 和第 2 行。模式 2 仅包含第 2 和 4 列以及第 2、3、4 行。

这背后的商业理念是在各种社交网络用户群体之间寻找相似性模式。在现实世界中，行数可以达到 3E7，列数可以达到 300。

除了蛮力匹配之外，无法真正找到解决方案。

请建议问题的正确名称，以便我可以阅读更多内容，或者建议一个优雅的解决方案。

我正在尝试从高维数据集中检测密集子空间。为此，我想使用 ELKI 库。但是 ELKI 库的文档和示例很少。

我尝试了以下 -

我给出了以下输入-

2,2
2,3
5,2
5,3
8,4

结果是——

我希望输出作为分组到子空间的输入数据点。可能是我选择了错误的值或以错误的方式设置参数。

请帮忙。提前致谢。

如何存储高维数据以计算子空间聚类算法（如 clique、enclus 等）中的密集单元。? 例如，我有一个点的 20 个维度，所以如果使用数组，我必须为其分配 20 个维度，这将耗尽内存。代码是用'C'编写的，所以请建议我可以用什么来存储高维点。

假设有一个黑匣子（/算法），它给了我一个图的集团。反正有没有从中找到派系的封面？

图片中给出了我想要找到的直观想法。我正在尝试找到黑匣子部分。如果需要进一步说明，请随意。我有一个想法，通过删除派系的边缘来更新图形。我不知道它会有多好。期待任何其他想法。

此外，如果您能给我提供任何关于近似团覆盖算法的良好参考，那将非常有帮助。

我有一个大图（100000 个节点），我想找到它的大小为 5 的派系。我使用这个命令来实现这个目标：

计算这个操作需要很多时间。似乎它首先尝试找到图的所有最大团，然后选择大小为 5 的团；我猜这是因为这两个命令之间的运行时间存在巨大差异，而它们都在做同样的工作：

我正在寻找一个命令，比如adjacent.triangles有效地找到大小为 5 的集团。

谢谢

所以我有一个有向图的邻接矩阵，我想在图中找到派系。我所做的是使邻接矩阵对称然后立方它；之后我查看对角线条目，如果它们是正数，则表示该条目的顶点在某个集团中。我想弄清楚的是如何区分不同的派系并知道哪些顶点进入哪个派系。

编辑：如果 P 连接到 Q，并且 Q 连接到 P，那么 P 和 Q 在一个集团中。

我是理论计算机的新手，我被要求做一个在多项式时间内工作的算法，让 K-CLIQUE 证明它属于 P。

我正在考虑一种算法，它采用 n 个顶点的图形，对于每个顶点，例如 S0，我检查它有多少个团，例如 (s1 , s2 , s5) ，然后检查 S1 是否有团s2, s5 然后我去 s2 并检查它是否与 s5 有一个集团。

但我觉得我的生活很复杂，对吧？

对算法有什么建议吗？我知道这很容易，也许有人会帮助我了解查找算法的工作原理。

赞赏

给定图表 G，我需要两条信息：

1. G中的团数。
2. 这些集团的相对规模。

例如：有 3 个大小为 3 的小组、10 个大小为 4 的小组、7 个大小为 5 的小组等。

我正在使用 Python，我知道库 networkx 中定义了许多函数。谁能帮我得到这些结果？