Vzdálenost úpravy grafu - Graph edit distance - Wikipedia

v matematika a počítačová věda, vzdálenost pro úpravy grafů (GED) je míra podobnosti (nebo odlišnost) mezi dvěma grafy Koncept vzdálenosti pro úpravy grafů byl poprvé matematicky formalizován Albertem Sanfeliuem a King-Sun Fu v roce 1983.^[1]Hlavní aplikace vzdálenosti pro úpravy grafů je v nepřesná shoda grafu, jako tolerantní k chybám rozpoznávání vzorů v strojové učení.^[2]

Vzdálenost úpravy grafu mezi dvěma grafy souvisí svzdálenost úpravy řetězce mezi struny S interpretací řetězců jako připojeno, směrované acyklické grafy z maximální stupeň jedna, klasická definice úpravy vzdálenosti jako Levenshteinova vzdálenost,^[3][4]Hammingova vzdálenost^[5]a Vzdálenost Jaro – Winkler lze interpretovat jako vzdálenosti úprav grafů mezi vhodně omezenými grafy. Podobně je vzdálenost pro úpravy grafů také zobecněním vzdálenost pro úpravy stromu mezizakořeněné stromy.^[6][7][8][9]

Formální definice a vlastnosti

Matematická definice vzdálenosti úprav grafu závisí na definicích grafů, nad kterými je definována, tj. Zda a jak jsou vrcholy a hrany grafu označeno a zda jsou hrany režie Obecně platí, že vzhledem k souboru operace úprav grafů (také známý jako základní operace grafu ), vzdálenost mezi dvěma grafy ${ displaystyle g_ {1}}$ a ${ displaystyle g_ {2}}$, psáno jako ${ displaystyle GED (g_ {1}, g_ {2})}$ lze definovat jako

${ displaystyle GED (g_ {1}, g_ {2}) = min _ {(e_ {1}, ..., e_ {k}) in { mathcal {P}} (g_ {1}, g_ {2})} sum _ {i = 1} ^ {k} c (e_ {i})}$

kde ${ displaystyle { mathcal {P}} (g_ {1}, g_ {2})}$ označuje sadu transformačních cest úprav ${ displaystyle g_ {1}}$ do (graf izomorfní na) ${ displaystyle g_ {2}}$ a ${ displaystyle c (e) geq 0}$ je cena každé operace úpravy grafu ${ displaystyle e}$.

Sada operátorů úpravy elementárních grafů obvykle zahrnuje:

vložení vrcholu zavést do grafu jeden nový označený vrchol.

odstranění vrcholu odstranit jeden (často odpojený) vrchol z grafu.

substituce vrcholů změnit štítek (nebo barvu) daného vrcholu.

vkládání hran zavést novou barevnou hranu mezi dvojicí vrcholů.

vymazání okraje k odstranění jedné hrany mezi dvojicí vrcholů.

náhrada hrany změnit štítek (nebo barvu) dané hrany.

Mezi další, ale méně běžné operátory, patří operace jako rozdělení hran který zavádí nový vrchol do hrany (také vytváří novou hranu) a kontrakce hran který eliminuje vrcholy stupně dva mezi hranami (stejné barvy). Ačkoli lze takové složité editační operátory definovat z hlediska více elementárních transformací, jejich použití umožňuje jemnější parametrizaci nákladové funkce ${ displaystyle c}$ když je provozovatel levnější než součet jeho složek.

Podrobná analýza operátorů úpravy elementárního grafu je uvedena v ^[10][11]

Byly předloženy některé metody automatického odvození těchto operátorů elementární úpravy grafů^{[12][13][14][15]}

Aplikace

Vzdálenost pro úpravy grafů vyhledá aplikace v rozpoznávání rukopisu,^[16] rozpoznávání otisků prstů^[17] a cheminformatika.^[18]

Algoritmy a složitost

Přesné algoritmy pro výpočet editační vzdálenosti grafu mezi dvojicí grafů obvykle transformují problém na jednu z možností nalezení minimální editační cesty mezi dvěma grafy. Výpočet optimální editační cesty je vržen jako hledání cesty hledat nebo problém s nejkratší cestou, často implementován jako * Vyhledávací algoritmus.

Kromě přesných algoritmů je také známa řada efektivních aproximačních algoritmů. Většina z nich má kubický výpočetní čas ^{[19][20][21][22][23]}

Kromě toho existuje algoritmus, který odvozuje aproximaci GED v lineárním čase ^[24]

Navzdory výše uvedeným algoritmům, které v praxi někdy fungují dobře, je obecně problém výpočtu vzdálenosti pro úpravy grafů NP-úplný^[25] (důkaz, který je k dispozici online, najdete v části 2 z Zeng a kol. ), a je dokonce těžké jej aproximovat (formálně je.) APX -tvrdý^[26]).

Reference