algorithm - 在邻接矩阵中找到一组彼此是单跳邻居的节点

Question

对于给定的具有N 个节点及其邻接矩阵的无向图，假设至少有一组n 个节点，其中每个成员节点都是一个-跳集合中其他人的邻居。 (n <<N)

在这种情况下，找到这样一组节点的算法是什么？

例如，这是a sample adjacency matrix (link: GitHub Gist)有 42 个节点。并且已知有一个集合，其中 3 个节点是彼此的单跳邻居。那么，集合的组成是什么？

我的最终目标是对大约 450 个节点执行此过程，以找到包含 9 个单跳邻居节点的集合。因此，我正在寻找一种可扩展且高效的解决方案。

Answer 1

图中彼此相邻的一组节点称为团，并且finding the largest clique in a graph, or indeed whether any clique of a specified size even exists in the graph , 是一个经典的 NP-hard 问题。

一些 NP-hard 问题，称为固定参数可处理 (FPT) 问题，即使对于大 n 也可以有效地解决，只要某些问题参数(除了大小)很小:这里明显的参数是最大的集团。不幸的是，关于此参数，Maximum Clique 不是 FPT，并且最著名的算法是 n 的指数。维基百科页面上提到了几个。当然，由于您已经知道存在给定大小的团，您可能会很幸运并通过试探法快速找到它。

请注意 maximum(最大可能)和 maximal(无法生长)派系之间的区别。