I would like to identify all subgraphs of maximal size (maximum number of nodes) that are recurrent in a single undirected, labeled, connected graph. I provide exemples of input and expected output below.
I'm a freshman to graph theory so the terminology may not be the most appropriate. Please correct me if you read between the lines.
- By labeled graph I mean the nodes are labeled and labels can be redundant.
- By connected graph I mean all nodes are connected.
- By undirected graph I mean edges are not oriented/directed.
- By all subgraphs of maximal size I am not sure if I mean all possible non-overlapping isomorphisms.
So I have a single graph that I know will contain some symmetries (it contains subgraphs that will be repeated N times in the graph). And I want to find the repeated patterns.
I understand this can be a (very) complex problem but the graphs I have to use will never contain more than 150-200 nodes, so that's already something.
I have to do this using python 3.x and I can use any libraries. I have tried some brute-force detection but it gets complicated quickly and I feel like I shall use some clustering, maybe with trees representations. Possibly it can be solved with the right functions from packages likes networkX, but I can't figure it out atm.
Also, in case there is a central node, I don't really care if it is included in multiple subgroups.
I can't tell you how grateful I already am for any insights you may provide :)
But this last criterion is really bonus at this point.