NetworkX Make iteration list of combinations of edges

Question

I have a 180x180 adjacency matrix which I am trying to generate all plausible combinations to work with using NetworkX.

I want to sequentially delete parts of the graph and then determine the effect on global efficiency of the new edited graph.

A plausible set of combinations in this view are all sets of nodes which are contiguous with each other, and all possible combination of subgraphs from assuming they are contiguous with each other up to the subgraph.

The brute force approach of running all of the combinations is too slow and has a run time of about 21 hours for any deletion series more than 15. So we want to address this by only looking at combinations which are contiguous with each other.

Basically the code needs to do the following:

1. Import a csv containing a binary adjacency matrix where 1 implies physical continuity (in this case in the brain)
2. Import into networkx graph
3. Deterimine all sets of combinations which are at most path length of 1 away from each other ....in other words if two nodes or two node sets are greater than 1 apart at either end, then they get ignored
4. Generate a list of those sets of nodes for each plausible combination

Here is the basic problem

assume the physical space of a region of the brain includes several areas which roughly sit like this...assume these are irregular polygons tesselating a plane

1 2 3 4 5

6 7 8 9

10 11

we can make this into an adjacency matrix where 1 means the regions share a border and 0 means they are not physically bordering each other

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

basically that adjacency matrix represents parts of the brain which are next to each other......we want to go through and generate lists of groupings of these nodes which start with single nodes and work up to every possible combination of nodes with the caveat that we dont want the combinations to not be in physical contact with each other.....

so for example such a list would have 1,2,....11 also 1+2 and 7+8 etc eventually we would have 2+7+8 and 6+7+8+10 because all of those nodes touch each other and form a connected component 1-11 would not be allowed because they dont share a border neither would 4+5+10 because they dont touch

the reason this is important is that we are brain surgeons and we delete parts of graphs for a living...ie brain graphs....but you would never delete nodes which are not next to each other...we are trying to use graphs to define how far we can go in surgery....so we need to use python to generate all possible combinations of nodal deletions which make sense in the real world...the binary adjacency matrix represents reality in physical space

once i have a list of plausible combination of nodal deletions, i have code which takes a different pandas dataframe....zeros out the nodes and edges and then creates a networkx graph which we run efficiency metrics on.....i just need a way to determine all possible sets of contigious components so we dont run anatomically implausible combinations

the way i thought about solving this was using some kind of contigious components function in networkx, but i cannot find anyway to export all possible combinations of connected components from a graph

essentially the code would go something like this

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)

Note that we use one csv to determine the list and use that list on a different CSV

thanks in advance...this is an important problem you are helping to solve that will save lives

Answer 1

The correct naming of your connected component is complete subgraph (don't mess with the true connected components). Your problem is known as clique problem. networkx has several algorithms for solving this problem: networkx cliques

Your problem can be solved by this function: networkx.algorithms.clique.enumerate_all_cliques

Note, that this function returns all possible cliques, with 1 and 2 length too (i.e. every node and every edge) so you should filter 1-2 length cliques. For example, for your graph this function returns:

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

but if we will filter all useless cliques, we will get this:

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