3 ms·

I also hear that some people use graph isomorphism to compare files, do optical character recognition, and analyze social networks, but it seems highly probable

I also hear that some people use graph isomorphism to compare files, do optical character recognition, and analyze social networks, but it seems highly probable to me that GI is not the central workhorse (or even a main workhorse) in these fields. Can somebody in HN more familiar with this add a comment about this?

jules 11y ago
Maybe there is somebody who uses GI to do those things, but that is not a standard method and likely a bad idea. For comparing files the standard method is just a diff based on Levenshtein distance, and the standard methods for character recognition are various forms of machine learning (e.g. SVM, NN).
- deleted 11y ago
  [deleted]
- OJFord 11y ago
  Social networks sounds like a likely application though. Consider "Graph A is Alice's network of friends; B is Bob's. Do they know exactly and only the same people?" That might be slightly contrived. But it could be used to indicate how introverted a certain community is!
  - bmm6o 11y ago
    In your hypothetical case the vertices would be labeled by friends' names or ids. So you only have to check whether the obvious isomorphism applies i.e. that the graphs are equivalent as sets.
    - OJFord 11y ago
      Ah, yes that's true of course - I clearly wasn't thinking.. Well, then I can't even contrive an example! Still, it's interesting; I wish I had the background to understand it better.
CJefferson 11y ago
Graph Isomorphism is indeed not used much in these field. Subgraph isomorphism (and variants of it) are very useful, and surprisingly (well, suprising to me), the techniques for solving graph isomorphism and subgraph isomorphism are entirely different. On practical use of graph isomorphism is finding symmetries in programs -- (basically) build an AST, and then run graph isomorphism on that. Also, the algorithms used for graph isomorphism are used (with modification) to solve a large range of group theory problems, including group intersection, so this might help with a large range of other group theory problems.

jules 11y ago

Maybe there is somebody who uses GI to do those things, but that is not a standard method and likely a bad idea. For comparing files the standard method is just a diff based on Levenshtein distance, and the standard methods for character recognition are various forms of machine learning (e.g. SVM, NN).

deleted 11y ago
[deleted]
OJFord 11y ago
Social networks sounds like a likely application though. Consider "Graph A is Alice's network of friends; B is Bob's. Do they know exactly and only the same people?" That might be slightly contrived. But it could be used to indicate how introverted a certain community is!
- bmm6o 11y ago
  In your hypothetical case the vertices would be labeled by friends' names or ids. So you only have to check whether the obvious isomorphism applies i.e. that the graphs are equivalent as sets.
  - OJFord 11y ago
    Ah, yes that's true of course - I clearly wasn't thinking.. Well, then I can't even contrive an example! Still, it's interesting; I wish I had the background to understand it better.

CJefferson 11y ago

Graph Isomorphism is indeed not used much in these field. Subgraph isomorphism (and variants of it) are very useful, and surprisingly (well, suprising to me), the techniques for solving graph isomorphism and subgraph isomorphism are entirely different. On practical use of graph isomorphism is finding symmetries in programs -- (basically) build an AST, and then run graph isomorphism on that. Also, the algorithms used for graph isomorphism are used (with modification) to solve a large range of group theory problems, including group intersection, so this might help with a large range of other group theory problems.