A gráf egy olyan adatszerkezet, amellyel egyedek közötti kapcsolatokat ábrázolhatunk. Matematikai értelemben egy gráf csúcsok egy V halmazából és a csúcsokat páronként összekötő élek egy E halmazából áll. Minden élt egy ( v i , v j ) csúcspárral jelölünk, ahol v i , v j ∈V . Minden v i csúcshoz hozzárendelhetünk egy l( v i ) címkét, amely az egyed nevét ábrázolja. Hasonlóképpen, minden ( v i , v j ) élhez is hozzárendelhetünk egy, a két egyed közötti kapcsolatot leíró l( v i , v j ) címkét. tab4:graph_examples. táblázatban különböző típusú gráfok csúcsait és éleit láthatjuk. Egy webgráfban például a csúcsok weboldalakhoz tartoznak, az élek pedig a weboldalak közötti hiperlinkeket reprezentálják.

7.4. Definíció

(Részgráf) Egy G'= (V',E') gráf a G=(V,E) gráf részgráfja, ha csúcsainak V' halmaza a V részhalmaza, éleinek E' halmaza pedig E részhalmaza. A részhalmaz kapcsolatot G' ⊆ S G módon jelöljük.

A 7.9. ábrán egy olyan gráf látható, amelynek 6 csúcsa és 11 éle van, továbbá a lehetséges részgráfjai közül egy. A 7.9. (b) ábrán látható részgráfba az eredeti gráf 6 csúcsa közül csak 4, és 11 éle közül is csak 4 tartozik bele.

7.5. Definíció

(Támogatottság) Ha adott gráfok egy G halmaza, akkor egy g részgráf támogatottságát az összes g -t részgráfként tartalmazó gráf hányadaként definiáljuk, azaz

s(g)= |{ G i |g ⊆ S G i ,   G i ∈G}| |G| . (7.2)

7.2. Példa.

Tekintsük a 7.10. ábrán látható G 1 , , G 5 gráfokat. Az ábra jobb felső sarkában ábrázolt g 1 gráf G 1 , G 3 , G 4 és G 5 részgráfja, így s( g 1 )=4/5=80% . Hasonlóképpen kiszámítható, hogy s( g 2 )=60% , mivel g 2 a G 1 , G 2 és G 3 gráfok részgráfja, míg s( g 3 )=40% , mert g 3 a G 1 és G 3 gráfok részgráfja.

Ebben a szakaszban a gyakori részgráf bányászat problémájának egy formális definícióját mutatjuk be, és ezen feladat összetettségét érzékeltetjük .

7.6. Definíció

(Gyakori részgráfok bányászata) Ha adott gráfok egy G halmaza és egy minsup támogatottsági küszöb, akkor a gyakori részgráfok bányászatának célja minden olyan g részgráf feltárása, melyre s(g)≥minsup . Bár ez a megfogalmazás általánosságban bármilyen gráftípusra alkalmazható, ebben a fejezetben az irányítatlan és összefüggő gráfokra helyezzük a hangsúlyt. A következőkben ezen gráfok definícióit adjuk meg:

A más típusú részgráfok (irányított vagy nem összefüggő) kezeléséhez szükséges módszerek kidolgozásának feladatát meghagyjuk az Olvasónak (lásd a 15. feladatot a 497. oldalon).

A gyakori részgráfok bányászata nagy számításigényű feladat, mert a keresési tér exponenciális. Hogy a feladat összetettségét érzékeltessük, tekintsünk egy d számú egyedet tartalmazó adatállományt. A gyakori elemhalmazok bányászatánál minden egyed egy elem, a feltárásra váró keresési tér mérete pedig 2 d , amely a generálható elemhalmaz jelöltek száma. Gyakori részgráfok bányászatánál minden egyed egy csúcs, amelyből legfeljebb d−1 él vezethet más csúcsokba. Ha feltételezzük, hogy a csúcsok címkéi egyediek, az összes lehetséges részgráf száma

∑ i=1 d ( d i )× 2 i(i−1)/2 ,

