图中有向图的团

Question

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

Answer 1

对于此问题，您可以将问题的定向实例转换为无定向实例。考虑任意两个节点，如果它们之间只有一条有向边，则根据您的定义，它们不可能是集团的一部分。因此，如果没有对应的(v，u)，我们可以忽略任何边(u，v)。否则，如果我们同时有(v，u)和(u，v)，则它等价于无向边。

换句话说，我们创建一个无向图G‘，其边在u和v之间当且仅当存在有向边u -> v和v -> u，在G’中找到一个团应该会找到G中的等价团。