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 :)

Exemple 1 enter image description here

Exemple 2 enter image description here

Exemple 3 enter image description here enter image description here

But this last criterion is really bonus at this point.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.