问题标签 [clique]

给定一个无向图 G = G(V, E)，如何在多项式时间内找到其中最大团的大小？知道边的数量，我可以设置最大集团大小的上限

https://cs.stackexchange.com/questions/11360/size-of-maximum-clique-given-a-fixed-amount-of-edges

，然后我可以从该上限向下迭代到 1。由于这个上限是 O(sqrt(|E|))，我想我可以检查 O(sqrt(|E|) * sqrt 中的最大集团大小(|E|) * sqrt(|E|)) 时间。

有没有更有效的方法来解决这个 NP 完全问题？

我有一个要解决的问题，我想实现一个方法，该方法采用一个集团并返回包含该集团的最大集团。我正在研究的方法是递归的，并使用回溯来根据集团定义接受或拒绝解决方案。我的问题是我不想使用 Bron-Kerbosch 算法，因为我只想将一个参数传递给该方法。这是我所做的伪代码：

你能帮我想想如何选择打破递归的条件吗？我不知道如何将下一个候选者的值保持到下一个循环而不将其传递给方法参数！

如何证明一个大小为 n 的团的任何最小顶点覆盖必须恰好有 n-1 个顶点？谢谢

是否有任何软件或算法描述可以让您在具有约 17000 个加权顶点和约 75% 密度的图中找到具有已知顶点数的最大团（大约）？我尝试使用 Cliquer，但它太慢了（让我几天才能得到结果）。

关于我的问题，以防万一 - 这是一个时间安排问题，我有 18 个时间段，每个时间段都可以由不同数量的替代方案填充。每个变量代表一个插槽的一个备选方案。因此，一个插槽的所有替代方案都是互斥的，并且不同插槽的一些替代方案是不兼容的。如果两个备选方案兼容，那么它们之间就有优势。权重代表备选方案的价值。

给定消除顺序和图的弦化，我需要一个很好的图树分解。

我的想法是获取图中的所有派系（我可以做到）并从根开始构建二叉树并根据派系共有的验证数来生成子级（即派系）。我想这样做，直到使用所有派系，因此，我有一棵树。问题是团可能有两个以上的顶点，所以我不能递归地为每个顶点运行，因为树可能不是二元的。

http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph

我正在用 python 进行实现，目前我有弦图、所有派系的列表和消除排序。想法和/或代码非常受欢迎！

我有一个网络，我想通过集团绑定，但我还没有完全弄清楚如何正确地做到这一点。我可以使用 k-cores 执行相同的过程，但不确定创建仅包含派系的图形的正确过程是什么。

我希望如果我展示使用该k_core函数查找子图的过程，有人可以帮助我更改我的过程以使用该clique函数查找子图。

首先，我创建一个图表，我将使用空手道俱乐部：

在 iPython 中绘图：

接下来，我找到 4 核内的所有边（有 4 个或更多边）：

将这些边添加到新图中：

绘制 4 核图：

关于如何做到这一点的任何想法，但不是使用 k 核来绑定网络，而是使用具有 4 个或更多顶点的团？

我想在一个中等大小但密集连接的图中找到所有派系，该图中有 369 个节点和 22,724 条边。Graph.cliques()首先我简单的通过python接口调用了igraph的方法：

它仍在运行，并且在 i7-4600U 内核上消耗了超过 3 小时的净 CPU 时间。因此，我开始关注其他可能性，并且我记得几年前我已经使用了一个很好的代码。它被称为 justTheCliques，可在此处获得：https ://github.com/aaronmcdaid/MaximalCliques 。描述说：

在边缘列表上运行 Bron-Kerbosch 算法

运行此算法会在几秒钟内在同一图表上给出结果：

我喜欢igraph，我只想知道，这背后的本质原因是什么？Igraph 使用不同的算法？结果应该是一样的吧？

我有一个这样的数据框：

现在，我使用库 igraph 使用以下代码在 R 中绘制此图：

现在，在运行此代码时，我得到了图形的图和形成最大集团的值。但是，如果我想要那个实际最大的集团的情节，我该怎么做？谢谢！

Real-world problem:

I have data on directors across many firms, but sometimes "John Smith, director of XYZ" and "John Smith, director of ABC" are the same person, sometimes they're not. Also "John J. Smith, director of XYZ" and "John Smith, director of ABC" might be the same person, or might not be. Often examination of additional information (e.g., comparison of biographical data on "John Smith, director of XYZ" and "John Smith, director of ABC") makes it possible to resolve whether two observations are the same person or not.

Conceptual version of the problem:

In that spirit, am collecting data that will identify matching pairs. For example, suppose I have the following matching pairs: {(a, b), (b, c), (c, d), (d, e), (f, g)}. I want to use the transitivity property of the relation "is the same person as" to generate "connected components" of {{a, b, c, d, e}, {f, g}}. That is {a, b, c, d, e} is one person and {f, g} is another. (An earlier version of the question referred to "cliques", which are apparently something else; this would explain why find_cliques in networkx was giving the "wrong" results (for my purposes).

The following Python code does the job. But I wonder: is there a better (less computationally costly) approach (e.g., using standard or available libraries)?

There are examples here and there that seem related (e.g., Cliques in python), but these are incomplete, so I am not sure what libraries they are referring to or how to set up my data to use them.

Sample Python 2 code:

This produces the desired output: [Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])].

Sample Python 3 code:

This produces [set(['a', 'c', 'b', 'e', 'd']), set(['g', 'f'])]):

我有一个由 150 万对元素组成的数组（由 ' ' 分隔）：

每对元素都是唯一的，元素是 15 到 20 个字符的字符串。

在我的管道中，此数组表示 [0]“element1 与 element2 相关”，[1]“element2 与 element3 相关”，...我想将所有相关元素聚集在一起并获得类似于以下内容的输出：

我想这个任务很简单，我可能错过了一个明显的方法来完成它，但是我没有找到一种快速的方法来聚集我的元素（即从几分钟到几个小时）。