ahol d i azon lehetőségek száma, ahányféleképpen i számú csúcsot választhatunk ki egy részgráf kialakításához, 2 i(i−1)/2 pedig a csúcsok közötti élek maximális száma. A 7.8. táblázatban az elemhalmazok és részgráfok számát hasonlítjuk össze különböző d értékekre.

A részgráf jelöltek száma valójában sokkal kisebb, mert a 7.8. táblázatban megadott értékek tartalmazzák a nem összefüggő részgráfokat is. A nem összefüggő részgráfokat általában figyelmen kívül hagyjuk, mert kevésbé érdekesek, mint az összefüggő részgráfok.

Nyers erőn alapuló megközelítéssel ezt úgy tehetjük meg, hogy jelöltként generáljuk az összes összefüggő részgráfot, és kiszámítjuk azok támogatottságát. Tekintsük például a 7.11. (a) ábrán látható gráfokat. Feltéve, hogy a csúcsok címkéit az {a,b} halmazból, az élek címkéit pedig a {p,q} halmazból választjuk, az összefüggő, egy és három közötti számú csúcsból álló részgráfok listája a 7.11. (b) ábrának megfelelő lesz. A következő okokból sokkal nagyobb a részgráf jelöltek száma, mint az elemhalmaz jelöltek száma a hagyományos asszociációs szabály bányászatban:

Mivel a részgráf jelöltek száma igen nagy, egy nyers erőn alapuló algoritmus akár közepes méretű gráfon alkalmazva is összeomolhat.

Ebben a szakaszban azt vizsgáljuk, hogy hogyan fejleszthetünk ki egy Apriori-szerű algoritmust, amellyel gyakori részgráfokat tárhatunk fel.

Az adatok transzformálása

Egy lehetséges megközelítés minden gráf egy tranzakciószerű formátumba alakítása, hogy alkalmazhatóak legyenek az olyan meglévő algoritmusok, mint például az Apriori. A 7.12. ábra azt szemlélteti, hogy hogyan alakíthatjuk át gráfok egy halmazát a vele ekvivalens bevásárlókosár reprezentációba. Ebben az l(e) élcímkék és a hozzájuk tartozó (l( v i ) és l( v j )) csúcscímkék minden kombinációját egy ``termékre'' képezzük le. A ``tranzakció'' szélességét a gráfban lévő élek száma adja meg. Egyszerűsége ellenére ez a megközelítés csak akkor működik, ha egy gráfban minden élhez a csúcs- és élcímkék egy egyedi kombinációja tartozik. Más esetben a gráfok nem modellezhetőek teljes pontossággal ebben a reprezentációban.

A gyakori részgráf bányászati algoritmus általános felépítése

A következő lépésekből áll egy gyakori részgráfok bányászatára szolgáló Apriori-szerű algoritmus:

A szakasz további részében ezen lépések jellegzetes részleteit fejtjük ki.

A jelöltek generálása során két gyakori (k−1) -részgráfot egyesítünk, egy k -részgráf jelöltet létrehozva így. Az első kérdés azzal kapcsolatban merül fel, hogy hogyan definiáljuk k -t, a részgráfok méretét. A 7.11. ábrán látható példában k a gráf csúcsainak számát jelenti. Csúcsnövelésnek (vertex growing) nevezik azt a módszert, amelynél egy további csúcs hozzáadásával iteratív módon bővítjük a részgráfokat. Jelentheti azonban k a gráf éleinek számát is. Élnövelésnek (edge growing) nevezik azt a megközelítést, amelynél egy további élt adunk hozzá a meglévő részgráfokhoz.

Jelöltek többszöri generálásának elkerülése érdekében megadhatjuk továbbá azt a feltételt is az egyesítéshez, hogy a két (k−1) -részgráfnak rendelkeznie kell egy közös (k−2) -részgráffal. Ezt a közös (k−2) -részgráfot a gráfok magjának nevezzük. A továbbiakban röviden ismertetjük a jelöltek generálásának folyamatát a csúcsnöveléses és élnöveléses stratégiák esetére is.

