问题标签 [clique]

Google Pregel 论文中提到了半聚类算法。使用以下公式计算半集群的分数

在哪里

Ic 是所有内部边
的权重之和 Bc 是所有边界边的权重之和
Vc 是半簇中的顶点数
fb 是边界边得分因子（用户定义在 0 和 1 之间）

该算法非常简单，但我无法理解上述公式是如何得出的。请注意，分母是 Vc 个顶点之间可能的边数。

有人可以解释一下吗？

有谁知道解决集团覆盖问题的库或一些代码（最好是Java）？

我找到了一个 OCaml版本，但我想使用一些我可以更容易集成的东西。

我还找到了 Java代码和 C 代码来查找图中的最大团，但我不知道如何利用此代码找到团覆盖（例如，迭代删除最大团，直到没有节点留下不会产生最佳解决方案）。

我正在开发一个基于 R 中的追随者关系的 Twitter 网络。在这个网络中，我想确定每个人都可以在他或她的时间线中阅读彼此推文的最大派系的规模。因此我需要最大的.cliques。但是这个函数忽略了方向性。我知道它没有集成在 igraph 包中，但是有没有办法在有向网络中找到派系，每个节点都主动和被动地相互连接？

我试图解决一个基本的集团问题，但我坚持以下几点：

• what is is the minimum size of the largest clique in any graph with N nodes and M edges

• To Find the largest clique in a graph

请告诉我以上两种说法的区别。

关于派系问题（特别是 k 派系）的问题。如果存在这样的集团，是否有任何算法利用连通图的特性来找到给定大小的k集团？

对于一个大学项目，我正在尝试实现Bron–Kerbosch 算法，即在给定图中列出所有最大派系。

我正在尝试实现第一个算法（没有旋转），但我的代码在维基百科的示例中测试后并没有产生所有答案，到目前为止我的代码是：

为什么我只得到部分答案有什么帮助？

我有一个 netlogo 问题。我有一些与（无向）链接连接的节点的图形结构。我需要找出其中一个结构中最小的子图。基本上子图意味着哪些节点都相互连接。因此，如果我有 5 个节点的结构并且节点 1 连接到 2 和 3；节点 2 到 3、1 和 4；和节点 3 到 1、2 和 5 我需要检测节点 1、2 和 3 的子图，因为它们都是互连的。

有没有一种简单的方法可以做到这一点，或者它基本上在计算上是不可能的？

编辑：我发现如果我使用 netlogo 扩展 nw 我可以使用 nw:maximal-cliques 方法来计算我想要的。虽然现在我有另一个问题。我正在尝试以这种方式填写集团列表

lista-cliques 通常长度为 2，但第一个元素应该是 clique 的海龟列表，是这样的列表

当 guild = g 的海龟制作的图的长度约为 2-8 只海龟时，长度为 300。对 nw:maximal-cliques 的调用做得好吗？

关于我做错了什么的任何想法？

编辑2：我想出了如何通过这样做来修复列表的长度

现在该列表不是 300 个节点，而是等于图中具有 guild = g 的节点的节点数量。

这意味着

等于

这显然也是错误的，因为我可以看到节点仅连接到一个或两个节点的图形。我想我越来越近了，但我不知道为什么 nw:maximal-cliques 没有创建最大集团的列表，而是创建图表上所有节点的列表。

有任何想法吗？

谢谢

最大团问题（MC-problem）是一个经典的NP问题，我们可以使用branch-bound来有效地解决这个问题。最近，我尝试开发一种算法来找出图中具有最大边加权团的团，正如我们所知，最大边加权团问题（MEC-problem）。

我发现了一些关于这个问题的属性。首先，集团必须是不属于任何更大集团的最大集团。那么团的边之和必须是所有最大团中最大的。

然而，传统的 MC-problem 算法对 MEC-problem 是无效的。因此，我想找到一种有效的 MEC 问题算法，尤其是分支定界算法。

我的问题是这样的：

我有一个人列表，每个人都有一定数量的 Facebook 喜欢。我想将这些人分成 N 个组，这样，对于每个组，每个成员都至少分享一个喜欢（即这个组中的每个人都喜欢 Daft Punk）。小组的人数不能超过 3 或 4 人，我想尽量减少不在小组中的人数。（但是，如果这意味着我可以进一步减少无与伦比的人，我愿意打破固定大小的规则）

我被告知要查看垃圾箱包装和派系，但它们不太适合我的问题。

在搜索以前的问题时，我遇到了这个问题：根据属性将输入数据分类到集合中 类似这样的方法似乎可行，但我组中的每个成员都有多个值（喜欢的数组）。此外，我不确定它是否可以最大限度地减少被排除在外的人数。

先感谢您！

我有一个关于将 s-clique 转换为 s-独立集的算法类的作业问题。下面是代码，最底部的功能independent_set_decision(H,s)是我需要完成的。我难住了。