Elektrotehniški vestnik 85(4): 162-168, 2018
Izvirni znanstveni (članek
Iskanje vzorčnih grafov s pomočjo iskalnega načrta ob prisotnosti avtomorfizmov
Luka Fürst, Uroš Cibej, Jurij Mihelič
Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Večna pot 113, 1000 Ljubljana, Slovenija E-pošta: luka.fuerst@fri.uni-lj.si
Povzetek. Problem podgrafnega izomorfizma, ki se ukvarja z iskanjem pojavitev podanega vzorčnega grafa v podanem gostiteljskem grafu, postaja zaradi vseprisotnosti velikih omrežij čedalje pomembnejši. Problem je NP-poln, na učinkovitost iskanja pa lahko negativno vplivajo tudi simetrije v vzorčnem grafu. V članku predstavljamo algoritem za reševanje problema podgrafnega izomorfizma s pomočjo iskalnega načrta, seznama navodil za sistematičen prebor vzorčnega grafa. Predstavljeni algoritem upošteva morebitne simetrije vzorčnega grafa in tako deluje učinkoviteje kot premočrtna različiča, ki zgolj na vse mogoče načine izpolnjuje navodila iskalnega načrta. S preizkušanjem algoritma na umetnih in realnih grafih smo empirično potrdili njegovo prednost pred naivnim pristopom in odgovorili na več raziskovalnih vprašanj.
Ključne besede: graf, podgrafni izomorfizem, avtomorfizem, simetrija, iskalni načrt, preiskovalna ekvivalenča
Searching for pattern graphs using a search plan in the presence of automorphisms
The subgraph isomorphism problem, the goal of which is to find the occurrences of a given pattern graph in a given host graph, is, owing to the pervasiveness of large networks, becoming increasingly important. However, the problem is NP-complete, and the search efficiency may also be negatively affected by symmetries in the pattern graph. In this paper, we present an algorithm for solving the subgraph isomorphism problem using a search plan, a sequence of instructions for a systematic traversal of the pattern graph. The presented algorithm pays attention to the symmetries in the pattern graph and thus performs more efficiently than its straightforward counterpart which merely follows the search plan instructions in all possible ways. By testing our algorithm on artificial and real-world graphs, we empirically confirm its advantage over the naive approach and answer several research questions.
1 Uvod
Veliki grafi igrajo v današnjem svetu čedalje pomembnejšo vlogo. Socialna omrežja z milijoni ali celo milijardami vozlišc (uporabnikov) in še precej vec povezavami (»prijateljstvi«) so nemara najbolj razvpit primer velikih grafov, seveda pa še zdalec niso edini. Pomislimo na transportna in energetska omrežja, omrežja e-poštnih sporocil, omrežja citiranja znanstvenih objav, lingvi-sticna omrežja itd. [1], [2], [3]
Zaradi obsega in pomembnosti velikih omrežij je nujno, da jih znamo ucinkovito preiskovati. Pogosto nas zanima prisotnost dolocenih podgrafov v podanem omrežju. Na primer, štetje trojic vzajemnih prijateljstev v socialnem omrežju lahko prevedemo na štetje pojavitev 3-ciklov v grafu omrežja. Žal pa je problem pod-
Prejet 12. junij, 2018 Odobren 23. avgust, 2018
grafnega izomorfizma (»ugotovi, ali podani gostiteljski graf H vsebuje pojavitev podanega vzorčnega grafa G«) NP-poln [4], pripadajoči preštevalni problem (»poišči vse pojavitve grafa G v grafu H«) pa #P-poln [5]. To pomeni, da najverjetneje ne obstaja algoritem, ki bi tovrstne probleme reševal v polinomskem času. Tudi najučinkovitejši znani algoritmi v najslabšem primeru potrebujejo eksponentno veliko časa v odvisnosti od velikosti vhoda, četudi se lahko v tipičnih realnih primerih kar dobro obnesejo [6], [7], [8].
Problem podgrafnega izomorfizma je mogoče reševati na različne načine [9]. Med bolj znanimi je Ullman-nov pristop [10], ki s pomočjo sestopanja gradi in popravlja dvojiško matriko, ki predstavlja vse mogoče monomorfizme* med vzorčnim in gostiteljskim grafom. V našem članku pa bomo primerke vzorčnih grafov iskali s pomočjo iskalnega nacrta [11]. Iskalni načrt je zaporedje navodil za sistematični prebor vozlišč in povezav vzorčnega grafa, zato ga lahko uporabimo za iskanje njegovih pojavitev v poljubnem gostiteljskem grafu. Prvo navodilo v zaporedju obišče eno od vozlišč vzorčnega grafa, vsako od nadaljnjih pa obišče bodisi še ne obiskanega soseda že obiskanega vozlišča (in obenem tudi povezavo med vozliščema) bodisi še ne obiskano povezavo med že obiskanima vozliščema. Algoritma za iskanje pojavitev grafov s pomočjo iskalnega načrta ni težko zasnovati, saj moramo zgolj po vrsti slediti iskalnemu načrtu in sestopiti, ko ne moremo več naprej ali pa ko želimo poiskati naslednjo pojavitev vzorčnega grafa.
Poseben izziv pri reševanju problema podgrafnega
* Monomorfizem je injektivna preslikava med množičo elementov vzorčnega grafa in množičo elementov gostiteljskega grafa, ki določa eno od pojavitev vzorčnega grafa v gostiteljskem.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV
163
izomorfizma so simetrije v obliki avtomorfizmov vzorčnega grafa. Če ima vzorčni graf k avtomorfizmov, bo iskalni postopek brez dodatnih ukrepov vsako njegovo pojavitev v gostiteljskem grafu odkril po k-krat. Tudi če gostiteljski graf ne vsebuje nobene pojavitve, bo iskalni algoritem zaradi avtomorfizmov odkril več kandidatnih delnih monomorfizmov, kot bi jih dejansko moral. Obstaja več pristopov za rokovanje s simetrijami [12], [13], [14], v tem članku pa si bomo pomagali s preiskovalno ekvivalenco vozlišč vzorčnega grafa [15], [16]. Če ima vzorčni graf simetrije, potem lahko na podlagi preiskovalne ekvivalenče postopek iskanja izboljšamo tako, da ta tvori manj odvečnih delnih in popolnih monomorfizmov med vzorčnim in gostiteljskim grafom in s tem porabi manj časa. Kot bomo videli, je na podlagi partičije množiče vozlišč grafa, ki jo določa preiskovalna ekvivalenča, mogoče neposredno definirati nabor omejitev, ki zmanjša redundančo iskalnega postopka.
V	pričujočem članku bomo pokazali, kako lahko algoritem za reševanje problema podgrafnega izomor-fizma, ki temelji na iskalnem načrtu, izboljšamo tako, da upošteva preiskovalno ekvivalenčo vzorčnega grafa. Poleg tega bomo predstavili rezultate eksperimentov, ki smo jih izvedli na umetnih in realnih grafih. Oboje lahko obravnavamo kot izvirni prispevek k znanosti.
V	razdelku 2 bomo definirali pojme, ki jih bomo uporabili pri opisu problema in iskalnega algoritma.
V	razdelku 3 bomo natančno formulirali problem. V razdelku 4 bomo predstavili naivni in izboljšani algoritem za reševanje problema podgrafnega izomorfizma s pomočjo iskalnega načrta. V razdelku 5 bomo rezultate eksperimentov prikazali in o njih razpravljali, z razdelkom 6 pa bomo članek zaključili.
2 Ozadje
Graf G je dvojiča (VG, EG), kjer je VG množiča vozlišč, EG C VG x VG pa množiča povezav. Kadar bo jasno (ali pa nepomembno), kateremu grafu pripada množiča vozlišč oziroma povezav, bomo namesto VG in EG pisali kar V in E .V članku se bomo brez pretirane izgube splošnosti omejili na neusmerjene grafe brez zank: E C {uv | u < v}.* Prav tako bomo predpostavili, da velja
V	= {1,2,..., |V|}.
Graf H je podgraf grafa G (H C G), če velja VH C VG in Eh C Eg. Homomorfizem med grafoma G in H je funkčija h: G ^ H, ki ohranja sosednosti: V(u, v) G EG : h(u) h(v) G EH. Injektivni homomorfizem se imenuje monomorfizem ali podgrafni izomorfizem. Če je h: G ^ H monomorfizem, potem je graf h(G) C H pojavitev grafa G v grafu H. Pojavitvi grafa G v grafu H, določeni z monomorfiz-moma hi: G ^ H in h2: G ^ H, obravnavamo kot istovetni (kot eno in isto pojavitev), če pokrivata
* Vrstni red krajišč povezave ni pomemben: zapisa uv in vu oba pomenita povezavo med vozliščema u in v.
isto množičo vozlišč in povezav grafa H, torej če velja {hi(v) | v G Vg} = {h2(v) | v G Vg} in {hi(e) | e G Eg} = {h2(e) | e G Eg}.
Bijektivni homomorfizem se imenuje izomorfizem. Grafa G in H sta izomorfna, če obstaja izomorfizem h: G ^ H. Izomorfizem v istem grafu (h: G ^ G) se imenuje avtomorfizem. Množičo vseh avtomorfizmov grafa G označimo z Aut(G).
Monomorfizem {1 ^ v1, 2 ^ v2, ..., |V| ^ v|V|} bomo zapisali kar kot viv2... vi v . Graf C4 (4-čikel), prikazan na sliki 2, ima 8 avtomorfizmov: Aut(C4) = {1234, 2341, 3412, 4123, 4321, 3214, 2143, 1432}. Eden od številnih monomorfizmov med grafom C4 in grafom na sliki 3 je {1 ^ 7, 2 ^ 11, 3 ^ 10, 4 ^ 6} oziroma 7 11 10 6.
Iskalni načrt [11], [17] je zaporedje navodil za prebor čelotnega vzorčnega grafa G, ki nam omogoča iskanje pojavitev grafa v poljubnem gostiteljskem grafu H. Prvo navodilo je vedno oblike [u]; razumemo ga kot »obišči poljubno vozlišče w v grafu H in ga priredi vozlišču u v grafu G (tj. vzpostavi h(u) = w)«. Vsako od nadaljnjih navodil pa ima bodisi obliko [u ^ v] (»prični v vozlišču, prirejenem vozlišču u, obišči enega od njegovih še ne obiskanih sosedov in izbranega soseda priredi vozlišču v) bodisi obliko [u?v] (»preveri, ali sta vozlišči grafa H, prirejeni vozliščema u in v, povezani«). Navodilo oblike [u ^ v] obišče novo vozlišče in povezavo, navodilo oblike [u ? v] pa samo novo povezavo. Na primer, eden od iskalnih načrtov za graf C4 se glasi ([1], [1 ^ 2], [2 ^ 3], [3 ^ 4], [1?4]>.
Če v gostiteljskem grafu izpolnimo iskalni načrt za podani vzorčni graf na vse mogoče načine (tj. v vsakem koraku preizkusimo vse veljavne možnosti), bomo zanesljivo našli vse pojavitve vzorčnega grafa v gostiteljskem. V tem smislu so vsi iskalni načrti za podani graf med seboj enakovredni. Kot bomo videli, pa niso nujno enakovredni po učinkovitosti iskanja.
Množiča A C Aut(G) pokriva množičo P = {v1, v2, ..., vk} C V (oznaka: cover(A,P)), če za vsako permutačijo a: P ^ P obstaja avtomorfizem a G A, tako da velja a(v1) = a(v1), a(v2) = a(v2), ..., a(vk) = a(vk). Na primer, množiča Aut(C4) pokriva množičo {1,3}, saj avtomorfizem 1234 zajema permutačijo {1 ^ 1, 3 ^ 3}, avtomorfizem 3214 pa permutačijo {1 ^ 3, 3 ^ 1}. Stabilizator množiče A C Aut(G) glede na množičo P C V je množiča vseh avtomorfizmov v A, ki fiksirajo vse elemente množiče P: Stab(A, P) = {a G A | Vv G P: a(v) = v}. Na primer, Stab(Aut(C4), {1, 3}) = {1234, 1432}.
Zaporedje P = (P1; P2,..., Ps> je urejena particija množiče V, če velja |J ®=1 Pj = V in Pj n P j = 0 za vse i = j. Urejena partičija (P1, P2,..., Ps> je preiskovalno ekvivalentna, če za vse i G {1,..., s} velja cover(Ai-1, Pj) in Aj = Stab(Ai-1, Pj), pri čemer je A0 = Aut(G). Na primer, pri grafu C4 je urejena partičija ({1, 3}, {2,4}> preiskovalno ekvivalentna. To velja tudi za partičijo ({1, 2}, {3}, {4}>, ne pa za partičijo
164
FURST, ČIBEJ, MIHELIČ
({1, 2}, {3,4}), saj množica Stab(Aut(G), {1, 2}) = {1234} ne pokriva množice {3,4}.
Množica V = {Pi, P2,..., Ps} je particija množice V, ce velja US=1 Pi = V in Pi n Pj = 0 za vse i = j. Particija {P^ P2,..., Ps} je preiskovalno ekvivalentna, ce obstaja permutacija a: {1,..., s} ^ {1,..., s}, tako daje urejena particija (PCT(i), PCT(2),..., PCT(S}) preiskovalno ekvivalentna.
Kot bomo pokazali v razdelku 4, lahko pri reševanju problema podgrafnega izomorfizma na podlagi preiskovalno ekvivalentne particije {P1, P2,..., Ps} vpeljemo omejitve, ki število odkritih monomorfizmov med vzorčnim in gostiteljskim grafom zmanjšajo za faktor F = |P11! |P2|! ... |Ps|!, zato med razlicnimi kandidatnimi preiskovalno ekvivalentnimi particijami izberemo optimalno — tisto, pri kateri je faktor (ocena) F najvecji. Pri grafu C4 je optimalna particija {{1, 3}, {2,4}}, pri grafu C6 (slika 2) pa particija {{1,3, 5}, {2}, {4}, {6}} z oceno 3! 1! 1! 1! = 6; alternativa {{1,3}, {2, 5}, {4}, {6}} je z oceno 2! 2! 1! 1! = 4 slabša. Oceno optimalne preiskovalno ekvivalentne particije grafa G bomo oznacili s F *(G).
3 Opredelitev problema
Vhod v problem, ki ga rešujemo v clanku, sestavljajo
•	vzorcni graf G,
•	gostiteljski graf H,
•	iskalni nacrt za graf G in
•	preiskovalno ekvivalentna particija grafa G, pricakovani izhod pa je seznam vseh pojavitev grafa G v grafu H, pri cemer ne zahtevamo, da se vsaka pojavitev izpiše samo po enkrat.
4 Naš pristop
Najprej pokažimo naslednjo trditev in njeno posledico:
Trditev 1. Naj bo (P1, P2,..., Ps) preiskovalno ekvivalentna urejena particija množice V, pri cemer je
Pi = {vi,1, Vi,2, ..., Vi,ki} in Vi,1 < Vi,2 < ... < Vi,ki za vse i G {1,..., s}. Naj bo HG pojavitev grafa G v grafu H. Potem obstaja izomorfizem h: G ^ HG, za katerega pri vseh i g {1,...,s} velja h(vi1) < h(vi,2) < .. . < h(vi,fc.).
Dokaz: Naj bo h0: G ^ HG poljuben izomorfizem in naj bodo a*: P1 ^ P1, ..., a*: Ps ^ Ps takšne permutacije, da za vse i G {1,...,s} velja ho(a*(vi,1)) < ho(a*(vi,2)) < ... < ho(ai(vi,fci)).Naj bo permutacija a*: V ^ V definirana kot al(vi,j) = a*(vi,j) za vse i G {1,..., s} in j G {1,..., ki}.
Naj bo a1 permutacija množice P^ a2 permutacija množice P2 itd. in naj A(a1, a2,..., ar) oznacuje množico avtomorfizmov a G Aut(G) z lastnostjo a(vi,j) = ai(vi,j) za vse i G {1,..., r} in j G {1,..., ki}. Ker po definiciji preiskovalne ekvivalence množica Aut(G) pokriva množico P^ je množica A(a1) neprazna za
pojubno permutacijo a1 množice P1. Ker množica Stab(Aut(G), P^ pokriva množico P2, je neprazna tudi množica A(a1,a2), in to za poljubni par permu-tacij a1 in a2. (Če razmislek nadaljujemo, ugotovimo, da za poljubno množico permutacij a1: P1 ^ P1, ..., as: Ps ^ Ps množica A(a1, a2,..., as) vsebuje vsaj en avtomorfizem. Vsak avtomorfizem iz množice A(a*, a*,..., a*) premeša vozlišca v vsaki posamezni množici P^ ..., Ps tako, da h = h0oa* postane izomor-fizem z iskano lastnostjo: po definiciji iz prejšnjega odstavka velja namrec h(vi,1) < h(vi,2) < ... < h(vi,ki) za vsak i G {1,..., s}.	■
Posledica 2. Pri uporabi preiskovalno ekvivalentne particije {P^ P2,..., Ps} je število izomorfizmov h: G ^ HG, ki izpolnjujejo pogoje iz trditve 1, enako
| Aut(G)| / F*(G).
Dokaz: Število vseh izomorfizmov G ^ HG je enako številu avtomorfizmov na grafu G. Vendar pa v vsaki množici |Pi|! izomorfizmov, ki v grafu HG zajamejo vseh |Pi|! permutacij slike množice Pi, le eden izpolnjuje pogoj h(vM) < h(vi,2) < ... < h(vi,fc.). Ker to velja za vse i G {1,...,s}, se število izomorfizmov zmanjša za faktor Fl (G) = P |! P |! ... |PS |!. ■
Iz trditve 1 neposredno sledi, da se lahko pri iskanju pojavitev vzorcnega grafa G v gostiteljskem grafu H omejimo samo na tiste (delne in popolne) monomor-fizme G ^ H, za katere veljajo navedene omejitve. Z drugimi besedami: ce vozlišci u in v z lastnostjo u < v pripadata istemu ekvivalencnemu razredu v preiskovalno ekvivalentni particiji grafa G, potem ohranimo (in razvijamo) zgolj tiste delne in popolne monomorfizme h: G ^ H, za katere velja h(u) < h(v), vse druge pa zavržemo.
Algoritem za iskanje pojavitev s pomocjo iskalnega nacrta je prikazan kot algoritem 1. Postopek se sproži s klicem procedure Izvrsi, ki sprejme vzorcni graf G, iskalni nacrt zanj (zaporedje navodil (D1, D2,..., Dr), pri cemer je navodilo D1 vedno oblike [v0]), preiskovalno ekvivalentno particijo (P) grafa G in gostiteljski graf H. Algoritem po korakih — z zaporednim izvrševanjem navodil iskalnega nacrta — gradi monomorfizem h: G ^ H. Navodilo [v0] seveda izpolnjujejo vsa vozlišca grafa H. Navodilo [v1 ^ v2] pa algoritem izpolni tako, da izbere enega od sosedov w2 vozlišca h(v1) v grafu H, ki v trenutnem poskusu iskanja pojavitve grafa G še ni bil obiskan in ki izpolnjuje pogoj
Vv G h-1(VH):(3P G P: {v,v2}C P)
(v < v2 ^^ h(v) < ^2),
(1)
pri cemer h-1(VH) oznacuje množico vseh vozlišc v G VG, za katera po trenutnem delnem monomorfizmu h že obstaja slika h(v) G VH .Ko algoritem izpolni vsa navodila iskalnega nacrta in tako zgradi popoln monomorfizem, izpiše pojavitev, ki jo doloca monomorfizem, nato pa sestopi, da poišce še druge monomorfizme.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV
165
Sestopimo tudi tedaj, ko nobeno vozlišče grafa H ne izpolnjuje trenutnega navodila oziroma pogoja (1).
Postopek poleg delnega monomorfizma h: G ^ H vzdržuje tudi množico Visited, ki vsebuje vsa vozlišča grafa H, ki smo jih pri gradnji tekočega monomorfizma že obiskali. Preslikava h: G ^ H je, kot vemo, mo-nomorfizem samo tedaj, ko se različna vozlišča grafa G preslikajo v različna vozlišča grafa H.
Množiča Neighbors(u) = {v G V | uv G E} vsebuje vse sosede vozlišča u. Spremenljivka i v pomožni proče-duri IzvrsiPom podaja zaporedno številko trenutnega navodila iskalnega načrta.
V razdelku 5 bomo Algoritem 1 primerjali z njegovo naivno različičo. Ta se od Algoritma 1 razlikuje le po funkčiji PreveriPE: function PreveriPE(G, P, h, v2, w2)
return true end function
Naivni algoritem preiskovalne ekvivalenče sploh ne upošteva in zgolj premočrtno na vse mogoče načine izpolnjuje navodila iskalnega načrta.
Oglejmo si razliko med delovanjem naivnega in izboljšanega algoritma na primeru iskanja pojavitev grafa C4 v grafu K4 (slika 2). Vse tri pojavitve so prikazane na sliki 1. Graf C4 ima 8 avtomorfizmov (| Aut(C4)|), očena njegove optimalne preiskovalno ekvivalentne par-tičije (F*(C4)) pa znaša 4. Zato naivni algoritem vsako pojavitev grafa C4 odkrije po 8-krat, izboljšani pa le po dvakrat (= | Aut(C4)|/F*(C4)). Na primer, za pojavitev, določeno z monomorfizmom 1324, bi naivni algoritem tvoril monomorfizme 1324, 3241, 2413, 4132, 4231, 2314, 3142 in 1423, izboljšani pa le monomorfizma 1324 in 3142, saj sta edina, ki izpolnjujeta zahtevi h(1) < h(3) in h(2) < h(4).
h = 1234 h = 1243 h = 1324 Slika 1: Vse pojavitve grafa C4 v grafu K4
5 Eksperimentalni rezultati in
razprava
S pomočjo eksperimentov smo poskušali empirično odgovoriti na naslednja raziskovalna vprašanja:
•	Kako se po učinkovitosti razlikujeta algoritem, ki upošteva preiskovalno ekvivalenčo vzorčnega grafa, in algoritem, ki zgolj premočrtno na vse mogoče načine izpolnjuje navodila iskalnega načrta?
•	Kako na delovanje algoritma vpliva očena preiskovalno ekvivalentne partičije in kako velikost vzorčnega grafa?
• Ali izbira drugačnega iskalnega načrta za isti vzorčni graf vpliva na učinkovitost algoritma?
Večino poskusov smo izvedli z vzorčnimi grafi, prikazanimi na sliki 2. Barve vozlišč označujejo posamezne ekvivalenčne razrede v optimalni preiskovalno ekvivalentni partičiji. Vozlišča iste barve pripadajo istemu ekvivalenčnemu razredu, neobarvana vozlišča pa vsak svojemu. Na primer, optimalna preiskovalno ekvivalentna partičija grafa Ce je {{1,3,5}, {2}, {4}, {6}}. Števili ob oznaki grafa (npr. (8 / 4) pri grafu C4) podajata število avtomorfizmov (| Aut(G)|) in očeno optimalne preiskovalno ekvivalentne partičije (F*(G)). Kot smo že povedali, bo naivni algoritem vsako pojavitev grafa odkril po | Aut(G)|-krat, izboljšani pa po (| Aut(G)| /F *(G))-krat.
V	nadaljevanju bomo z N označevali število pojavitev podanega vzorčnega grafa G v podanem gostiteljskem grafu H, s t0 oziroma t+ pa čas v milisekundah, ki ga za podani par grafov G in H potrebuje naivni oziroma izboljšani algoritem. Algoritma smo implementirali v programskem jeziku Č, poganjali pa na računalniku s 3,40-gigaherčnim 8-jedrnim pročesorjem Intel Čore i7-3770.
V	prvem nizu poskusov smo Algoritem 1 in njegovo naivno različičo preizkušali na umetnih gostiteljskih grafih, in sičer na grafih Mn z (n + 1)2 vozlišči in 2n(n + 1) povezavami (E = {v, v + 1 | v ^ 0 (mod (n + 1))} U {(v, v + n +1) | v < n(n + 1)}) in na grafih Kn z n vozlišči in n(n — 1) / 2 povezavami (E = {uv | u < v}). Graf M3 je prikazan na sliki 3.
Tabela 1 prikazuje rezultate izvajanja obeh algoritmov na vseh parih vzorčnih grafov in gostiteljskih grafov Mi00 in K15. Kot bi lahko pričakovali, razmerje med časom delovanja naivnega in izboljšanega algoritma narašča z naraščajočo očeno optimalne preiskovalno ekvivalentne partičije. Razlika je še posebej izrazita pri vzorčnih grafih Kn. Na primer, pri grafu K9 se število odkritih pojavitev z uporabo preiskovalne ekvivalenče zmanjša za faktor F*(K9) = 9! = 362 880, poraba časa pa za faktor, večji od 50000. Tudi v primerih, ko graf H ne vsebuje nobene pojavitve grafa G, je izboljšani algoritem hitrejši od naivnega, saj uporaba preiskovalne ekvivalenče omeji tudi število vzpostavljenih delnih, ne samo popolnih monomorfizmov.
Iz tabele 1 razberemo tudi to, da se razmerje med izvajalnim časom naivnega in izboljšanega algoritma pri večjih vzorčnih grafih približuje očeni optimalne preiskovalno ekvivalentne partičije za vzorčni graf. S povečevanjem vzorčnega grafa se namreč zmanjšuje časovni delež programske kode, ki je neodvisna od velikosti vzorčnega grafa in je skupna obema algoritmoma. Postopno približevanje čiljnemu razmerju pride še bolj do izraza, če algoritma poženemo na družini grafov z različno velikostjo, a enako očeno optimalne preiskovalno ekvivalentne partičije. Tabela 2 prikazuje rezultate iskanja grafa Ln v grafu M100 za n G {2,..., 14}. Vidimo, da se razmerje v porabi časa približuje vrednosti
166
FURST, ČIBEJ, MIHELIČ
Algoritem 1 Iskanje pojavitev grafa s pomočjo iskalnega načrta in preiskovalne ekvivalence
1: function Izvrsi(G, ([v0], D2,..., Dr), P, H)
2:	for all v G VG do
3:	h(v) := ± > to pomeni, da v (še) nima svoje slike v grafu H
4:	end for
5:	for all w0 G VH do
6:	h(v0) := w0 > izpolnimo prvo navodilo iskalnega načrta
7:	Visited := {W0}
8:	IZVRSIPOM(G, (D2,..., Dr), 2, P, H, h, Visited)
9:	end for 10: end function
11:
12: function IZVRSIPOM(G, (D2,..., Dr), i, P, H, h, Visited)
13:	if i = r then
14:	izpiši h(G) > izpolnili smo vsa navodila iskalnega nacrta
15:	else
16:	if Dj = [vi ^ v2] then
17:	for all w2 G Neighbors(h(v1)) do	> navodilo izpolnimo na vse mogoče nacine
18:	if w2 G Visited, A PREVERIPE(G, P, h, v2, w2) then
19:	h(v2) := W2
20:	Visited := Visited U {W2}
21:	IZVRSlPOM(G, (D2, . . . , Dr), i + 1, P, H, h, Visited)
22:	Visited := Visited \ {W2}
23:	h(v2) := ±
24:	end if
25:	end for
26:	else if Dj = [v1 ? v2] then
27:	if h(v1) h(v2) G then > preverimo obstoj povezave med že obiskanima vozliščema
28:	IZVRSlPOM(G, (D2, . . . , Dr), i +1, P, H, h, Visited)
29:	end if
30:	end if
31:	end if
32: end function
33:
34: function PreveriPE(G, P, h, v2, w2)
35:	for all v G VG do > preverimo, ali lahko v monomorfizem h dodamo preslikavo v2 ^ w2
36:	if h(v) = ±A3P G P: {v,v2}C P then
37:	if (v < v2 A h(v) > w2) V (v > v2 A h(v) < w2) then
38:	return false
39:	end if
40:	end if
41:	end for
42:	return true
43: end function
F *(L„) = 2.
Poskusi so pokazali, da iskalni načrt praviloma nima skoraj nikakršnega vpliva na delovanje algoritma, kljub temu pa neugodni primeri obstajajo. Vsi dosedanji poskusi so bili izvedeni z iskalnimi načrti, ki vozlišča vzorčnih grafov obiskujejo po vrsti od vozlišča 1 do vozlišča |V|. Pojavitve grafa Cn, denimo, odkrivamo z iskalnim načrtom Ni = ([1], [1 ^ 2], [2 ^ 3], ..., [9 ^ 10], [10 ^ 11], [11 ? 1]). V kombinačiji z optimalno preiskovalno ekvivalentno partičijo {{1, 2},
{3}, {4}, ..., {11}} je iskalni načrt Ni ugoden, saj moramo že pri izpolnjevanju drugega navodila upoštevati omejitev h(1) < h(2). To pomeni, da že zgodaj v postopku iskanja pojavitve zatremo nekatere odvečne delne monomorfizme. Iskalni načrt N2 = ([2], [2 ^ 3], [3 ^ 4], ..., [9 ^ 10], [10 ^ 11], [11 ^ 1], [1 ?2]) pa je v obravnavem primeru izrazito neugoden, saj omejitev h(1) < h(2) učinkuje šele pri izpolnjevanju predzadnjega navodila. Preden bo algoritem neperspektivni monomorfizem zavrgel, ga bo zgradil skoraj v čeloti.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV
167
Tabela 1: Rezultati na umetnih gostiteljskih grafih
H	G	N	to	t+
M100	¿4	178 596	31,0	19,5
	C4	10 000	20,3	14,0
	K4	0	7,1	6,1
	¿6	1 387104	244	136
	Ce	19 800	127	58
	K6	0	7,0	6,4
	¿9	28 273 662	5430	2920
	C9	0	2380	977
	K9	0	7,1	6,9
Ki5	¿4	16 380	5,4	2,9
	C4	4095	7,2	3,0
	K4	1365	10,1	0,75
	¿6	1 801 800	274	143
	Ce	300 300	361	61
	Ke	5005	660	2,54
	¿9	908 107 200	159000	84100
	C9	100 900 800	202000	34 200
	K9	5005	527000	10,3
G	N	to	t+	to /t+
¿2	20 200	5,78	4,98	1,16
¿3	59 998	12,1	9,84	1,23
¿4	178 596	31,5	20,0	1,58
¿5	492 006	86,9	53,2	1,63
¿6	1 387 104	249	139	1,79
¿7	3 780 626	700	395	1,77
¿8	10 455 084	1970	1080	1,82
¿9	28 273 662	5430	2980	1,82
¿10	77 233 024	15 400	8230	1,87
¿11	207 943 998	42 400	22 700	1,87
¿12	563 572 700	118 000	63000	1,87
¿13	1512 373 042	334 000	176000	1,90
¿14	4077 286 312	919 000	483000	1,90
algoritmov na gostiteljskih grafih, ki izvirajo iz realnega sveta. Algoritma smo preizkusili na šestih grafih iz baz KONECT* (grafi Les Misérables, US Power Grid, David Copperfield in Jazz Musicians) [1] in SNAPt (grafa ca-HepTh in ca-CondMat) [2]. Grafom smo odstranili morebitne oznake, zanke in večkratne povezave med istim parom vozlišč, morebitne usmerjene povezave pa smo spremenili v neusmerjene. Nato smo v vsakem od grafov z naivnim in izboljšanim algoritmom našteli vse pojavitve grafov L4, C4 in K4 in dobili rezultate, zbrane v tabeli 4. Tudi tukaj vidimo, da izboljšani algoritem v vseh primerih prekaša naivnega, razmerje v porabi časa pa je marsikje blizu |F*(G)|. Ni presenetljivo, da na porabo časa bolj kot sama velikost gostiteljskega grafa vpliva razmerje med številom povezav in vozlišč. Večje povprečno število povezav na vozlišče na splošno pomeni tudi več pojavitev vzorčnega grafa.
Tabela 4: Rezultati na realnih gostiteljskih grafih
Tabela 2: Iskanje pojavitev grafa Ln v grafu M100 za različne vrednosti n
H	G	N	t0	t+
Les Misérables	¿4	26 784	5,9	2,0
|V | = 77	C4	2672	8,9	3,7
|E | = 254	K4	639	7,6	0,8
US Power Grid	¿4	52 556	13	8,5
|V | = 4941	C4	979	12	4,5
|E | = 6594	K4	90	6,6	2,4
David Copperfield ¿4		61254	15	4,5
|V | = 112	C4	2579	9,4	2,9
|E | = 425	K4	58	5,8	0,9
Jazz Musicians	¿4	3 850 915	480	260
|V | = 198	C4	406 441	870	250
|E | = 2742	K4	78 442	670	43
ca-HepTh	¿4	4 207 311	550	300
|V | = 9877	C4	239 081	630	200
|E | = 25 973	K4	65 592	360	36
ca-CondMat	¿4	50 543 325	6300	3500
|V | = 23133	C4	1 505 383	9900	2600
|E | = 93 439	K4	294 008	3700	270
Kot prikazujejo rezultati za iskanje pojavitev grafa Cii v grafu Kn (tabela 3), je razlika med iskalnima načrtoma Ni in N2 očitna. (Graf Ku vsebuje 1814400 pojavitev grafa Cn.)
Tabela 3: Iskanje pojavitev grafa C11 v grafu K11 s pomočjo ugodnega in neugodnega iskalnega načrta
Iskalni nacrt	to	t+
N1	8340	4210
N2	8460	6960
6 Sklep
Predstavili smo algoritem za reševanje problema pod-grafnega izomorfizma s pomočjo iskalnega načrta, ki upošteva avtomorfizme vzorčnega grafa in zato deluje učinkoviteje kot premočrtni iskalni algoritem. Algoritem s pomočjo poznavanja preiskovalno ekvivalentne partičije vzorčnega grafa omeji množičo obravnavanih monomorfizmov med vzorčnim in gostiteljskim grafom. Algoritem smo preizkusili na umetnih in realnih go-stiteljskih grafih. Proučili smo vpliv očene optimalne
Nazadnje predstavljamo še rezultate izvajanja obeh
*http://konect.uni-koblenz.de/ îhttp://snap.stanford.edu/data/
168
FURST, ČIBEJ, MIHELIČ
La (2 / 2)	L6 (2 / 2)
C4 (8 / 4)
Lg (2 / 2) Ce (12 / 6)
Cg (18 / 6)
K4 (24 / 24) K6 (720/720) Kg (362 880/362 880) Slika 2: Grafi, ki smo jih uporabljali v vecini poskusov
Slika 3: Graf Ms
preiskovalne ekvivalence, velikosti vzorčnega grafa in zaporedja navodil v iskalnem načrtu.
Preiskovalna ekvivalenca ne vodi nujno do optimalnega nabora omejitev. Na primer, pri 4-ciklu dobimo na podlagi optimalne preiskovalno ekvivalentne particije nabor omejitev {h(1) < h(3), h(2) < h(4)}, toda še večje prihranke nam ponuja nabor {h(1) < h(2) < h(4)}. Tega nabora ne moremo izpeljati iz preiskovalne ekvivalence, kljub temu pa se lahko prepričamo, da z njegovo uporabo ne izpustimo nobene pojavitve 4-cikla, ne glede na oštevilcenje vozlišc v gostiteljskem grafu. Ena od zamisli za nadaljnje delo je torej iskanje tovrstnih omejitev, zanimiva pa bi bila tudi študija vpliva omejitev na razlicne iskalne algoritme.
Literatura
[1]	J. Kunegis, "KONECT: the Koblenz network collection," Proceedings of the International Web Observatory Workshop, Rio de Janeiro, Brazilija, maj 2013, pp. 1343-1350, 2013.
[2]	J. Leskovec, A. Krevl, SNAP Datasets: Stanford large network dataset collection, http://snap.stanford.edu/data,
2014.
[3]	U. Cibej, "Graditev in analiza grafov slovenskih besed," Elektrotehniški vestnik, vol. 80, no. 4, pp. 141-146, 2013.
[4]	S. A. Cook, "The complexity of theorem-proving procedures," Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), Shaker Heights, Ohio, ZDA, maj 1971, pp. 151-158, 1971.
[5]	S. Arora, B. Barak, Computational complexity: a modern approach. Cambridge University Press, 2009.
[6]	L. P. Cordella, P. Foggia, C. Sansone, M. Vent, "A (sub)graph isomorphism algorithm for matching large graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, 2004.
[7]	Tomaž Hočevar, Janez Demšar, "A combinatorial approach to graphlet counting," Bioinformatics, vol. 30, no. 4, pp. 559-565,
2014.
[8]	U. Cibej, J. Mihelic, "Improvements to Ullmann's algorithm for the subgraph isomorphism problem," International Journal of Pattern Recognition and Artificial Intelligence, vol. 29, no. 7,
2015.
[9]	J. Lee, W.-S. Han, R. Kasperovics, J.-H. Lee, "An in-depth comparison of subgraph isomorphism algorithms in graph databases," Proceedings of the VLDB Endowment, vol. 6, no. 2, pp. 133-144, 2012.
[10]	J. R. Ullmann, "An Algorithm for Subgraph Isomorphism," Journal of the ACM, vol. 23, pp. 31-42, 1976.
[11]	J. Rekers, A. Schürr, "Defining and parsing visual languages with Layered Graph Grammars," Journal of Visual Languages and Computing, vol. 8, no. 1, pp. 27-55, 1997.
[12]	M. O. Albertson, K. L. Collins, "Symmetry breaking in graphs," The Electronic Journal of Combinatorics, vol. 3, no. 1, 1996.
[13]	M. G. Everett, S. P. Borgatti, "Computing regular equivalence: Practical and theoretical issues," Metodološki zvezki, vol. 17, 2002.
[14]	I. P. Gent, K. E. Petrie, J.-F. Puget, "Symmetry in constraint programming," Handbook of Constraint Programming, vol. 10, pp. 329-376, 2006.
[15]	J. Mihelic, L. Fürst, U. Cibej, "Exploratory equivalence in graphs: definition and algorithms," Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, FedCSIS 2014, Varšava, Poljska, september 2014, pp. 447-456, 2014.
[16]	L. Fürst, U. Cibej, J. Mihelic, "Maximum exploratory equivalence in trees," Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lodz, Poljska, september 2015, pp. 507-518, 2015.
[17]	L. Fürst, M. Mernik, V. Mahnic. Improving the graph grammar parser of Rekers and Schürr. IET Software, 5(2):246-261, 2011.
Luka Fürst je leta 2013 na Univerzi v Ljubljani doktoriral s področja računalništva in informatike. Zaposlen je kot asistent na Fakulteti za računalništvo in informatiko. Raziskovalno se ukvarja s sintaksno analizo in indukcijo grafnih gramatik, v novejšem času pa tudi z grafnimi algoritmi nasploh.
Uroš Cibej je leta 2007 doktoriral na Fakulteti za računalništvo in informatiko Univerze v Ljubljani iz podvajanja podatkov v porazdeljenih sistemih. Trenutno je asistent in raziskovalec na omenjeni fakulteti. Raziskovalno se ukvarja s porazdeljenimi sistemi, snovanjem in analizo algoritmov za kombinatorično optimizacijo (npr. za iskanje vzorcev v grafih), programskimi jeziki in simulacijami.
Jurij Mihelic deluje kot docent v okviru Laboratorija za Algorit-miko Fakultete za racunalništvo in informatiko Univerze v Ljubljani, kjer je tudi leta 2006 doktoriral iz racunalniških znanosti. Njegova raziskovalna podrocja zajemajo inženiring in optimizacijo algoritmov, kombinatoricno optimizacijo ter sistemsko programsko opremo in virtualizacijo.