寻找最大派系和删除节点？ [英] Finding maximal cliques and removing nodes?

问题描述

目前，我正在使用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]。
$ b

更新

我们可以使用 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给出[[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给出[[5,6]，[5,7 ]] 
 
 [G.remove_node（nd）for for list2 [0]] 
 list3 = list（nx.find_cliques（G））
＃list3 give [[7 ]] 
  

但每次删除节点时，都会找到新的最大派系并将其存储在新列表中等等。它如何在while循环中运行，直到图G中没有剩余边，即节点数是0或1。

解决方案

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

如何删除第一集团的所有节点：$ b​​
$ b pre $ 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））
  

请注意，这与在任何 maximal集团中删除全部节点不同每一步，这将是：

  lst = list（nx.find_cliques（G））
而len（lst）> 0：
 
＃这会将派别列表变为一个列表。 `set`减少为唯一值。 
 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）＃将最大派系排序到前面
 [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））
  

作为附加说明，应该指出这些操作基本上是'销毁'图。如果稍后再次需要该图并需要很长时间才能构建，则可以在图的副本上工作，以便保留原始图。复制可以这样做：



  G2 = G.copy（）
  




I am trying to find maximal cliques for a set of items.

Currently I am using networkx library of python and using find_cliques() function to find all the maximal cliques as below:

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]]

But what I am actually expecting is to find maximal cliques and then remove the nodes which were in the maximal clique graph, and then again find maximal clique out of the nodes left after previous removal.

For the above example, I am expecting to get [2, 1, 3, 4] and then remove these nodes, so only 5 and 6 would be left, which will be another clique [5, 6] .

Update

We can use G.remove_node(), it removes the node as well as all the adjacent edges as expected.

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]]

But every time the nodes are removed, new maximal cliques are found and stored in a new list and so on. How can it be run in the while loop until there is no edge left in graph G i.e number of nodes is 0 or 1.

解决方案

You can use G.remove_node to remove the nodes (and the associated edges) from your graph.

How to remove all nodes of the first clique:

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

To repeatedly remove the nodes of the first clique, until no cliques are left:

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))

Note that this is not the same as removing all nodes that are in any maximal clique at each step, which would be:

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))

Finally, if there is a certain order in which you would like to remove cliques (e.g. the maximum clique first), you could do this by sorting lst accordingly:

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))

Edit: for completeness sake, here's how one could store the cliques before deleting them (as per your comment, @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))

As an additional note it should be pointed out that these operations basically 'destroy' graph G. If the graph is needed again later on and takes a long time to construct, it makes sense to work on a copy of the graph so that the original is preserved. A copy can be made like this:

G2 = G.copy()

这篇关于寻找最大派系和删除节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！