问题标签 [clique-problem]

我正在尝试解决集团问题。我正在使用 Bron Kerbosch Clique 算法，它很好地用 java 编写，一个聪明的实现可以在这里找到。然而，由于派系的硬度，它可能非常缓慢，

我想要做的是使用一组我知道它们是连接的初始顶点。然后调用方法。对于我的一生，我不确定我在这里做错了什么，结果不是派系。

注意：注释代码来自原始代码（上面链接）。

所以简而言之，我唯一的改变是在getAllMaximalCliques方法上。我不太确定递归调用方法在这里是如何工作的。

如果可以提供任何帮助或指导，我将不胜感激。

我想利用 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 完全的。

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

我正在寻找一种重新排序技术来将邻接矩阵的连接组件组合在一起。

例如，我用蓝色和绿色两组做了一个插图。最初，'1' 的条目分布在矩阵的行和列中。通过对行和列重新排序，所有“1”都可以位于矩阵的两个连续部分中，从而更清楚地显示蓝色和绿色分量。

我不记得这种重新排序技术叫什么了。我搜索了许多邻接矩阵、集团、排序和重新排序的组合。

我发现的最接近的热门歌曲是

1. symrcm将元素移近对角线，但不组成组。

2. 有没有办法重新排序矩阵的行和列以在 R 中创建一个密集的角落？它专注于删除完全空的行和列

请提供该技术的通用名称，以便我可以更有效地进行谷歌搜索，或者向我指出 Matlab 函数的方向。

首先，我想提一下，这是我的功课。但是，为了解决我的问题，我可以使用任何我想要的文献。

尽管我认为这个问题从它的名字就很清楚了，但我还是会给出描述：“对于给定的无向图 G 和给定的整数 k，G 是否包含大小为 k 的完全连通（团）子图或完全不连通子图（独立集）尺寸 k。”

我知道从3-SATtoCLIQUE和 from 3-SATto 的多项式归约INDEPENDENT-SET。（http://mlnotes.com/2013/04/29/npc.html）但是，我对此有疑问，因为我无法将这两种减少结合起来。我也尝试从CLIQUEto减少，CLIQUE-OR-INDEPENDENT-SET但没有多大成功。

所以我真的很感激任何提示！

提前致谢。

我正在处理约 200 个节点和约 3500 条边的图。我需要找到这张图的所有派系。使用 networkxenumerate_all_cliques()可以很好地处理最多 100 个节点的较小图，但对于较大的图，内存不足。

“然而，这种算法希望不会耗尽内存，因为它只会将候选子列表保留在内存中并不断删除用尽的子列表。” enumerate_all_cliques() 的源代码

为了节省内存，有没有办法返回所有长度为 k 的派系的生成器，而不是所有派系？

我正在尝试在 R 中重新创建 Biclique 社区方法 ( Lehmann, Schwartz, & Hansen, 2008 )，它依赖于 Ka,b biclique 的定义。下面的示例显示了两个相邻的 K2,2 bicliques - 第一个 clique 是 {A,B,1,2}，第二个 clique 是 {B,C,2,3}。我希望能够使用 R 识别这些集团，以便我可以将其应用于更广泛的数据集。

到目前为止，我已将我的尝试包含在 R 中，但我遇到了以下两个问题：

1. 如果我使用标准 walktrap.community 它识别社区但不允许集合 {B,2} 属于两个派系
2. 如果我使用更新的clique.community功能，这似乎无法识别派系或我不正确理解（或两者兼而有之）

示例代码：

我有一个图，它的节点相邻矩阵。问题是找到与“all to all”相邻的所有节点。例如（在图片中）结果必须是[1,2,3,7]所有这些节点连接在一起。对于任何类型的图表，我都需要获取所有“全部”节点集合的列表。如何解决？谢谢。

我有一个对称邻接矩阵，其对角线上的值为零。现在我正在寻找重新排序方法来显示社区，该社区将矩阵分为两个集团，分别具有 +1 和 -1 值。如果有人可以在这方面帮助我，我们将不胜感激。

例如：矩阵（10,10）

输出必须是：

零条目可被视为 1

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

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

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

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

赞赏