The Data Mining Forum                             open-source data mining software data science journal data mining conferences high utility mining workshop
This forum is about data mining, data science and big data: algorithms, source code, datasets, implementations, optimizations, etc. You are welcome to post call for papers, data mining job ads, link to source code of data mining algorithms or anything else related to data mining. The forum is hosted by P. Fournier-Viger. No registration is required to use this forum!.  
difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 20, 2018 09:14PM

Hello,

Does any one know the difference between graph isomorphism and subgraph isomorphism problems? and which one is used in frequent subgraph mining?

Regards,
Maya

Options: ReplyQuote
Re: difference between graph isomorphism and subgraph isomorphism
Date: June 20, 2018 09:54PM

Those are mostly the same thing.

In simple words, two graphs are isomorphic if we map the edges and vertices of one graph to the other and they are equivalent.

Subgraph isomorphim checking is the same thing. But since you add the word "subgraph" it means that you are comparing subgraphs of a graph to check if these subgraphs are equivalent.

Yes, the idea of graph isomorphism is used in frequent subgraph mining to detect if equivalent graphs are found more than once, and eliminate these redundant graphs. And since a pattern in frequent subgraph mining is a subgraph, then you can say that it is subgraph isormorphism checking.



Edited 2 time(s). Last edit at 06/20/2018 09:57PM by webmasterphilfv.

Options: ReplyQuote
Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 23, 2018 01:21AM

Thanks a lot for your clarification.

Regards,
Maya

Options: ReplyQuote
Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 23, 2018 01:25AM

another question!

in two isomorphic graphs,should the mapped nodes and edges have the same names or not necessary? or the should have the same shape only?

Options: ReplyQuote
Re: difference between graph isomorphism and subgraph isomorphism
Date: June 23, 2018 02:25AM

In frequent subgraph mining, you typically have edges and vertices that have names. For example, you could have a graph about a water molecule, and you would have two nodes that have the same label "Hydrogen" and one node with the label "Oxygen"

Hydrogen ---- Oxygen ----- Hydrogen

Now, when you check if two graphs are isomorphic, yes, you need to check that the structure match but also the names (labels). And if you have label on the edges, you also need to check the labels on the edges.

Options: ReplyQuote
Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 25, 2018 08:05AM

Thanks a lot for your reply.

Options: ReplyQuote


This forum is powered by Phorum and provided by P. Fournier-Viger (© 2012).
Terms of use.