Vzdálenost editace grafu

Vzdálenost editace grafu je koeficient podobnosti (nebo nepodobnosti) mezi dvěma grafy . Pojem editační vzdálenosti grafu poprvé matematicky zformulovali Alberto Sanfeliu a King-San Fu v roce 1983 [1] . Hlavní aplikace vzdálenosti editace grafu je v nepřesném porovnávání grafů , jako je robustní rozpoznávání vzorů ve strojovém učení [2] .

Vzdálenost úprav grafu mezi dvěma grafy souvisí se vzdáleností úprav mezi řádky . Při interpretaci propadů jako spojených orientovaných acyklických grafů s maximálním stupněm dva lze klasické definice editační vzdálenosti, jako je Levenshteinova vzdálenost [3] , Hammingova vzdálenost [4] a Jaro-Winklerova vzdálenost , interpretovat jako vzdálenosti editace grafu mezi vhodné grafy. Podobně vzdálenost úprav grafu je zobecněním vzdálenosti úprav stromu mezi zakořeněnými stromy [5] [6] [7] [8] .

Formální definice a vlastnosti

Matematická definice vzdálenosti editace grafu závisí na definici grafů, pro které je vzdálenost definována. Záleží například na tom, zda a jak jsou označeny vrcholy a hrany grafu a také na tom, zda je graf orientován . Obecně platí, že vzhledem k sadě operací úprav grafů (také známých jako elementární operace s grafy ), lze vzdálenost úpravy grafu mezi dvěma grafy a , zapsané jako , definovat jako

,

kde znamená množinu transformačních cest do ( izomorfní s grafem) a rovná se ceně každé editační operace .

Sada základních operací s grafy obvykle zahrnuje:

vložení vrcholu — do grafu se vloží jeden nový označený vrchol. odstranění vrcholu — jeden (často nesouvisející) vrchol je z grafu odstraněn. nahrazení vrcholu - změna označení (nebo barvy) daného vrcholu. vložení hrany — do grafu se mezi dvojici vrcholů vloží nová barevná hrana. odstranění hrany — odstranění jedné hrany mezi dvojicí vrcholů. substituce hrany - změna označení (nebo barvy) dané hrany.

Kromě toho, ale spíše výjimečně, operace jako rozdělení hrany , které vloží nový vrchol do hrany (výsledkem jsou dvě hrany), a zmenšení hrany , které odstraní vrchol stupně dva mezi hranami (stejné barvy). sloučení dvou hran, jsou zahrnuty v jednom. I když lze takto složité operace definovat z hlediska jednodušších transformací, jejich použití umožňuje lepší parametrizaci nákladové funkce , když je operátor levnější než součet jeho částí.

Aplikace

Vzdálenost editace grafu má aplikace v rozpoznávání rukopisu [9] , rozpoznávání otisků prstů [10] a chemoinformatiky [11] .

Algoritmy a složitost

Přesné algoritmy pro výpočet vzdálenosti editace grafu mezi párem grafů obvykle transformují problém na problém nalezení minimální transformační cesty mezi dvěma grafy. Výpočet optimální cesty úprav se redukuje na hledání cesty nebo problém s nejkratší cestou , často implementovaný jako vyhledávací algoritmus A* .

Kromě přesných algoritmů je známo mnoho účinných aproximačních algoritmů [12] [13] .

Ačkoli výše uvedené algoritmy někdy v praxi fungují dobře, obecně je problém výpočtu editační vzdálenosti grafu NP-úplný [14] (důkaz je k dispozici v sekci 2 na webových stránkách Zeng et al. ) a dokonce obtížné aproximovat (formálně je to APX -hard [15] ).

Poznámky

  1. ↑ Sanfeliu, Fu, 1983 , str. 353–363.
  2. ↑ Gao, Xiao, Tao, Li, 2010 , str. 113-129.
  3. ↑ Levenshtein, 1965 , s. 845–848.
  4. ↑ Hamming, 1950 , str. 147–160.
  5. ↑ Shasha and Zhang 1989 , str. 1245–1262.
  6. ↑ Zhang, 1996 , s. 205–222.
  7. ↑ Bille, 2005 , str. 22–34.
  8. ↑ Demaine, Mozes, Rossman, Weimann, 2010 , str. A2.
  9. ↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , str. 194–203.
  10. ↑ Neuhaus, Bunke, 2005 , s. 191–200.
  11. ↑ Birchall, Gillet, Harper, Pickett, 2006 , str. 557–586.
  12. ↑ Neuhaus, Bunke, 2007 .
  13. ↑ Riesen, 2016 .
  14. ↑ Garey, Johnson, 1979 .
  15. ↑ Lin, 1994 , str. 74–82.

Literatura