python - NetworkX 制作边组合的迭代列表

Question

我有一个 180x180 的邻接矩阵，我正在尝试生成所有可能的组合以使用 NetworkX。

我想依次删除部分图，然后确定新编辑图对全局效率的影响。

此 View 中的合理组合集是所有彼此相邻的节点集，以及所有可能的子图组合，假设它们彼此相邻直至子图。

运行所有组合的蛮力方法太慢，对于任何超过 15 个的删除系列，运行时间约为 21 小时。因此我们希望通过仅查看彼此相邻的组合来解决这个问题.

基本上，代码需要执行以下操作:

1. 导入包含二进制邻接矩阵的 csv，其中 1 表示物理连续性(在本例中为大脑)
2. 导入networkx图
3. 确定所有路径长度最多为 1 的组合集......换句话说，如果两个节点或两个节点集在任一端的距离大于 1，则它们将被忽略
4. 为每个可能的组合生成这些节点集的列表

这是基本问题

假设大脑某个区域的物理空间包括几个大致像这样的区域......假设这些是镶嵌在一个平面上的不规则多边形

1 2 3 4 5

6 7 8 9

10 11

我们可以将其变成邻接矩阵，其中 1 表示区域共享边界，0 表示它们在物理上彼此不相邻

+--+---------------------------------+
|  | 1  2  3  4  5  6  7  8  9  10 11|
+--+---------------------------------+
|1 | 0  1  0  0  0  1  0  0  0  0  0 |
|2 | 1  0  1  0  0  0  1  1  0  0  0 |
|3 | 0  1  0  1  0  0  0  1  1  0  0 |
|4 | 0  0  1  0  1  0  0  0  1  0  0 |
|5 | 0  0  0  1  0  0  0  0  1  0  0 |
|6 | 1  0  0  0  0  0  1  0  0  1  0 |
|7 | 0  1  0  0  0  1  0  1  0  1  1 |
|8 | 0  1  1  0  0  0  1  0  1  0  1 |
|9 | 0  0  1  1  0  0  0  1  0  0  0 |
|10| 0  0  0  0  0  1  1  0  0  0  1 |
|11| 0  0  0  0  0  0  1  1  0  1  0 |
+--+---------------------------------+

基本上，邻接矩阵表示大脑中彼此相邻的部分......我们想要遍历并生成这些节点的分组列表，这些节点从单个节点开始，直到每个可能的组合需要注意的是我们不希望这些组合彼此之间没有物理接触的节点......

例如，这样的列表将有 1,2,....11还有 1+2 和 7+8 等等最终我们会得到 2+7+8 和 6+7+8+10 因为所有这些节点都相互接触并形成一个连通分量1-11 不被允许，因为它们不共享边界​​，4+5+10 也不被允许，因为它们不接触

这很重要的原因是我们是脑外科医生，我们以删除部分图表为生......即脑图......但你永远不会删除彼此不相邻的节点......我们正在尝试使用图形来定义我们在手术中能走多远……所以我们需要使用 python 生成所有可能的节点删除组合，这在现实世界中是有意义的……二元邻接矩阵代表物理中的现实空间

一旦我有了一个合理的节点删除组合列表，我就有了采用不同 pandas 数据框的代码……将节点和边清零，然后创建一个网络图，我们在上面运行效率指标…… .我只需要一种方法来确定所有可能的连续组件集，这样我们就不会运行解剖学上难以置信的组合

我想解决这个问题的方法是在 networkx 中使用某种连续的组件函数，但我无法找到从图中导出连接组件的所有可能组合

基本上代码会是这样的

boundary=pd.read_csv(adjacency.csv)
G=networkx.from_pandas_adjacency(boundary)
combo="something to iterate the graph g to create a list of all connected components"


for row in combo:
        values = row
        datasafe=pandas.read_csv("connections.csv", index_col=0)
        datasafe.loc[values, :] = 0

        datasafe[values] = 0

        g=networkx.from_pandas_adjacency(datasafe)
        h=networkx.from_pandas_adjacency(datasafe)
        le=local_efficiency(g)
        LE_list.append(le)
        ge=global_efficiency(h)
        GE_list.append(ge)
output=pandas.DataFrame(list(zip(combo, GE_list,LE_list)))
output.to_csv('multi.csv',index=None)

请注意，我们使用一个 csv 来确定列表并在不同的 CSV 上使用该列表

在此先感谢...这是您正在帮助解决的一个重要问题，它将挽救生命

Answer 1

连接组件的正确命名是complete subgraph (不要弄乱真正的 connected components )。您的问题称为 clique problem . networkx 有几种算法可以解决这个问题: networkx cliques

您的问题可以通过这个函数解决:networkx.algorithms.clique.enumerate_all_cliques

请注意，此函数返回所有可能的团，长度也为 1 和 2(即每个节点和每条边)，因此您应该过滤 1-2 长度的团。例如，对于您的图形，此函数返回:

list(nx.enumerate_all_cliques(G))

[[0],
 [1],
 [2],
 [3],
 [4],
 [5],
 [6],
 [7],
 [8],
 [9],
 [10],
 [0, 1],
 [0, 5],
 [1, 2],
 [1, 6],
 [1, 7],
 [2, 3],
 [2, 7],
 [2, 8],
 [3, 4],
 [3, 8],
 [4, 8],
 [5, 6],
 [5, 9],
 [6, 7],
 [6, 9],
 [6, 10],
 [7, 8],
 [7, 10],
 [9, 10],
 [1, 2, 7],
 [1, 6, 7],
 [2, 3, 8],
 [2, 7, 8],
 [3, 4, 8],
 [5, 6, 9],
 [6, 7, 10],
 [6, 9, 10]]

但是如果我们过滤掉所有无用的集团，我们会得到这个:

list(filter(lambda x: len(x) > 2, nx.enumerate_all_cliques(G)))

[[1, 2, 7],
 [1, 6, 7],
 [2, 3, 8],
 [2, 7, 8],
 [3, 4, 8],
 [5, 6, 9],
 [6, 7, 10],
 [6, 9, 10]]