CODEWITHSUNDEEP
pythongraphnetworkx
user2983638
user2983638

Reputation: 941

Efficient way for finding all the complete subgraphs of a given graph (Python)?

Is there an efficient way for finding all the fully-connected components (i.e. the complete subgraphs) of a given (undirected) graph with networkx? For example, I have the following adjacency matrix (without self-loops):

    |0 1 1 0 0|
    |1 0 1 0 0|
G = |1 1 0 1 0|
    |0 0 1 0 1|
    |0 0 0 1 0|

which corresponds to the following graph enter image description here The code should return the following tuples of nodes:

(0,1), (1,2), (0,2), (3,4), (2,3), (0,1,2)

I know networkx has routines for finding cycles, strongly-connected components, etc, but I cannot find anything about fully-connected components. If it's not possible with networkx, it would also be fine with Numpy + Scipy. Many thanks in advance!

EDIT

This is what I did:

import networkx as nx
import itertools


def findsubsets(S, m):
    return set(itertools.combinations(S, m))



A = np.array([[0, 1, 1, 0, 0],
              [1, 0, 1, 0, 0],
              [1, 1, 0, 1, 0],
              [0, 0, 1, 0, 1],
              [0, 0, 0, 1, 0]])


G = nx.from_numpy_matrix(A)

M = np.sqrt(np.size(A))


for m in range(2, M+1):

    for a in findsubsets(range(0, M), m):

        if(nx.number_of_edges(G.subgraph(a)) == (m**2 - m)/2.):

            print nx.nodes(G.subgraph(a))

which basically finds all the possible mXm subgraphs of the given one, and then checks if they have the maximum (i.e. (m**2 - m)/2) number of connections. But I was wondering if there is a more efficient way to do that, because the performance of the function itertools.combinations is not very good for large graphs.

Upvotes: 5

Views: 7520

Answers (1)

user2983638
user2983638

Reputation: 941

Ok, I found it. It's simply list(nx.find_cliques(G)), just because I didn't know that in graph theory a clique is a fully connected subgraph.

EDIT

More precisely, list(nx.find_cliques(G)) finds the maximal cliques, therefore it's not what I need. I found a similar post at this link.

So the correct answer is to use list(nx.enumerate_all_cliques(G)). However, this function returns also cliques of size 1, which I don't like since I don't have self-loops in my graph. Therefore the final solution is to use the following line of code:

[s for s in nx.enumerate_all_cliques(G) if len(s) > 1]

Upvotes: 8

Related Questions