Jelöltgenerálás csúcsnöveléssel

A csúcsnövelés az a folyamat, amely során úgy generálunk egy új jelöltet, hogy egy új csúcsot adunk hozzá egy meglévő gyakori részgráfhoz. A megközelítés leírása előtt tekintsük először a gráfok szomszédsági mátrix reprezentációját. A mátrix egy M(i,j) eleme vagy a v i és v j csúcsok közötti él címkéjét tartalmazza, vagy pedig a nullát, ha nincs közöttük él. A csúcsnöveléses megközelítést tekinthetjük úgy, mint egy k×k méretű szomszédsági mátrix létrehozását két (k−1)×(k−1) méretű szomszédsági mátrix kombinálásával, ahogy az a 7.13. ábrán látható. A G1 és G2 két olyan gráf, melyek szomszédsági mátrixai M(G1) és M(G2) . A gráfok magját az ábrán szaggatott vonal jelöli.

A következőekben a csúcsnöveléses jelöltgeneráló eljárást mutatjuk be.

Az így kapott gráfban egy vagy két éllel van több, mint az eredeti gráfban. A 7.13. ábrán G1 és G2 is négy csúcsot és négy élt tartalmaz. Az egyesítésükkel létrejövő G3 gráf öt csúcsot tartalmaz. A G3 éleinek száma attól függ, hogy a d és e csúcsok össze vannak-e kötve. Ha d és e nincsenek összekötve, akkor G3 -ban öt él van, a hozzájuk tartozó (d,e) mátrixelem pedig nulla. Ellenkező esetben viszont G3 -ban hat él van, a (d,e) -hez tartozó mátrixelem értéke pedig az újonnan létrehozott él címkéje. Mivel ez az élcímke ismeretlen, (d,e) -hez minden lehetséges élcímkét számba kell vennünk, így a részgráf jelöltek száma lényegesen megnő.

Jelöltgenerálás élnöveléssel

Élnövelés alkalmazásakor a jelöltek generálása során egy új élt szúrunk be egy meglévő gyakori részgráfba. A csúcsnöveléssel ellentétben az eredményül kapott részgráfban nem feltétlenül nagyobb a csúcsok száma az eredeti gráfhoz képest. A 7.14. ábrán két lehetséges részgráf jelölt látható, amelyeket G1 és G2 egyesítésével kaptunk az élnöveléses stratégiát alkalmazva. Az első részgráf jelölt, G3 , egy további csúcsot tartalmaz, míg a második részgráf jelöltben, G4 -ben, ugyanannyi csúcs van, mint az eredeti gráfokban. Az ábrán szaggatott vonal jelöli a gráfok magját.

A következőképpen foglalhatjuk össze az élnöveléses részgráf jelölt generáló eljárást.

Az egyesítendő gráfok számos topológiailag ekvivalens csúcsot tartalmazhatnak. A topológiailag ekvivalens csúcsok fogalmának szemléltetéséhez tekintsük a 7.15. ábrán látható gráfokat. A G1 gráf négy azonos, ``a'' címkéjű csúcsot tartalmaz. Ha a négy csúcs bármelyikéhez egy új élt kapcsolunk hozzá, akkor az így kapott gráfok azonosak lesznek. A G1 csúcsai így topológiailag ekvivalensek egymással.

A G2 gráfban két topológiailag ekvivalens csúcspár van, v 1 és v 4 , illetve v 2 és v 3 , annak ellenére, hogy a csúcsok és élek címkéi megegyeznek. Könnyen látható, hogy v 1 topológiailag nem ekvivalens v 2 -vel, mert nem egyezik meg a csúcsokban végződő élek száma. Így ha egy új élt kapcsolunk v 1 -hez, akkor nem ugyanazt a gráfot kapjuk, mint ha ugyanazt az élt v 2 -höz csatolnánk. Ugyanakkor a G3 gráfnak nincsenek topológiailag ekvivalens csúcsai. Noha a v 1 és v 4 csúcsoknak megegyezik a csúcscímkéje és ugyanannyi él végződik bennük, más gráfot kapunk akkor, ha v 1 -hez kapcsolunk egy új élt, mint akkor, ha ugyanazt az élt v 4 -hez kapcsolnánk.

