找到最大派系并删除节点？

Question

我正在尝试查找一组项目的最大派系。

目前我正在使用 python 的 networkx 库并使用 find_cliques() 函数来查找所有最大派系，如下所示：

import newtworkx as nx

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6]]

G.add_edges_from(E)
#G.edges()

lst = list(nx.find_cliques(G))
lst

Out [] : [[2, 1, 3, 4], [2, 5, 6]]

但我实际上期望的是找到最大团，然后删除最大团图中的节点，然后再次从上次删除后留下的节点中找到最大团。

对于上面的例子，我希望得到 [2, 1, 3, 4] 然后删除这些节点，所以只剩下 5 和 6，这将是另一个团 [5, 6] 。

更新

我们可以使用G.remove_node()，它会按预期删除节点以及所有相邻边。

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6], [3,5], [5,7]]
G.add_edges_from(E)

list1 = list(nx.find_cliques(G))
#list1   gives [[2, 3, 1, 4], [2, 3, 5], [2, 6, 5], [7, 5]]

n = nx.number_of_nodes(G)
#n

[G.remove_node(nd) for nd in list1[0]]
list2 = list(nx.find_cliques(G))
#list2    gives [[5, 6], [5, 7]]

[G.remove_node(nd) for nd in list2[0]]
list3 = list(nx.find_cliques(G))
#list3    gives [[7]]

但是每次删除节点时，都会找到新的最大团并将其存储在新列表中，依此类推。在 while 循环中怎么可能运行直到图 G 中没有剩余边，即节点数为 0 或 1。

Answer 1

您可以使用 G.remove_node 从图形中删除节点（和关联的边）。

如何删除第一个 clique 的所有节点：

lst = list(nx.find_cliques(G))
[G.remove_node(nd) for nd in lst[0]]

重复删除第一个团的节点，直到没有团为止：

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

请注意，这与在每个步骤中删除所有个位于 any 最大团 中的节点不同，即：

lst = list(nx.find_cliques(G))
while len(lst) > 0:

    # This flattens the list of cliques into one list. `set` reduces to unique values.
    flattened = set([nd for cl in lst for nd in cl])

    [G.remove_node(nd) for nd in flattened]
    lst = list(nx.find_cliques(G))

最后，如果您希望按照特定顺序删除派系（例如最大派系优先），您可以通过相应地排序 lst 来完成此操作：

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    lst.sort(key=len, reverse=True)       # Sort maximum clique to the front
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

编辑： 为了完整起见，以下是在删除派系之前如何存储派系（根据您的评论，@Ankie）：

out = []
lst = list(nx.find_cliques(G))
while len(lst) > 0:
    out.append(lst[0])
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

作为附加说明，应该指出这些操作基本上是 'destroy' 图 G。如果稍后再次需要该图并且需要很长时间来构建，那么处理该图的副本以保留原始图是有意义的。可以这样复制：

G2 = G.copy()

找到最大派系并删除节点？

Finding maximal cliques and removing nodes?

python

numpy

graph

clique

pandas