Blog Archives

Graph matching & Levenshtein distance (p1)

J.K. Nguyen

Graphs are mathematical structures widely used to abstract and model relation dynamics in various systems. For example, the web can be represented by a graph in which nodes (vertices) correspond to webpages and edges (links) correspond to hyperlinks.

Definition: A graph $latex G$ is a set of vertex $latex V$ connected by edges  $latex E$ denoted as the ordered pair $latex G=(V,E)$.

A very important problem in graph theory is called graph matching which is measuring the similarity between graphs. This problem has a variety of applications such as social networks, image processing and bioinformatics.

How do we know if two graphs are the same? Well, you can try to take nodes of one graph and rearrange it to look like the other graph without adding or removing edges. If the two graphs end up looking identical (ignoring labels if any) then we say that the graphs are isomorphic. You can…

View original post 386 more words