A topológiailag ekvivalens csúcsok fogalmán keresztül könnyebben megérthető, hogy miért generálható több részgráf jelölt az élnövelés során. Tekintsük a 7.16. ábrán látható (k−1) -részgráfokat, G1 -et és G2 -t. A jelölés egyszerűsítése végett a két gráf k−2 közös élt tartalmazó magját egy téglalappal ábrázoljuk. A G1 fennmaradó, nem a magba tartozó élét egy az a és b csúcsokat összekötő, ``lengő'' éllel jelöljük. A G2 fennmaradó, nem a magba tartozó élét is hasonlóan, egy a c és d csúcsokat összekötő ``lengő'' éllel ábrázoljuk. Bár a G1 és G2 gráfok magjai megegyeznek, az is előfordulhat, hogy a és c topológiailag ekvivalensek, és az is, hogy nem. Ha a és c topológiailag ekvivalensek, akkor a=c módon jelöljük őket. A magon kívüli csúcsok esetén a b=d jelölést használjuk, ha a címkéik megegyeznek.

A következő hozzávetőleges szabályok segítségével határozhatjuk meg a jelöltgenerálás során kapott részgráf jelölteket:

Több részgráf generálható akkor is, ha egynél több mag társítható a két (k−1) -részgráfhoz, ahogy az a 7.18. ábrán is látható. A sötét színnel jelölt csúcsok azok, amelyek élei magot alkotnak az egyesítési művelet során. Minden egyes mag más részgráf jelöltekhez vezethet. Ha két gyakori (k−1) -részgráfot egyesítünk, akkor legfeljebb k−2 lehetséges mag létezhet elméletileg, melyek mindegyikét úgy kapjuk, hogy valamelyik gráfból eltávolítunk egy élt. Noha az élnöveléses módszer több részgráf jelöltet is előállíthat, a részgráf jelöltek száma általában még így is kisebb, mint a csúcsnöveléses stratégiával előállítottak száma.

Miután generáltuk a k -részgráf jelölteket, le kell nyesnünk azokat, amelyek (k−1) -részgráfjai nem gyakoriak. A nyesés lépését elvégezhetjük úgy, hogy a k -részgráf jelöltből egymás után eltávolítjuk az éleket, és ellenőrizzük, hogy az így kapott (k−1) -részgráfok gyakoriak-e. Ha nem, akkor az adott k -részgráfot elvethetjük.

A (k−1) -részgráfok gyakoriságának vizsgálatához össze kell hasonlítanunk azokat más gyakori (k−1) -részgráfokkal. Annak meghatározását, hogy két gráf topológiailag ekvivalens-e (vagy izomorf-e), gráfizomorfizmus problémának nevezzük. Hogy a gráfizomorfizmus probléma megoldásának nehézségét érzékeltessük, tekintsük a 7.19. ábrát. Bár a két gráf különbözőnek látszik, valójában izomorfak, mert kölcsönösen egyértelműen feleltethetők meg egymásnak a két gráf csúcsai.

A gráfizomorfizmus kezelése

A gráfizomorfizmus kezelésének egyik standard módszere, hogy mindkét gráfot egy egyedi sztring reprezentációra képezünk le, amelyet kódnak vagy kanonikus címkének nevezünk. A kanonikus címkék rendelkeznek azzal a tulajdonsággal, hogy ha két gráf izomorf, akkor kódjaik is megegyeznek. Ez a tulajdonság lehetővé teszi, hogy a kanonikus címkéik összehasonlításával ellenőrizzük gráfok izomorfizmusát.

