# Graph matching & Levenshtein distance (p1)

*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

Posted on June 27, 2013, in Algorithms and tagged Graph matching, Levenshtein distance. Bookmark the permalink. 3 Comments.

Pingback: Recent Progress and Gromov-Hausdorff Convergence | Eventually Almost Everywhere

Pingback: Preferential Attachment Models | Eventually Almost Everywhere

Pingback: Mixing of the Noisy Voter Model | Eventually Almost Everywhere