logo标签列表

NetworkX创建边的组合迭代列表

pythonnetworkx
3
我有一个180x180的邻接矩阵，我想生成所有可能的组合，在NetworkX中使用。 我想按顺序删除图的一部分，然后确定新编辑图对全局效率的影响。在此视图中的一个可行的组合是所有相互连续的节点集以及从假定它们彼此连续的子图开始的所有可能的组合。运行所有组合的暴力方法太慢了，并且对于任何删除系列的运行时间超过15个小时。因此，我们要通过仅查看彼此连续的组合来解决这个问题。 基本上代码需要执行以下操作：导入包含二进制邻接矩阵（其中1表示物理连续性）的CSV文件，将其导入到networkx graph中，确定最多只有1个路径长度互相连通的所有组合集......换句话说，如果两个节点或两个节点集在两端的距离大于1，则会被忽略，为每个可行的组合生成这些节点集的列表。这里是基本问题假设大脑区域的物理空间包括几个区域，大致如下...假设这些是不规则多边形，平铺一个平面我们可以将其转换成邻接矩阵，其中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图，我们对其运行效率指标...我只需要一种确定所有可能的连续组件集合的方法，以便我们不运行解剖学上不合理的组合。
我想解决这个问题的方法是使用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上使用该列表。
谢谢您的协助，这是一项重要的问题，您正在帮助解决，将拯救生命。
所以，您想要一个列出所有直接相连节点的列表？请提供您的数据和代码的最小示例。 - warped
请提供一个最小的示例，即一小段数据（输入）和期望的输出。同时请提供您代码中相关的部分。 - Mathieu
我编辑了问题，包括我们需要的示例。 - Michael Sughrue
1个回答
2
你的连通组件正确命名为完全子图（不要与真正的连通组件混淆）。你的问题被称为团问题。 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]]
如果你以后需要帮助，可以通过vurmux@gmail.com邮箱或Telegram中的t.me/vurmux联系我。我很乐意帮助你！ - vurmux
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接