Az első lépés egy gráf kanonikus címkéjének megszerkesztéséhez a gráf szomszédsági mátrix reprezentációjának előállítása. A 7.20. ábrán egy ilyen mátrixra láthatunk példát, amely a megadott gráfhoz tartozik. Elméletben egy gráfnak több szomszédsági mátrix reprezentációja is lehet, mert a csúcsokat a szomszédsági mátrixban többféleképpen is sorba rendezhetjük. A 7.20. ábrán látható példában az első sor és oszlop az a csúcshoz tartozik, melynek 3 éle van, a második sor és oszlop egy másik a csúcshoz tartozik, melynek 2 éle van, és így tovább. Ahhoz, hogy kinyerjük egy gráf összes szomszédsági mátrix reprezentációját, tekintenünk kell a mátrix sorainak (és a hozzájuk tartozó oszlopoknak) az összes lehetséges permutációját.

Matematikai értelemben minden permutáció a kezdeti szomszédsági mátrix és egy megfelelő permutációs mátrix szorzatához tartozik, mint ahogy a következő példa is mutatja.

7.3. Példa.

Tekintsük a következő mátrixot:

M=( 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ).

A következő permutációs mátrixot használhatjuk M első sorának (és oszlopának) és harmadik sorának (és oszlopának) cseréjére:

P 13 =( 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 ),

ahol P 13 -at úgy kapjuk, hogy megcseréljük az egységmátrix első és harmadik sorát. Az első és harmadik sor (és oszlop) megcseréléséhez a permutációs mátrixot megszorozzuk M -mel:

M'= P 13 T ×M× P 13 =( 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16 ).

Figyeljük meg, hogy ha jobbról szorozzuk M -et P 13 -mal, akkor M első és harmadik oszlopa cserélődik fel, míg ha balról szorozzuk M -et P 13 T -tal, akkor M első és harmadik sora. Ha mindhárom mátrixot összeszorozzuk, akkor az M' mátrixot kapjuk, amelynek az első és harmadik sora, illetve oszlopa cserélődik fel.

A második lépés a sztring reprezentáció meghatározása minden egyes szomszédsági mátrixhoz. Mivel a szomszédsági mátrix szimmetrikus, elég, ha a mátrix felső háromszög részére alapozva készítjük el a sztring reprezentációt. A 7.21. ábrán látható példában a kódot úgy kapjuk meg, hogy oszloponként összefűzzük a felső háromszögmátrix elemeit. Az utolsó lépésben összehasonlítjuk a gráf összes sztring reprezentációját, és kiválasztjuk közülük azt, amelyiknek a legkisebb (vagy a legnagyobb) a lexikografikus értéke.

Az előbb tárgyalt megközelítés költségesnek tűnhet, mivel a kanonikus címke megtalálásához meg kell vizsgálnunk a gráf összes lehetséges szomszédsági mátrixát, és mindnek ki kell számítanunk a sztring reprezentációját. Konkrétan, k! számú permutációt kell tekintenünk minden egyes k csúcsból álló gráfra. A feladat bonyolultságának csökkentésére kidolgozott módszerek közé tartozik a korábban kiszámított kanonikus címke gyorsítótárazása (így nem kell azt újra kiszámítanunk, amikor ugyanazon gráfon végezzük a izomorfizmus vizsgálatát), és a kanonikus címke meghatározásához szükséges permutációk számának csökkentése olyan további információk bevonásával, mint például a csúcsok címkéi és foka. Az utóbbi megközelítés túlmutat a könyv által tárgyalt témákon, de az érdeklődő Olvasó figyelmébe ajánljuk a fejezet végén található irodalmi megjegyzéseket.

A támogatottság kiszámítása is költséges művelet lehet, mert meg kell határoznunk minden részgráf jelöltet, amelyet a G∈G gráf tartalmaz. Ezt a műveletet például úgy gyorsíthatjuk fel, hogy egy listát tartunk fenn, amely az egyes gyakori (k−1) -részgráfokhoz tartozó gráfazonosítókat tartalmazza. Amikor két (k−1) -részgráf egyesítésével egy új k -részgráf jelöltet generálunk, a két gráfhoz tartozó azonosítólisták metszetét vesszük. Végül, a részgráfok izomorfizmusának vizsgálatát a metszetlistában lévő gráfokon végezzük el, hogy meghatározzuk, tartalmaznak-e egy adott részgráf jelöltet.