问题标签 [clique]

我有一个关于 igraph::graphlet_basis 的可能太基本的问题我正在分析相对较小的加权图（大约 20-30 个节点，40-60 条边），我想在其中确定 k2-k5 graphlet 分布。据我了解，graphlet 与 clique 不同，不需要在它们之间连接所有节点。但是， igraph::graphlet_basis 函数专门搜索派系。有没有查找graphlet的功能？

例如，这些是 2 节点到 5 节点的 graphlet：

小图

我目前有一个解决子图同构的程序。如果存在同构子图，则返回 1，否则返回 0。

我正在尝试使用此实现来解决派系问题（图 G 是否包含 k 个顶点上的派系）。我已经坚持了一段时间，所以任何帮助表示赞赏。

给定一个无向图，我需要找到最大的集团。我要做的是首先找到它的大小（即有多少顶点/节点）。这样做时，我删除了不属于最大集团的所有节点（即，如果最大大小为 3，我将删除所有只有一个相邻节点的节点，因为它们不能成为这个更大集团的一部分）。

这是我的代码：

我正在通过 Udemy 课程的在线检查器提交，结果如下：

我一直在为我的硕士论文尝试在 Rust 中实现Bron-Kerbosch 算法。到目前为止一切正常，但是当我尝试从 a 更改为 aBTreeSet以HashSet进行性能比较时，行为变得完全随机（至少结果是这样）。

我找不到有关对结果有任何影响的节点顺序的任何信息，但是，更改为无序集合会破坏结果，因为算法似乎在回溯期间错过了一些分支。

操场

运行代码使用BTreeSet给出正确的结果。

更改Nodes类型以HashSet产生完全不同的结果。

我希望找到称为紊乱图的特殊类型凯莱图的所有最大团。我在 GAP 工作，我目前使用 GRAPE 包来建立以下内容：

我已经多次阅读 GRAPE 文档，但找不到生成所有最大派系的命令。在 Sage 中，可以调用 cliquer 命令 ( https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/cliquer.html )，它可以相当快速有效地找到所有最大 cliques (对于根据我的经验，订单 < 3000）。GAP中有这样的选择吗？

注意：我也尝试使用 YAGS 包来使用“CompletesOfGivenOrder(Cay,n)”命令，但我发现它非常慢。

我需要一些“已知集团规模图”数据集进行实验。是否有任何开源或网站，我可以在哪里找到它们？

g是一个 igraph 对象。我希望找到派系（mylist），然后将这个大列表对象转换为数据框对象。即一列带有派系编号，另一列带有该派系的成员。

但是，代码会产生错误：Error in as.data.frame.default(value, stringsAsFactors = FALSE) : cannot coerce class ‘"igraph.vs"’ to a data.frame

编辑：

运行vertex_attr_names(g)会产生“NodeID”（因此 NodeID 是节点属性）。

但是，我的g（igraph 对象）似乎没有将 NodeID 显示为属性。这是正常的吗？

数据文件链接： https ://drive.google.com/drive/folders/14eiJhW499lMM5BKaU4Qau-B7ieZCrSKx?usp=sharing

我有 27,000 个节点和 38,000 个派系，maximal.cliques()在 R中使用。

是否可以有比节点数更多的派系？为什么这么多节点属于超过 1 个 clique？

如何将每个节点限制为仅属于 R 中的 1 个集团？

我有一个断开的无向网络。我想识别并删除所有属于 cliques 的组件。我不想删除所有的派系，只是那些本身就是网络组成部分的派系。

我应该如何进行？

我实现了 BK 算法 ( https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm ) <- 在 C++ 中没有旋转版本，但没有按预期工作。代码是：

预期产出集团：ABC

AE

CBDF

ED

实际输出派系：ABC

AE

CBDF

CDF <- 这不应该存在

ED

一个相关的问题在这里：Bron Kerbosch algorithm in c++ 解决方案是使用 P 的副本（我正在这样做，虽然我不完全理解为什么需要它）。我测试它的图表是这样的：

注意： users 被定义为 a: map<string, vector<string>>，所以 users[v] 实际上是一个包含 v 所有邻居的向量。

完整的类实现： https ://pastebin.com/dRXrC0Rf

声明类后重现输出的代码： https ://pastebin.com/vV6ppunF