Efficient algorithm for counting subgraphs
I've searched related questions about listing subgraphs. However, they did not meet my requirement (*). (If I don't understand something, please tell me.)
Is there an efficient algorithm or tools for listing all "linked and untagged" subgraphs of an undirected parent graph.
In my case, the parent graph is the Internet topology, so the number of nodes can be large. And I would like to list all the related untagged templates (i.e. Subgraphs) of the parent graph.
(*) I searched for Efficiently find all related subgraphs and listing subgraphs , but both were targeting vertex-induced induced and full subgraphs respectively. But all I want is just connected unlabeled subgraphs.
source to share
A topic title that can be helpful is "frequent subtitle", which is one of its titles. There are various tools and algorithms in this area, although they may of course not do exactly what you want.
As you can see from the answers to the two questions in your links, the number of subgraphs of large graphs can be very large. Assuming you really want to list them and not just count them, this can be time consuming.
Edit : The OP pointed out that ONE large graph is introduced here, not a bunch of smaller ones, which won't work with standard mountain graph
I still think the general approach might work here. The input plot set for design is some subset of the subplots of your data plot. But this sub-set is what you want in the first place!
So let's say you choose the size of the subgraph you want (let's say 6 vertices), then you randomly choose the starting vertices in your parent (internet topology) and "grow" those seeds, discarding at each stage of growth those that are not match. Then repeat for different sizes of the subgraph.
This is of course a probabilistic algorithm, but it might give you some idea.
source to share