1
$\begingroup$

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.

$\endgroup$

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.