STRUKTURÁLIS DEANONIMIZÁCIÓS ALGORITMUSOK ELEMZÉSE ÉS FEJLESZTÉSE

Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Hálózati Rendszerek és Szolgáltatások Tanszék

Simon Benedek

STRUKTURÁLIS DEANONIMIZÁCIÓS ALGORITMUSOK ELEMZÉSE ÉS FEJLESZTÉSE

KONZULENS

Gulyás Gábor György BUDAPEST, 2015

Tartalomjegyzék Összefoglaló ..................................................................................................................... 6 Abstract............................................................................................................................ 7 1 Bevezetés ....................................................................................................................... 8 2 Irodalomkutatás ......................................................................................................... 11 2.1 A Narayanan algoritmus ....................................................................................... 12 2.1.1 A terjedési fázis működése ............................................................................ 13 2.1.2 A vizsgálat módja és eredmények ................................................................. 15 2.2 A Seed-and-Grow algoritmus ............................................................................... 17 2.2.1 Az algoritmus működése ............................................................................... 17 2.2.2 A vizsgálat módja és eredmények ................................................................. 19 2.3 Bayes döntésen alapuló algoritmus ....................................................................... 21 2.3.1 Az algoritmus működése ............................................................................... 21 2.3.2 A vizsgálat módja és eredmények ................................................................. 22 2.4 Bringmann algoritmus: ......................................................................................... 23 2.4.1 Közösségi hálók modellezése ........................................................................ 23 2.4.2 Az algoritmus működése ............................................................................... 24 2.4.3 A vizsgálat módja és eredmények ................................................................. 25 2.5 A state-of-the-art algoritmus kiválasztása ............................................................ 26 3 Vizsgálati keretrendszer ............................................................................................ 28 3.1 Régi keretrendszer, mátrixos leírásmód ................................................................ 28 3.2 Java alapú keretrendszer ....................................................................................... 30 4 A mérések módszertana ............................................................................................ 34 4.1 A támadó eredményének mérése .......................................................................... 34 4.2 Mérések beállításai ............................................................................................... 35 4.2.1 Perturbáció erősségének változtatása............................................................. 35 4.2.2 Deanonimizációs paraméterek beállítása ....................................................... 36 4.2.3 Különböző méretű és típusú seed hatásának vizsgálata................................. 36 4.2.4 Futási idő mérése ........................................................................................... 36 5 Grasshopper: Narayanan algoritmus fejlesztése .................................................... 38 5.1 Fejlesztési célok .................................................................................................... 38 5.2 A fejlesztés alapgondolata .................................................................................... 38

5.3 Súlyozásos helyettesítés ........................................................................................ 39 5.4 A Grasshopper összehasonlítása a state-of-the-art algoritmussal ......................... 42 5.4.1 Perturbáció erősségének változtatása............................................................. 42 5.4.2 A θ paraméter vizsgálata ................................................................................ 44 5.4.3 Különböző méretű és típusú seed hatásának vizsgálata................................. 46 5.4.4 Stabilitási tartományok vizsgálata ................................................................. 50 5.4.5 Futási idő mérése ........................................................................................... 51 6 A Bumblebee algoritmus ........................................................................................... 54 6.1 Elfedési jelenségek bemutatása ............................................................................ 54 6.2 Az algoritmus működése, új normalizálási eljárás ............................................... 56 6.3

A

Bumblebee

összehasonlítása

a

state-of-the-art

algoritmussal

és

a

Grasshopperrel ............................................................................................................ 58 6.3.1 A δ paraméter beállítása................................................................................. 58 6.3.2 Perturbáció erőssége szerinti mérések ........................................................... 60 6.3.3 A θ paraméter vizsgálata ................................................................................ 64 6.3.4 Különböző méretű és típusú seed hatásának vizsgálata................................. 66 6.3.5 Futási idő mérése ........................................................................................... 68 7 Összefoglalás............................................................................................................... 70 Irodalomjegyzék............................................................................................................ 72 Függelék ......................................................................................................................... 74

HALLGATÓI NYILATKOZAT Alulírott Simon Benedek, szigorló hallgató kijelentem, hogy ezt a diplomatervet meg nem engedett segítség nélkül, saját magam készítettem, csak a megadott forrásokat (szakirodalom, eszközök stb.) használtam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben, de átfogalmazva más forrásból átvettem, egyértelműen, a forrás megadásával megjelöltem. Hozzájárulok, hogy a jelen munkám alapadatait (szerző(k), cím, angol és magyar nyelvű tartalmi kivonat, készítés éve, konzulens(ek) neve) a BME VIK nyilvánosan hozzáférhető elektronikus formában, a munka teljes szövegét pedig az egyetem belső hálózatán keresztül (vagy hitelesített felhasználók számára) közzétegye. Kijelentem, hogy a benyújtott munka és annak elektronikus verziója megegyezik. Dékáni engedéllyel titkosított diplomatervek esetén a dolgozat szövege csak 3 év eltelte után válik hozzáférhetővé. Kelt: Budapest, 2015. 05. 22.

...……………………………………………. Simon Benedek

Összefoglaló Napjainkban a közösségi hálók felhasználói egyre több információt osztanak meg magukról. Ezekhez az információkhoz számos fél hozzáférhet. A hálózat üzemetetője kutatási célra közzé teheti az információkat vagy eladhatja ipari partnereinek. Ilyenkor a felhasználók privátszférájának védelme érdekében az egyértelmű azonosítókat eltávolítják, vagyis nevet, címet, e-mail címet nem közölnek. Az ilyen módon elvégzett anonimizáció azonban visszafordítható. Léteznek olyan algoritmusok, amelyek a hálózat struktúrája alapján egy háttérismereti hálózat segítségével képesek az anonim felhasználókat összekötni valós identitásukkal. Dolgozatomban először a jelentősebb algoritmusokat ismertetem, majd kiválasztom a state-of-the-art algoritmust. Ezután ismertetem a mérésekhez kifejlesztett keretrendszert illetve a mérések módszertanát. A state-of-the-art algoritmus fejlesztéseként két új algoritmust javasolok. Ezek a Grasshopper és a Bumblebee, melyeket az ismertetett módszertan segítségével összehasonlítok a state-of-the-art algoritmussal. Rávilágítok az új algoritmusok előnyeire illetve hátrányaira. Méréseimből kiderül, hogy a Grasshopper jelentősen javít a hibaarányon és kisebb kezdeti információ mellett is képes működni, miközben futási időben jól skálázódik. Továbbá, hogy a Bumblebee akár már egyetlen kezdeti párosítás megadásával is képes működni, illetve hibaaránya és hozama közötti kompromisszum széles skálán állítható.

Abstract Nowadays, the users of social networks share more and more information about themselves. This information is accessible by numerous parties; however, the operator of the network can share it for research purposes or sell it to business partners. The identifiers, like names, addresses or e-mail addresses are removed in the process in order to protect the users privacy. Unfortunately, such naive anonymization techniques can be reversed. There are algorithms which can connect anonymous users with their real identity using a background network, based on the structure obtained from a different public network. First of all, discuss the most efficient and current algorithms, then I choose the state-of-the-art algorithm in my thesis. Thereafter, I disclose the framework developed for the measurements and the methodology of the measurements. I propose two new algorithms as improvements of the state-of-the-art algorithm. These are the Grasshopper and the Bumblebee attacks, which I compare to the state-ofthe-art algorithm with the help of the disclosed methodology. The benefits and the disadvantages of the algorithms are also presented. As my measurements show, Grasshopper significantly improves the error rate and is able to operate with less initial information, while also scaling well in runtime. Furthermore, Bumblebee is able to run with only a single given seed, and the trade-off between its error rate and yield can be adjusted in a wide range.

7

1 Bevezetés A közösségi hálózatok mindennapjaink részét képezik, naponta osztunk meg magunkról különböző információkat ezen oldalak segítségével. Ezek az információk alkalmasak lehetnek visszaélésekre a felhasználók privátszférájával szemben. Harmadik fél kezébe kerülve célzott hirdetéseket adhatnak le, vagy akár dinamikus árazást is megvalósíthatnak. Másrészt olyan visszaélésekre is sor kerülhet, amelyek az etikusság határát súrolják. Például egy hiteligény jóváhagyása vagy elutasítása múlhat azon is, hogy milyen ismerőseink vannak a Facebook-on [8]. Ezen kockázat ellenére a felhasználók továbbra is megosztják érzékeny információikat, naivan abban bízva, hogy a közösségi hálók üzemeltetői a megfelelő diszkrécióval és kizárólag az ő javukra kezelik adataikat. Minden közösségi háló alapvetően egy gráf struktúrára épül. Az egyes felhasználókat tekintjük a gráf csúcsainak, míg a közöttük létrejött különböző kapcsolatokat illetve interakciókat tekintjük a gráf éleinek. Ilyen hálózat lehet egy közösségi oldal kapcsolati térképe, hogy ki milyen filmet értékelt vagy nézett meg vagy akár az is, hogy ki kivel levelezett. A hálózatok üzemeltetői sok esetben megosztják az adataik egy részét, főleg kutatási céllal, többek között a hálózat gráf reprezentációját. Ilyenkor a gráf csúcsainak illetve éleinek bizonyos attribútumait is elérhetővé tehetik. Ezek között az attribútumok között szerepelhetnek érzékeny információk is, de ilyenkor az egyes felhasználók közvetlen beazonosítására alkalmas attribútumait (név, cím, email cím stb.) törlik, így anonimizálva a hálózatot. Más esetekben pont ezek az információk állnak rendelkezésre, míg az érzékeny információk nem. Így a privátszféra védelme adott, az információk egyszerre nem érhetőek el. Az egyes csúcsok szomszédsága is az attribútumok körét képezik, ez is lehet érzékeny, de jellegéből fakadóan nem törölhető a gráfból, általában minimális mértékben ezt is módosítani szokták (ügyelve, hogy a gráf jellemzői alig változzanak).

8

1. ábra: példa a strukturális újraazonosításra

Léteznek algoritmusok, melyek képesek megfeleltetést létrehozni két gráf csúcsai között pusztán a gráfok struktúrája alapján, akkor is, ha nagyméretű, több százezer csúcsból álló vagy nagyobb gráfokról van szó. Amennyiben rendelkezésünkre áll a fent említett gráfok közül egy olyan, mely a felhasználók érzékeny információit tartalmazza, illetve egy olyan, mely a személyes beazonosításra alkalmas információkat és ezek a gráfok strukturálisan hasonlóak, tehát legalább részben ugyanazt a közösséget reprezentálják, akkor egy ilyen algoritmus segítségével deanonimizációs támadást lehet végrehajtani, az anonim felhasználókat összekötjük valós identitásukkal. Az 1. ábrán szerepel erre egy példa. Az 1.a ábrán láthatjuk a nevekkel ellátott közösségi hálót, mely nem tartalmaz érzékeny információkat, a 1.b ábrán pedig egy naivan anonimizált hálózatot. A nevek nem szerepelnek, de fel van tüntetve, hogy ki szereti a kutyákat és ki szereti a macskákat. Tekintsük ezt érzékeny információnak. Fruzsinak van a legtöbb szomszédja, így a támadó azonosítja a 6-os felhasználóval és innen tudja, hogy Fruzsi a kutyákat szereti. Hasonlóan egyedi fokszámmal rendelkezik Erika és Gréta is, így a támadó az 5-ös és 7-es felhasználókként azonosítja őket és megállapítja, hogy mindketten a macskákat szeretik. A többi felhasználó fokszáma már nem egyedi, ezért ilyen módon nem lehet őket azonosítani. Nem reménytelen azonban a helyzet. Bogi és Juli két-két szomszéddal rendelkeznek, akik ráadásul már mind azonosítva vannak. Az anonimizált hálózatban két ekkora fokszámú felhasználó van, a 2-es és a 10-es. Bogi szomszédjai az 5-ös és 6-os felhasználóként lettek azonosítva, ezeknek közös szomszédja a 2-es felhasználó, de a 10-es csak a 6-osé. Ezért a támadó azonosítja Bogit a 2-es felhasználóval, majd hasonló módon Julit a 10-essel. Nem lehet azonban azonosítani Dórit és Krisztit, mindkettejüknek ugyanaz a szomszédsága. A 9

támadó az anonimizálás ellenére meg tudta állapítani, hogy az egyes felhasználók melyik állatot kedvelik. Egy ilyen algoritmust mutatott be Narayanan és Shmatikov 2009-ben [1]. Ez az algoritmus a fent említett anonimizált és ismert gráf összekapcsolását képes hatékonyan végrehajtani. Tanulmányukban egy Twitter és Flickr részgráfra megmutatták, hogy az algoritmus mindössze 12.1% hiba mellett 30.8% párosítást képes megtalálni. Az ismert átfedés tekintetében ez nagyjából 10 ezer felhasználó deanonimizálását jelenti. Az algoritmus működési elvét a 2.1 fejezetében mutatom be. Munkám során az ilyen strukturális deanonimizációs algoritmusokat vizsgálom. Az általam legjobbnak vélt algoritmus fejlesztésére javaslatokat teszek, majd ezeket az új algoritmusokat implementálom, és vizsgálom, hogy milyen javulást sikerült elérni és ez milyen hátrányokkal jár. Vizsgálataimat valós közösségi hálókon való mérésekkel támasztom alá.

10

2 Irodalomkutatás A hálózatok üzemeltetői által naivan anonimizált, majd megosztott adatbázisok deanonimizációjára többféle próbálkozás volt már. Például Srivatsa és Mudhakar tanulmányukban egy útvonal adatokból álló adatbázis alapján készítették el a mögöttes közösségi hálót, melyet ezután sikeresen deanonimizáltak [14]. A deanonimizálás egyik módja lehet a felhasználók speciális attribútumainak felhasználása. Azokat a felhasználókat lehet ilyenkor azonosítani, akiknek az attribútum halmaza egyedi. Ezt a módszert alkalmazta Vesdapunt és Garcia-Molina munkájukban [15]. Előfordulhat, hogy nem áll a támadó rendelkezésére megfelelő attribútum halmaz, ez motiválta a probléma megközelítését csupán a strukturális információkra hagyatkozva. Maga a strukturális ekvivalencia már a szociológiában is jelen van [13], bár ezeknél az algoritmusoknál ekvivalencia helyett hasonlóságot vizsgálnak. A siker lehetséges az egyes csúcsok szomszédsága szerinti globális azonosítással, ahogy azt Zhou és Pei tették tanulmányukban [16], akik bevezették a k-neighborhood anonymity fogalmát a k-anonymity mintájára, és azt vizsgálták, hogy egy csomóponthoz hány másik található, amelynek a szomszédjainak a struktúrája ugyanaz. Liu és Terzi a csúcsok fokszáma alapján vizsgálták az anonimitást [18] (és bevezették a k-degree anonymity fogalmát). Egy másik példában Hay, Miklau és Jensen többféle módszert alkalmaztak, például a csúcsokat a gráfok kitüntetett csúcsaihoz való viszonyuk alapján azonosították. Máskor pedig a csúcsok szomszédjainak fokszáma szerint tették ugyanezt [17]. Ezekben a példákban globálisan vizsgálják a gráfokat, így az azonosítható csúcsok száma limitált, ráadásul a gráfok méretének növekedésével rosszul skálázódnak. Egy ilyen, meta információkra épülő algoritmust hozott létre Narayanan és Shmatikov, amikor a Netflix ajánlórendszere továbbfejlesztésének céljából kiadott anonimizált adatbázis és az IMDB felhasználói között találtak kapcsolatot, így deanonimizálva az előbbit [5],[11]. A Netflix kiadott adatbázisa összes felhasználójának nyolcadáról tartalmazta filmértékeléseiket. A verseny célja az lett volna, hogy a kiadott információk alapján adatbányászati megoldásokkal megjósolják, hogy kinek milyen film fog tetszeni, így azt tudja a rendszer ajánlani. Ezt alapvetően úgy csinálják, hogy az adatbázisban keresnek olyan felhasználókat, akik hasonló pontokat adtak az egyes 11

filmekre. Ezután az olyan filmekre, melyet a felhasználó nem értékelt, azt a pontszámot jósolják, melyet a hozzá hasonló felhasználók adtak. Tehát csak a kiadott, anonim adatbázisban kerestek. Ezzel szemben Narayanan és Shmatikov egy új koncepcióval álltak elő. A filmértékeléseket ujjlenyomatként felhasználva egy erre a célra kifejlesztett hasonlósági metrika segítségével összehasonlították az IMDB adatbázisában lévő felhasználók értékeléseivel, így összekapcsolva őket. Ehhez elég volt, ha a felhasználó 8 filmet értékelt a Netflix illetve az IMDB adatbázisában, melyek közül csak 6 értékelésnek kellett azonosnak lennie. A Netflix adatbázisa így kibővült az IMDB információival, de ez visszafelé is igaz, vagyis az IMDB nem anonim felhasználóiról is több információ lett ismert, mely sértheti privátszférájukat. Egy későbbi munkájuk – ugyanezen alapelveket követve – már kifejezettem közösségi hálók újraazonosítására szolgált [1], ráadásul mindezt széles körben tette, tehát nem csak az egészen egyedi felhasználókat azonosította. Ezt az algoritmust részletesen elemzem a 2.1 fejezetben. A Narayanan algoritmus sikerein felbuzdulva többen is próbálkoztak még jobb algoritmust készíteni. Ilyenkor a célkitűzés lehet a minél nagyobb arányú újraazonosítás, a kisebb hibaszázalék vagy akár a szükséges kezdeti információk mennyiségének csökkentése. A 2.2, 2.3 és 2.4 fejezetekben ilyen algoritmusokat mutatok be, majd a 2.5 fejezetben megjelölöm a state-of-the-art algoritmust, mely a továbbiakban fejlesztéseim alapját képezi.

2.1 A Narayanan algoritmus Ebben a fejezetben Arvind Narayanan és Vitaly Shmatikov által létrehozott strukturális deanonimizációs algoritmust [1] mutatom be. Az itt ismertetett alapelvek többsége a későbbi algoritmusokban is megjelenik. A támadás két gráfon kerül végrehajtásra: az anonimizált cél gráfon, illetve az ismert háttér-információ, vagy forrás gráfon. A támadás célja, hogy ismert csúcsokat (forrás gráf) ismeretlenekkel összekössön (cél gráf), így deanonimizálva azokat. A támadás két fázisból áll. Az első fázisban, a seed keresésben, létrehoz egy kezdeti összerendelést néhány csomópont között, melyet a második fázis bemenetként használ fel, tovább bővíti a deanonimizált csomópontok halmazát.

12

A seed keresési algoritmusokra jellemző, hogy más bementet híján, a gráfok globális tulajdonságait veszik alapul (például kiugró egyedi fokszámok), az egész gráfban vizsgálódnak. Ez rossz skálázhatóságot eredményez, illetve erősen limitálhatja a megtalálható összerendelések számát. A korlátozott erőforrások miatt, ezekkel az algoritmusokkal csak egy kisebb részeredményt érhetünk el, a nagymértékű újraazonosításra nem alkalmasak. Szükségünk van tehát egy második fázisra, a terjedési (propagation) fázisra, mely az első fázisból származó összerendelések számát növeli. Ebben a szakaszban az algoritmus iteratív, minden iterációban az előző eredmények alapján növeli a deanonimizált csúcsok számát. Ebből is következik, hogy beindításához szükség van a seedre. Az algoritmus a két gráf egy-egy csúcsa között keres hasonlóságot. Ha elég nagymértékű hasonlóságot talál, akkor azt hozzáveszi a meglévő párosításokhoz. A hasonlóságot egy pontozásos rendszer segítségével állapítja meg.

2.1.1 A terjedési fázis működése Legyen a két gráf 𝐺1 = (𝑉1 , 𝐸1 ) és 𝐺2 = (𝑉2 , 𝐸2 ), a két összehasonlítandó csúcs pedig rendre 𝑢 ∈ 𝑉1 és 𝑣 ∈ 𝑉2 . 𝑣 minden olyan szomszédja után kap egy pontot, amelyik 𝑢 valamely szomszédjához van párosítva. Mivel ezekben a gráfokban elég nagy skálán mozognak a csúcsok fokszámai, így ezt a pontszámot v fokszámának gyökével leosztjuk. Legyen 𝑉𝑛𝑏𝑟 a 𝑣 szomszédjainak halmaza 𝑉2–ben, 𝑈𝑛𝑏𝑟 pedig 𝑢 szomszédjainak halmaza 𝑉1-ben, míg 𝑈𝑛𝑏𝑟 ′ az 𝑈𝑛𝑏𝑟 elemeihez párosított 𝑉2–beli csúcsok halmaza. |𝑉𝑛𝑏𝑟 ∩ 𝑈𝑛𝑏𝑟 ′ |

𝑠𝑐𝑜𝑟𝑒(𝑣, 𝑢) =

√|𝑉𝑛𝑏𝑟 |

Az így számolt mérték nagyon hasonlít a koszinusz hasonlósághoz. cos(𝑉𝑛𝑏𝑟 , 𝑈𝑛𝑏𝑟 ′ ) =

|𝑉𝑛𝑏𝑟 ∩ 𝑈𝑛𝑏𝑟 ′ | √|𝑉𝑛𝑏𝑟 ||𝑈𝑛𝑏𝑟 ′ |

Az 2. ábra segítségével szemléltethetőek az előzőekben tárgyalt hasonlóságok. A-nak és B-nek két-két olyan szomszédja van, amelyek egymással vannak párosítva, illetve B fokszáma 3 így: 𝑠𝑐𝑜𝑟𝑒(𝐵, 𝐴) =

2 √3

. Mivel A fokszáma is 3, ezért: cos(𝐴, 𝐵) =

13

2

. A későbbiekben A-hoz fogunk hasonlítani több különböző B-t, majd ezek közül

√3∗3

választunk, A fokszámának gyökével felesleges leosztani, az arányok megmaradnak az osztás nélkül is.

2. ábra: Hasonlóság számítása A és B között (kép forrása:[5])

Érdemes észrevenni, hogy A és B hasonlóságának vizsgálata során csak lokális információkat használtunk fel, így az algoritmus jól skálázható marad. Az egyes iterációkban az algoritmus kiválaszt egy olyan 𝑢 ∈ 𝑉1–et, amelynek van újraazonosított szomszédja (minden iterációban végighalad az összes ilyen 𝑢-n). Ezután kiszámolja a hasonlóságot 𝑢 és minden olyan 𝑣 ∈ 𝑉2 között, amelynek szintén van újraazonosított szomszédja. Ha az így kiszámolt pontok között valamelyik kiugróan nagyobb a többinél, akkor az ahhoz tartozó 𝑣 lesz 𝑢-hoz a legjobb találat. Ezután a két gráf szerepét felcserélve 𝑣-hez keressük a legjobb találatot. Ha ez éppen 𝑢, akkor (𝑢, 𝑣)-t hozzávesszük az eddigi párosításainkhoz. A pontok közül akkor számít kiugróan nagynak egy érték, ha az a legnagyobb, illetve ha a második legnagyobbnál az összes pontszám szórásának konstansszorosával nagyobb. Ezt a konstanst 𝜃-val jelöljük, segítségével beállíthatjuk, hogy az algoritmus mennyire legyen mohó. 𝑘𝑖𝑢𝑔𝑟á𝑠 =

max(𝑋) − 𝑚𝑎𝑥2(𝑋) 𝑠𝑡𝑑(𝑋)

14

Ahol 𝑋 a pontszámok halmazát, max(𝑋) a legnagyobb pontszámot, 𝑚𝑎𝑥2(𝑋) a második legnagyobb pontszámot, illetve 𝑠𝑡𝑑(𝑋) a standardszórást jelöli. Ha minden 𝑢-n végigmentünk, amelynek van újraazonosított szomszédja, az iterációnak vége. Ha az iteráció során találtunk új párosítást, akkor új iterációba kezdünk, egyébként az algoritmus leáll. Az algoritmus pszeudokódja [1]: function propagationStep(lgraph, rgraph, mapping) for lnode in lgraph.nodes: scores[lnode] = matchScores(lgraph,rgraph,mapping,lnode) if eccentricity(scores[lnode]) < theta: continue rnode = (pick node from rgraph.nodes where scores[lnode][node] = max(scores[lnode])) scores[rnode] = matchScores(rgraph,lgraph,invert(mapping), rnode) if eccentricity(scores[rnode]) < theta: continue reverse_match = (pick node from lgraph.nodes where scores[rnode][node] = max(scores[rnode])) if reverse_match != lnode: continue mapping[lnode] = rnode function matchScores(lgraph, rgraph, mapping, lnode) initialize scores = [0 for rnode in rgraph.nodes] for (lnbr, lnode) in lgraph.edges: if lnbr not in mapping: continue rnbr = mapping[lnbr] for (rnbr, rnode) in rgraph.edges: if rnode in mapping.image: continue scores[rnode] += 1 / rnode.in_degree ˆ 0.5 for (lnode, lnbr) in lgraph.edges: if lnbr not in mapping: continue rnbr = mapping[lnbr] for (rnode, rnbr) in rgraph.edges: if rnode in mapping.image: continue scores[rnode] += 1 / rnode.out_degree ˆ 0.5 return scores function eccentricity(items) return (max(items) - max2(items)) / std_dev(items) until convergence do: propagationStep(lgraph, rgraph, seed_mapping)

2.1.2 A vizsgálat módja és eredmények Az algoritmus megalkotói először a seed mérete szerint vizsgálódtak. A 3. ábrán a helyesen összerendelt csúcsok számát láthatjuk a seed mérete függvényében. Az algoritmus hozama függ a seed méretétől: egy bizonyos seed méret alatt az algoritmus csak az elméletileg azonosítható csúcsok elhanyagolható hányadát azonosítja, majd e 15

fölött a kritikus méret fölött az újraazonosított csúcsok száma megugrik, de ezután szinte nem változik.

3. ábra: Helyes összerendelések aránya a seed méretének függvényében (kép forrása: [1])

Különböző perturbációk esetében ez a kritikus méret változhat, illetve a seedelési eljárás tartalmazhat véletlenszerűségeket is, ezért a különböző seed méretekhez egy-egy valószínűséget rendelhetünk aszerint, hogy bekövetkezik-e a széleskörű újraazonosítás vagy sem.

4. ábra: Széleskörű újraazonosítás valószínűsége a seed méretének függvényében (kép forrása:[1])

A helyesen és hibásan azonosított csúcsok számát természetesen a perturbáció mértéke is befolyásolja. Ezt láthatjuk a 5. ábrán.

16

5. ábra: Helyesen illetve hibásan újraazonosított csúcsok aránya az élek átfedésének függvényében (kép forrása: [1])

A fentiekből látható, hogy az algoritmus igen alacsony hibaarány mellett széleskörű újraazonosítást ér el nem túl nagy kezdeti információ segítségével. Ráadásul mindezt gyorsan végzi, akár egy otthoni számítógépen is képes elfutni.

2.2 A Seed-and-Grow algoritmus Ebben a fejezetben a Seed-and-Grow [2] algoritmust mutatom be. Ez egy kétfázisú algoritmus, melyben az első fázis egy kezdeti párosítást keres, egy úgynevezett aktív seedelési módszer segítségével, majd a második fázis az így megszerzett információ segítségével végez széleskörű újraazonosítást.

2.2.1 Az algoritmus működése Az első fázis a két gráf közötti különbséget létrehozó zavarok, tehát a perturbáció előtt a gráfok közös ősébe beilleszt egy speciálisan megszerkesztett gráfot, melyet a perturbáció után mindkét gráfban könnyen azonosíthatunk. Ehhez egy olyan beültetendő gráfot hozz létre, mely strukturálisan egyedi, de beillesztve azt, nem tűnik ki, csak annak, aki a megfelelő mintát keresi. Továbbá a gráf nem lehet automorf, mivel így önmagán belül sem lehetne megkülönböztetni a csúcsait. A második fázisban az algoritmus az előző fázisban szerzett információk segítségével, a csúcsok különbözőségét vizsgáló metrika segítségével keres új párosításokat. Az algoritmus alkotói az algoritmusnak két változatát készítették el. Az első, bonyolultabb verzióban a csúcsok összehasonlítása folyamán az azonosított és nem 17

azonosított szomszédjaik különbözőségét külön-külön vizsgálja, majd ezeket az értékeket súlyozza aszerint, hogy az adott csúcsok szomszédsága milyen arányban van azonosítva. Később elkészítettek egy egyszerűbb változatot, mely jobb eredményeket hozott, ezért csak ezt ismertetem részletesebben. Ebben a verzióban két csúcs különbözőségét kizárólag a már azonosított szomszédjaik alapján számítják egy aszimmetrikus metrika segítségével. Legyen 𝑢 ∈ 𝑉1 , 𝑣 ∈ 𝑉2 . Ekkor 𝑇 (𝑢) 𝐵 (𝑣)| |𝑁𝑚 − 𝑁𝑚 ∆ 𝑇 (𝑢, 𝑣) = 𝑇 (𝑢)| |𝑁𝑚 𝐵 (𝑣) 𝑇 (𝑢)| |𝑁𝑚 − 𝑁𝑚 ∆𝐵 (𝑢, 𝑣) = 𝐵 (𝑣)| |𝑁𝑚 𝑇 (𝑢) 𝐵 (𝑣) Ahol 𝑁𝑚 illetve 𝑁𝑚 az 𝑢 és 𝑣 csúcsok már azonosított szomszédjainak

halmaza 𝑉1-ben. ∆ 𝑇 (𝑢, 𝑣) u szomszédjai közül a nem v szomszédjaival azonosítottak és u összes szomszédja között állít fel egy arányt, ∆𝐵 (𝑢, 𝑣) ugyanezt teszi u-t és v-t felcserélve. Ez a két érték közösen fejezi ki, hogy u és v mennyire különbözik. Az algoritmus minden iterációban először jelölteket választ 𝐺1 -ben illetve 𝐺2 ben, ezek az összes eddig azonosított csúcs illetve összes szomszédjaik. Ezután kiszámolja a 𝐺1 -ben lévő összes jelölt és a 𝐺2 -ben lévő összes jelölt között a fent taglalt különbözőségi értékeket egy mátrixba rendezve (melynek minden pontjában egy számpár áll). Következő lépésben az algoritmus kiválasztja azokat a számpárokat, melyek a sorukban és oszlopukban külön-külön a legkisebbek. Amennyiben egy sorban vagy oszlopban több ilyen is szerepel, az ezekhez tartozó oszlopok vagy sorok közül azt választja, amelyikben a számpár értékei kiugróan kisebbek a többi értéknél. Az így kiválasztott mátrixelemek egy-egy párosítást reprezentálnak, ezek lesznek a következő iteráció bemenetei. Az iterációkat addig folytatja az algoritmus, amíg egy iterációban már nem talál új párosításokat, majd ezután leáll. Mivel a jelöltek között vannak a már azonosított csúcsok és minden iterációban újra meghatározza a legalkalmasabb párosítást számukra is, ezért az algoritmus alkalmazza a revisitnek nevezett eljárást. Ez lehetővé teszi a korai iterációkban hibás párosítások javítását, így ezek a téves információk nem rontják el a későbbi iterációkat. Biztosabbak lehetünk azonosításainkban, ha a két csúcs szerepeit felcserélve is ugyanazt a párosítást kapjuk, ez az úgynevezett reverse matching. Ezt az algoritmus úgy 18

viszi végbe, hogy a mátrixban a sorok mellett az oszlopokat is vizsgálja: a sorban a legkisebb számpár mutatja, hogy 𝑢-hoz melyik v a legjobb választás, az oszlopban pedig, hogy v-hez melyik 𝑢 tartozhat. Ha a számpár mind a sorban, mind az oszlopban a legkisebb, az kölcsönösen a legjobb választást jelenti. Ezen felül az aszimmetrikus különbözőségi metrika is egyfajta reverse matchinget eredményez. Az algoritmus pszeudokódja [2]: Given the initial seed VS. C = ∅ loop CT = {u∈ VT|u connects to VS} CB = {v∈ VB|v connects to VS} if (CT,CB)∈ C then return VS end if C = C ∪ {(CT,CB)} for all (u, v) ∈ (CT,CB) do Compute ∆T(u, v) and ∆B(u,v). end for S = {(u, v) | ∆T(u, v) and ∆B(u,v) are smallest among conflicts} for all (u,v)∈ S do if (u,v) has no conflict in S or (u,v) has the uniquely largest eccentricity among conflicts in S then VS = VS ∪ {(u,v)} end if end for end loop

2.2.2 A vizsgálat módja és eredmények Az algoritmus teszteléséhez a LiveJournal illetve az emailWeek gráfokat használták ősgráfként. Az ősgráfból két részgráfot vágtak ki, adott mérettel úgy, hogy az átfedés előre meghatározott legyen. Ebből az átfedésből választottak seedet. Ezután mindkét gráfban függetlenül egymástól, véletlenszerűen éleket vettek fel. A fenti perturbációs eljárással készített gráfokon lefuttatták a Seed-and-Grow algoritmus („sng” a későbbi eredményekben) második fázisát illetve a Narayanan algoritmus második fázisát két különböző 𝜃 értékkel: egy agresszívabb 𝜃 = 0.0001 (nar a), illetve egy sokkal kevésbé mohó 𝜃 = 1 (nar c) értékkel

19

6. ábra: Különböző seed méretek mellett mért helyesen és hibásan újraazonosított csúcsok száma (kép forrása: [2])

. A LiveJournal esetében egy 800 csúcsból álló ősgráfból készítettek két 600 csúcsból álló gráfot, 400 csúcs átfedéssel. Az emailWeek esetében két 125 csúcsból álló gráfot készítettek, 100 csúcs átfedéssel. Ezek a méretek sajnos rendkívül kicsik, össze sem mérhetőek egy valódi közösségi hálóval. Bár a Seed-and-Grow algoritmus bizonyos jellemzőkben jobb eredményeket hoz, mint a Narayanan algoritmus, fontos észrevenni, hogy a Seed-and-Grow nagy memóriaigénnyel rendelkezik (minden jelöltet minden jelölttel összehasonlít). Ebből kifolyólag a gyakorlatban nem alkalmazható. Előnye azonban, hogy nincs szükség a 𝜃 paraméterre, amelyet ideálisan beállítva a Narayanan féle algoritmus jobb eredményeket produkálhat, de minden esetben más és más lehet ez az ideális érték. Ezt az algoritmus alkalmazója nem ismeri, és csak próbálgatással keresheti, megfelelő visszacsatolás nélkül, mivel csak a hozamot tudja mérni, a helytelenül azonosított párosítások számát már nem.

20

2.3 Bayes döntésen alapuló algoritmus 2.3.1 Az algoritmus működése A fejezetben taglalt algoritmus [3], az előzőekkel ellentétben, egy fázisban működik. Fontos különbség tehát, hogy a Narayanan illetve a Seed-and-Grow algoritmusok második fázisával szemben, itt nincs szükség előre meghatározott, az induláshoz szükséges kezdeti párosításra. Az algoritmus először rendezi 𝐺1 és 𝐺2 csúcsait fokszámaik alapján. Minden iterációban egy jelölthalmazban vizsgálódik. Ennek mérete kezdetben 2-2 csúcs, majd iterációnként megkétszereződik. Az előzőkhöz hasonlóan a csúcsok vizsgálata a gráf struktúrájában hagyott nyomaik alapján történik, ezt nevezzük ujjlenyomatnak, angolul fingerprintnek. Az algoritmus olyan metrikával él, melyben a fingerprint iterációról iterációra változik (bővül). A fingerprint első része a csúcs abszolút tulajdonságaiból áll. Ez a megvalósított algoritmusban egy elem, a csúcs fokszáma. A fingerprint második része a csúcs relatív tulajdonságaiból áll. A gyakorlatban ez a már azonosított csúcsoktól való távolságokból álló vektort jelenti. Az algoritmus során az azonosított csúcsok száma folyamatosan növekszik, így a fingerprint mérete is vele együtt nő. Az algoritmus összehasonlítja 𝐺1 jelölthalmazában lévő összes csúcsot 𝐺2 jelölthalmazában lévő összes csúccsal. Az összehasonlítás egy becsült valószínűség számítást jelent: mekkora a valószínűsége, hogy ha a két csúcs összetartozik, akkor a perturbáció folyamán az adott két fingerprint jött ki. Ehhez azonban ismerni kell a perturbáció modelljét, paramétereit, illetve a gráfok fokszám- és távolságeloszlását. Mivel ez nem áll rendelkezésre, ezért jobb híján csak becsülni lehet. A kialakult mátrixba rendezett értékeket tekinthetjük egy súlyozott teljes páros gráfnak is. Ebben a Magyar módszer [6] segítségével polinom időn belül lehet maximális súlyú párosítást találni. Ezt a maximális súlyú párosítást, mivel kvázi valószínűségek a súlyok, egy maximum likelihood becslésnek tekinthetjük. Mivel a jelölthalmazban lehetnek olyan csúcsok, melyek párja nincs benne a másik jelölthalmazban, ezért valószínű, hogy a teljes párosítás sok hibát tartalmaz. Hogy a hibák ne okozzanak még több hibát a későbbiekben, ezért a párosításokat az algoritmus hozzájuk rendelt súly alapján sorba rendezi, majd csak a sor felső felét 21

hagyja meg. Így várhatóan a párosításhalmaz jelentősen tisztul. Ezeket a párosításokat kapja meg a következő iteráció. Az algoritmus akkor áll le, ha a jelölthalmaz az egész gráfra kiterjed.

2.3.2 A vizsgálat módja és eredmények Az algoritmus készítői vizsgálataikhoz az EPFL-en gyűjtött adatokból készült gráfot használták, melyben a csúcsok az egyes felhasználókat reprezentálják, míg élek azok között a felhasználók között vannak, akik az adott időszakban email-t váltottak egymással (kb. 2000 felhasználó). A perturbációnak két fajtáját használták, az elsőben a gráf éleit mintavételezték 𝑠 mintavételi valószínűséggel. Ilyenkor az 𝑠 2 érték felel meg az élek átfedésnek, míg a csúcsok közötti átfedés teljes. A második esetben két különböző időszakból választották a gráfokat. Az élek közötti átfedés így az időbeli átlapolódással kapcsolatos, míg a csúcsok átfedése továbbra is teljes.

7. ábra: Különböző él átfedések mellett a hibaarány az algoritmus lefolyása során (kép forrása:[3])

Jól látható, hogy elfogadható eredményt csak 𝑠 2 = 0.72 vagy ennél kisebb mértékű perturbáció esetén kapunk. Ez nagyon kis perturbációt jelent tekintve, hogy teljes a csúcsok közötti átfedés. Mivel a vizsgált gráfok nagyon kicsik, ezért ezek az eredmények nem relevánsak. Valószínű, hogy a gráf méretét az algoritmus lassúsága és hatalmas memóriafoglalása miatt választották ekkorára. Az algoritmus teljes párosítást ad, még akkor is, ha nem teljes az átfedés a gráfok között. Ebben az esetben jelentősen nő a hibás összerendelések száma. Ezen segíthet az iterációk végén megismert módszer, mely szerint a sorrendbe állított súlyok felső részét hagyjuk csak meg. Természetesen nem tudjuk, hogy mekkora az átfedés, ezért a felső rész méretét sem tudhatjuk. Továbbá nagy hátránya lehet az algoritmusnak, hogy a két gráfnak azonos méretűnek kell lennie.

22

A fokszám- és távolság eloszlások modellezéséhez az Erdös-Rényi véletlen gráf modell egy módosított verzióját használták, melyben egy 𝑞 paramétertől függő mértékben háromszögeket helyeztek el az ősgráfban. Ennek következtében a perturbáció során a távolságok kisebb mértékben változnak, mely a fingerprintek összehasonlíthatóságát segíti. Az említett gráf modell illetve módosított verziója tekintetében nem támasztja alá semmi, hogy a valós közösségi hálók struktúráját követné. A Narayanan algoritmusnál gondot okozhatott, ha a seed elemei távol vannak egymástól (𝑑 ≥ 3). Ilyenkor egyetlen csúcs sincs, melynek két azonosított szomszédja is van. Itt ilyen probléma nincsen.

2.4 Bringmann algoritmus: 2.4.1 Közösségi hálók modellezése Mivel a soron következő algoritmus [4] működése nagyban épít a közösségi hálók gráfjainak egy speciális modellezésére és magára a perturbációs eljárás módjára, ezért az ismertetést ezekkel kezdem. Az algoritmus készítői a Chung-Lu [7] véletlen gráffal modellezték a közösségi hálókat. Ebben a modellben lehetőség van különböző paraméterek segítségével beállítani az átlagos fokszámot illetve a fokszám eloszlás exponensét. A modell ehhez először felveszi a kívánt mennyiségű csúcsot (még élek nélkül), majd a megfelelő eloszlás szerint súlyokat ad nekik, végül minden két csúcs közé egy bizonyos valószínűséggel behúz egy élet. Ez a valószínűség a két csúcs súlyának szorzata illetve az összes csúcs súlya összegének hányadosa. Az így készült gráfot tekintjük az ősgráfnak. Ebből a gráfból a csúcsok 𝑞1 valószínűségű mintavételezésével, majd a megmaradó élek 𝑝1 valószínűségű mintavételezésével kapjuk 𝐺1 -et, hasonlóan 𝑞2 illetve 𝑝2 valószínűségekkel kapjuk 𝐺2 -t. Így a csúcsok átfedése 𝑞1 ∙ 𝑞2 lesz. Az élek átfedése nem számítható hasonló módon, mivel a csúcsok mintavételezése során már elvesznek élek, de a 𝑝1 ∙ 𝑝2 szorzat egy jó mutató lehet. Az algoritmus az előzőekben tárgyalt kétfázisú algoritmusok elve szerint működik, melyből a cikk a második fázist taglalja. Az első kimenetét, tehát a seedet ismertnek tekinti. Ez a seed a csúcsokat súlyuk szerint rendezve a legnagyobb súlyúakból áll (a seed mérete paraméterként megadható). 23

2.4.2 Az algoritmus működése Az algoritmus a fentiekben leírt modell helyességét feltételezi a közösségi hálókra. Ismertnek tekinti az ősgráf méretét, átlagos fokszámát, fokszám eloszlását (illetve annak exponensét), a perturbáció 𝑞1 , 𝑞2 , 𝑝1, 𝑝2 paramétereit. Az algoritmus készítői szerint e paraméterek becslése megoldható 𝐺1 és 𝐺2 alapján, illetve jól becsülhetőek, ennek mikéntjéről azonban nem írnak. Az algoritmus kezdetben a fenti paraméterek segítségével becslést ad a csúcsok súlyaira. Ezután a súlyok segítségével lehet kiszámolni annak a valószínűségét, hogy két csúcs között van-e él. Iterációról iterációra összehasonlítja az összes még nem azonosított csúcsot a másik gráfban szereplő nem azonosított csúcsok mindegyikével. Az összehasonlításhoz egy Y-teszt elnevezésű eljárást dolgoztak ki. 𝑣1 és 𝑣2 csúcsok összehasonlításakor egy azonosított 𝑢 csúcspárhoz képest a 8. ábrán látható esetek lehetségesek.

8. ábra: Az Y-tesztben előforduló esetek

Ez alapján az Y értékek:

𝑣 ,𝑣2

𝑌𝑢 1

1 2𝑝𝑣1 ,𝑢 , 𝐴𝑢 𝑒𝑠𝑒𝑡𝑏𝑒𝑛 𝑝 1 − 𝑢2 , 𝐵𝑢1 𝑒𝑠𝑒𝑡𝑏𝑒𝑛 = 𝑝1 1 − , 𝐵𝑢2 𝑒𝑠𝑒𝑡𝑏𝑒𝑛 𝑢 { 1, 𝐶𝑢 𝑒𝑠𝑒𝑡𝑏𝑒𝑛

A két csúcs teljes összehasonlítása során minden már meglévő azonosított párral, vagyis minden 𝑢 szemszögéből az algoritmus kiszámolja Y-t, majd ezeket összeszorozza. 𝑣 ,𝑣2

𝑌 𝑣1 ,𝑣2 = ∏ 𝑌𝑢 1 𝑢∈𝑉𝐼

24

Amennyiben a kiszámított produktum nagyobb, mint egy meghatározott konstans, akkor az Y-teszt pozitív és 𝑣1 -et 𝑣2 -höz párosítjuk (𝑌 𝑣1 ,𝑣2 > 𝑛𝑐 𝑎ℎ𝑜𝑙 𝑐 > 0 konstans). Az algoritmus addig ismétli az iterációkat, amíg talál új összerendelést, ezután leáll. Ehhez várhatólag log(𝑛) iterációra lesz szükség (ennek a cikkben láthatjuk egy kezdetleges bizonyítását). Mivel az algoritmus 𝑂(𝑛3 ) futási idővel rendelkezik, a készítők kifejlesztettek egy gyorsabb eljárást amelyben, a fenti produktumban szereplő 𝑢-knak csak egy véletlenszerű részét használják (iterációnként újrasorsolva). Illetve az összehasonlítások számát egy hashelési eljárás segítségével a két gráf éleinek összegére csökkentik. Sajnos ezek a változtatások a hibásan azonosított csúcsok számát jelentősen növelik.

2.4.3 A vizsgálat módja és eredmények Mivel az algoritmus minden iterációban csak a még nem azonosított csúcsokat vizsgálja, ezért a keletkező hibák nem kerülnek később javításra és további hibákhoz is vezethetnek. A tesztekhez egy Dual Xeon CPU E5-2670 processzorral és 128Gb rammal rendelkező számítógépet használtak, ez már nem egy átlagos otthoni felhasználásra szánt gép. Lefuttatták az algoritmust a kezdetben feltételezett, Chung-Lu modellel készített gráfon, majd egyéb véletlen gráf modelleken, mint a Preferential Attachment [9] illetve az Affiliation Network [10] modellek. Végül valós közösségi hálókon is tesztelték az algoritmust. A Chung-Lu modell esetében az ismertnek feltételezett paraméterek tényleg ismertek voltak. A többinél az ősgráf paramétereit csak becsülni tudták, de a perturbáció paraméterei továbbra is ismertek.

9. ábra: Mérési eredmények (forrás: [4])

A 9. ábrán jól látható, hogy az algoritmus igen nagy gráfokon is képes gyorsan újraazonosítást végezni. Ráadásul ehhez igen kisméretű seedre van szüksége és a 25

hibásan azonosított csúcsokból adódó precizitás mértéke a Narayanan algoritmusnál látottakkal hasonló (valós közösségi hálók esetében). Hátrány azonban, hogy amennyiben nem a Chung-Lu modellel előállított gráfról (vagy ahhoz hasonló modellről) van szó, akkor az algoritmus hozama alacsony. Ez lehet a modell és a valós gráfok közötti különbség következménye, de lehet a paraméterek hibás becslésének folyománya. További hátrány, hogy a gráf készítésének paraméterein túl ismerni kell a perturbáció paramétereit is. Ennek ismerete azonban hibás feltételezés és az egész algoritmus létjogosultságát kérdőjelezi meg.

2.5 A state-of-the-art algoritmus kiválasztása A fentiekben leírt algoritmusok, több-kevesebb sikerrel, mind megoldást nyújtanak a tárgyalt problémára. Az általam leggyengébbnek ítélt algoritmus a 2.3 fejezetben taglalt Bayes döntésen alapuló algoritmus. Minden esetben teljes párosítást ad, még akkor is, ha nem teljes az átfedés. Csak azonos méretű gráfokkal működik, tehát csak speciális esetekben lehet alkalmazni. Bár előnye, hogy az egymástól távoli seedek nem okoznak problémát, a mérések csak az algoritmushoz igazított Erdős-Rényi véletlen gráf modellben hoztak jó eredményeket. Az előzőnél némileg jobb a 2.2 fejezetben tárgyalt „Seed-and-Grow” algoritmus. Ezt már általános esetben lehet alkalmazni. Eredményei a többi algoritmussal szemben is jónak tekinthetőek, de ezt csak igen kicsi gráfok esetében mérték ki. Az algoritmus memóriaigénye

nagyon

nagy,

illetve

rosszul

skálázódik,

így

az

általános

felhasználhatóság visszaszorul a kis gráfokra. Az 2.4 fejezetben ismertetett algoritmus igen jó eredményekkel szolgál. Elindulásához elegendő egy nagyon kicsi seed, futási ideje alacsony, jól skálázódik, hibaaránya a többi algoritmuséval azonos nagyságrendű. Sajnos hátránya, hogy magas hozamot csak a meghatározott gráf modelleknél ért el, valós hálózatokon ez visszaesett még a gyenge perturbáció mellett is. Legnagyobb hátránya mégis az, hogy itt a perturbáció paramétereit ismerni kell. Ezt általános esetben nem ismeri a támadó, így az algoritmus nem alkalmazható. Az általam megjelölt legjobb algoritmus a 2.1 fejezetben taglalt, Narayanan algoritmus. Általános esetben alkalmazható, a gráfok méretére vagy átfedésére nézve 26

nincsen megkötés. Számítási igénye alacsony, akár egy otthoni számítógépen is elfut. Jól skálázható, futási ideje és memóriaigénye a nagy gráfoknál is kezelhető. Hozama magas és hibaaránya alacsony. Ezért a továbbiakban state-of-the-art algoritmusnak ezt az algoritmust tekintem.

27

3 Vizsgálati keretrendszer Dolgozatomban egyaránt vizsgálom a state-of-the-art algoritmust és új, általam fejlesztett algoritmusokat. Megállapításaimat mérésekkel támasztom alá. Ezekhez a mérésekhez szükség van egy keretrendszerre, melyben az algoritmusok azonos körülmények között futhatnak, így összehasonlíthatóvá válnak.

3.1 Régi keretrendszer, mátrixos leírásmód Munkám kezdetén az egyszerűség kedvéért Python nyelven kezdtem el a keretrendszert elkészíteni. Ez a nyelv nagyon intuitív, könnyű a szintaktikája. Ezen kívül előnye még, hogy igen sok előre elkészített könyvtár segíti a fejlesztést. A gráfok kezelésére az iGraph illetve a networkx könyvtárakat használtam, illetve később egy mátrixos ábrázolásmódot. A gráfokat leírhatjuk szomszédossági mátrixaikkal is, ahol a sorok és oszlopok a mátrix csúcsait reprezentálják. A mátrix egy eleme akkor nem nulla, ha a sor által reprezentált csúcsból megy él az oszlop által reprezentált csúcsba. Ez lehetővé teszi irányított gráfok leírását is, irányítatlan esetben a mátrix szimmetrikus. Súlyozott gráf esetén az éleket reprezentáló bejegyzések a súly értékét veszik fel, nem súlyozott esetben egyet. Az újraazonosító algoritmusok során két gráfot és a köztük lévő megfeleltetést kell ábrázolni. Ez a megfeleltetés egy páros gráfnak tekinthető, illetve az egész rendszer tekinthető egy nagy gráfnak. 𝑎11 ⋮ 𝑎𝑛1 𝐺= 𝑚 11 ⋮ ( 𝑚1𝑘

… 𝑎1𝑛 ⋱ ⋮ … 𝑎𝑛𝑛 … 𝑚𝑛1 ⋱ ⋮ … 𝑚𝑛𝑘

𝑚11 ⋮ 𝑚𝑛1 𝑏11 ⋮ 𝑏𝑘1

… 𝑚1𝑘 ⋱ ⋮ … 𝑚𝑛𝑘 𝐺1 = ( … 𝑏1𝑘 𝑀𝑇 ⋱ ⋮ … 𝑏𝑘𝑘 )

𝑀 ) 𝐺2

Ahol 𝐺1 egy 𝑛 × 𝑛-es, 𝐺2 egy 𝑘 × 𝑘-s szimmetrikus mátrix, M pedig egy 𝑛 × 𝑘s mátrix, mely sok szempontból olyan, mint egy permutáció mátrix. Az 𝑀-mel való szorzás átrendezi a sorokat vagy az oszlopokat (a szorzás irányától függően), illetve megváltoztatja a mátrix méretét, és sorokat vagy oszlopokat nulláz ki.

28

A Narayanan algoritmus pontszámítási eljárása felfogható 3 lépés hosszú utak kereséseként is azzal a feltétellel, hogy az útvonal első két csúcsa az első gráfban, második két csúcsa a második gráfban van. Az algoritmus összeszámolja, hogy mennyi ilyen út van két csúcs között, majd végrehajtja a pontszám normalizálását a fokszámok alapján. Szomszédossági mátrixok használatával az ilyen útvonalkeresések igen egyszerűek, mivel a mátrix 𝑛-edik hatványával pontosan a csúcsok között lévő 𝑛 hosszú utak számát kapjuk a mátrix elemeiként. Tehát 𝐺 3 az összesített gráfban lévő 3 hosszú utak számát mutatja az egyes csúcspárok között. Ez még nem garantálja, hogy az útvonal közben bejárt csúcsok a megfelelő gráfban vannak. Ennek biztosításához bevezettem a szűrő mátrixokat: 𝐺1 𝑓𝑖𝑙𝑡𝑒𝑟 = (

𝐼𝑛×𝑛 0𝑘×𝑛

0𝑛×𝑘 0 ) , 𝐺2 𝑓𝑖𝑙𝑡𝑒𝑟 = ( 𝑛×𝑛 0𝑘×𝑘 0𝑘×𝑛

0𝑛×𝑘 ) 𝐼𝑘×𝑘

Ahol 𝐼 a megfelelő méretű identitás mátrix. 𝐺1 𝑓𝑖𝑙𝑡𝑒𝑟 -rel balról szorozva 𝐺-t olyan éleket kapunk, melyek 𝐺1 -ből indulnak, jobbról szorozva pedig olyanokat, melyek 𝐺1 -be érkeznek. Hasonlóan 𝐺2 𝑓𝑖𝑙𝑡𝑒𝑟 -rel balról szorozva 𝐺-t olyan éleket kapunk, melyek 𝐺2 -ből indulnak, jobbról szorozva pedig olyanokat, melyek 𝐺2 -be érkeznek. Ezek alapján azoknak a 3 hosszú útvonalaknak a száma, melyek 𝐺1 -ben indulnak, első lépésben 𝐺1 -ben maradnak, majd 𝐺2 -be lépnek és ott maradnak, a következő művelet szerint számítható: 𝐺1 𝑓𝑖𝑙𝑡𝑒𝑟 ∙ 𝐺 ∙ 𝐺1 𝑓𝑖𝑙𝑡𝑒𝑟 ∙ 𝐺 ∙ 𝐺2 𝑓𝑖𝑙𝑡𝑒𝑟 ∙ 𝐺 ∙ 𝐺2 𝑓𝑖𝑙𝑡𝑒𝑟 = 𝐺1 ∙ 𝑀 ∙ 𝐺2 A szűrő mátrixok hatásaként három mátrix szorzatára egyszerűsödik a képlet. A normalizálást két olyan mátrixszal való szorzással érhetjük, melyek főátlójában az 𝑛edik elem az 𝑛-edik csúcs fokszáma gyökének reciprokja. 1 √𝑑1 0

𝐷1 =

(

0 1

⋮

√𝑑2 ⋮

0

0

⋯

0

…

0

⋱

0 1

0

√𝑑𝑛 )

A fentiek alapján a Narayanan algoritmus által számított pontszámokat a következő mátrix tartalmazza: 𝑠𝑐𝑜𝑟𝑒 = 𝐷1 ∙ 𝐺1 ∙ 𝑀 ∙ 𝐺2 ∙ 𝐷2 29

A mátrix egyes sorai a 𝐺1 gráf egyes csúcsai és a 𝐺2 gráf összes csúcsai közötti pontszámokat mutatja. Ha tehát egy sorban egy elem kiugróan nagy, akkor az adott sor által reprezentált 𝐺1 -beli csúcshoz a legjobb találatot a kiugró elem oszlopa adja meg. Visszafelé pedig, ha egy oszlopban egy elem kiugróan nagy, akkor az adott oszlop által reprezentált 𝐺2 -beli csúcshoz a legjobb találatot a kiugró elem sora adja meg. A Narayanan algoritmus akkor fogad el egy párosítást, ha az mindkét irányban a legjobb találatot jelenti. Ha tehát a 𝑠𝑐𝑜𝑟𝑒 mátrix elemeit egyre változtatjuk, ha az elem mind sorában, mind oszlopában kiugró volt, illetve a többi elemet pedig nullára, akkor megkapjuk az új mappinget. Ezt a műveletet 𝑝𝑒𝑎𝑘-kel jelölöm. Az algoritmus 𝑛-edik iterációjában a mapping: 𝑀𝑛 = 𝑝𝑒𝑎𝑘(𝐷1 ∙ 𝐺1 ∙ 𝑀𝑛−1 ∙ 𝐺2 ∙ 𝐷2 ) Mivel 𝐷1 , 𝐷2 , 𝐺1 , 𝐺2 nem változnak az algoritmus lefutása során, ezért a 𝐷1 ∙ 𝐺1 és 𝐺2 ∙ 𝐷2 szorzatokat csak egyszer kell kiszámolni. Az algoritmus addig fut, amíg 𝑀𝑛 = 𝑀𝑛−1 egyenlőség be nem következik. A közösségi hálózatokat reprezentáló mátrixok ritka mátrixok, ellenben nagyon nagyok.

Ez

a

ritka

mátrixok

soronkénti

vagy

oszloponkénti

kompresszált

ábrázolásmódjával kezelhető. A kiugrás keresése egy oszlopban hosszadalmas művelet, ha soronként van kompresszálva a mátrix, illetve a soronkénti kiugráskeresés is hosszú ideig tart egy oszloponként kompresszált mátrixban. Mivel mindkettőre szükség van, ezért a kiugráskeresés összességében mindenképp lassabb a mátrixos ábrázolásmódban, mint korábban. Ennek ellenére ez a megoldás nem volt felesleges. Új algoritmus készítésekor más hosszúságú illetve más útvonal megkötésekkel rendelkező útvonalak összeszámlálása könnyen megvalósítható, így könnyen lehetett tesztelni az egyes ötleteket, a Grasshopper alapötlete is így született. Mivel az iGraph, a networkx, illetve a mátrixos ábrázolásmód segítségével megvalósított programok futási ideje nagyon nagy volt, illetve nem tudták kezelni a nagy hálózatokat, ezért készítettem egy új keretrendszert Java nyelven.

3.2 Java alapú keretrendszer A keretrendszert Java nyelven készítettem el. A GraphDeanonimization.jar elnevezésben a jar (befőttes üveg) egyrészről a kifejlesztett algoritmusok neveire utal

30

(egy félreértés következtében rovarokról lettek elnevezve), másrészről a kiterjesztést is jelöli. A gráfok kezelésére többféle könyvtár létezik a Java-ban, azonban a dolgozatban tárgyalt algoritmusok szempontjából előnytelenül tárolják azokat. Ezek ugyanis éllistaként reprezentálják a gráfokat, így egy csúcs szomszédjainak lekérdezése hosszú ideig tart, végig kell nézni az összes élet, és amelyekben szerepel a csúcs azonosítója, azokat össze kell gyűjteni. Amennyiben a lista rendezett, úgy a keresés lehet logaritmikus is. A gyorsabb futás érdekében elkészítettem saját gráf osztályomat (Graph). Ebben a gráfot egy rendezett tömbben tárolom, a tömb elemei csúcs osztályúak (Node). Minden csúcs tartalmazza az összes szomszédját a tömbön belüli címével reprezentálva (ami így azonosítóként is használható). Így a több tízezres él-lista végigkeresése néhány memóriacím kiolvasására egyszerűsödik. Ez az adatszerkezetbeli változtatás a korábbiakhoz képest 3-10szeres gyorsulást eredményezett a különböző perturbációktól illetve különböző gráfoktól függően. A rendelkezésre álló hálózatok mind él-listaként érhetőek el, ezért a keretrendszer képes ilyen adatszerkezetű gráfokat beolvasni, illetve kiírni (általában a tgf kiterjesztést használtam). A mérések elvégzéséhez nem elég egy gráf. A rendelkezésre álló gráf alapján kell létrehozni két alkalmas gráfot. Ehhez a [1]-ben taglalt perturbációs eljárást alkalmaztam. Ennek lényege, hogy egy valós közösségi háló segítségével létrehoztam két gráfot, melyek csúcsai és élei között előre meghatározott átfedés van. Ehhez az eredeti gráf, vagyis az ősgráf csúcsait véletlenszerűen három halmazba sorsoltam úgy, hogy a második halmaz, 𝑉𝐵 a teljes méret 𝛼𝑉 -szerese legyen a másik kettő pedig azonos méretű, 𝑉𝐴 és𝑉𝐶 . Ezután 𝑉𝐴 ∪ 𝑉𝐵 halmazba eső csúcsok fogják alkotni 𝐺1 -et, míg 𝑉𝐵 ∪ 𝑉𝐶 halmazba eső csúcsok 𝐺2 -t. Amennyiben két csúcs között az eredeti gráfban volt él, 1−𝛼

azt 𝛽 = 1+𝛼𝐸 valószínűséggel átmásolom a gráfba (𝐺1 -ben és 𝐺2 -ben függetlenül 𝐸

sorsolok). Ennek következtében az élek átfedése 𝛼𝐸 lesz, amennyiben 𝛼𝑉 = 1 (tehát teljes átfedés). Mivel az élek elvesztése miatt a gráfok széteshetnek több különálló részre, ezért ilyenkor a legnagyobb összefüggő részgráfot meghagyva törlöm a többi részt. Ebből kifolyólag 𝛼𝑉 jelentős mértékben eltérhet a tényleges csúcsok közötti átfedéstől.

31

Két csúcs akkor feleltethető meg egymásnak helyesen, ha mindkettő az ősgráf egyazon csúcsától származik. Ebből kifolyólag a lehetséges helyes összerendelések száma 𝑉𝐵 halmaz mérete, ez az úgynevezett groundtruth. Ehhez érdemes viszonyítani az algoritmus eredményeit, ezért ezt külön letárolom, illetve minden csúcsban feljegyzem a csúcsra vonatkozó helyes összerendelést. Annak érdekében, hogy a mérések megismételhetőek legyenek illetve, hogy az egyes perturbációk esetében később más mérési pontokban is lehessen mérni, célszerű elmenteni a perturbációt. Ez a gráfok és a groundtruth kiírásával lehetséges, utóbbit egy csv fájlba képes menteni a keretrendszer. Ez azért is jó, mert így a több magos processzorok hatékonyabb kihasználása érdekében, ha több szálon futtatjuk a keretrendszert párhuzamosan, az egyes szálakon használható ugyanaz a perturbáció. A Narayanan algoritmus első fázisát nem vizsgálom. Ennek eredményét a perturbáció során kinyert groundtruthból hozza létre a keretrendszer. Háromféle seed típust valósít meg. Az első a véletlenszerű seed (Rnd), mely esetében a groundtruthból egyenletes eloszlás szerint választja ki a paraméterként megadott méretű seedet. A második (Rnd25) is véletlenszerű seed, de már csak magasabb fokszámú csúcsokat veszi figyelembe. Ilyenkor a groundtruth elemeit fokszám szerint sorba rendezve a felső 25%-ból sorsol egyenletes eloszlás szerint. Az utolsó, harmadik eljárás (Top) során nincs véletlenszerűség, a legmagasabb fokszámú groundtruthban lévő csúcsok alkotják a seedet. Minden mérési pontban ugyanazon seed mellett futtathatóak az algoritmusok. A keretrendszer lehetőséget nyújt egy futáson belül több mérési pont bejárására. Ez történhet a seed mérete szerint vagy az algoritmusok különböző paraméterei szerint (𝜃, 𝛿). Fontos, hogy az algoritmusok karakterisztikáinak jellemző pontjai környékén mérjünk részletesebben. Ha mindenhol részletesen mérnénk, akkor az nagyon sokáig tartana. Ezért a mérési pontok bejárásához változtatható lépésközök használhatóak. Az egyes futások után a keretrendszer összeveti az algoritmus által generált összerendeléseket a groundtruthszal. Így összeszámolja, hogy mennyi összerendelés helyes (true positive, TP), és hogy mennyi hibás (false positive, FP). Ezeket az értékeket illetve az algoritmus és a perturbáció paramétereit a futási idővel kiegészítve egy csv fájlba menti. Ezt a csv fájlt egy python program dolgozza fel és készít belőle különböző statisztikákat illetve ábrákat.

32

Könnyebb kezelhetőség érdekében minden a keretrendszer indításához szükséges paraméter megadható parancssori argumentumként. Amennyiben ez nincs megadva, úgy egy előre beállított alapérték lesz figyelembe véve. Ez azért praktikus, mert így egy batch fájl segítségével könnyen előkészíthető akár több napnyi mérés. Példa a keretrendszer batch fájlból való indítására: start java -jar GraphDeanonimization.jar seedSize=5-200,5 seedStepRules=20-10,50-50 perturbationNumber=2,5 seedType=Rnd graphName=Epinions Grh=ON Nar=ON Blb=ON theta=0.1-1.0,0.1 saveTasks=ON

A fenti példában a keretrendszer az Epinions nevű gráfot használva az alapértelmezett 𝛼𝐸 = 0.75 és 𝛼𝑉 = 0.5 értékek mellett létrehoz két független perturbációt, majd ezeket elmenti. A Narayanan a Grasshopper és a Bumblebee algoritmusokat futtatja minden mérési pontban 5-ször. A mérési pontok mentén bejárja a 𝜃 = 0.1-től 𝜃 = 1.0-ig terjedő tartományt 0.1-es lépésközzel. Minden 𝜃 pontban bejárja az 5-200 seed méret tartományt, melyen belül az elején 5 a lépésköz, majd 20-tól 10, és 50-től 50. Ezután a mérési paraméterek által meghatározott nevű mappába menti az eredményeket, illetve mérésenként a részeredményeket is, így áramszünet esetén sem vesznek el eredmények.

33

4 A mérések módszertana Méréseim során minden esetben a state-of-the-art algoritmussal való összehasonlítás volt a cél. Ezt úgy lehet a legjobban megvalósítani, ha az egyes algoritmusok és a state-of-the-art algoritmus teljesen azonos körülmények között futnak, majd az így kapott eredményeket hasonlítom össze egy közös szempontrendszer szerint. Az első lépés tehát az azonos futási körülmények biztosítása. Ez akkor valósul meg, ha az algoritmusok ugyanazon gráf ugyanolyan paraméterű perturbációján azonos fajtájú és méretű seeddel futnak. Ennél még jobb, ha nem csak a paraméterek egyeznek, hanem ugyanazon perturbáció és ugyanazon seed mellett futnak az algoritmusok. A 3.2fejezetbenben ismertetett keretrendszer megfelelő paraméterezés mellett ezt biztosítja.

4.1 A támadó eredményének mérése Az algoritmusok által kiadott eredményeket több szempontból vizsgálhatjuk. Ezek között az egyik legfontosabb a helyesen azonosított csúcsok száma. Ezt TP-vel jelölöm (true positive). A seedként megadott párosítások ebbe a halmazba kerülnek, de ez nem az algoritmus érdeme, ezért a seed méretét levontam, a korrigált értékekkel dolgoztam. Mivel a TP érték legfeljebb akkora lehet, mint a groundtruth, ezért érdemes ehhez viszonyítani százalékos megadás esetén. Hasonlóan fontos a hibásan azonosított csúcsok száma. Ezt FP-vel jelölöm (false positive). A teljes hozam magába foglalja mind a helyes, mind a hibásan azonosított csúcsokat. Ezt RC-vel jelölöm (recall). Természetesen fennáll a 𝑅𝐶 = 𝑇𝑃 + 𝐹𝑃 összefüggés. Az egységes skálázás érdekében RC-t és FP-t is a groundtruthhoz viszonyítom. Ebből kifolyólag ezek az értékek meghaladhatják a 100%-ot, bár a gyakorlatban ez nem fordult elő. Két eredmény összehasonlításakor elképzelhető, hogy jobb az, amelyiknél ugyan kisebb a TP, de az FP arányaiban még kisebb. Ennek személtetésére alkalmaztam az FP/RC arányt. Ez azt mutatja meg, hogy a kapott eredmény mekkora hányada hibás, tehát mennyire tiszta a kapott adathalmaz.

34

4.2 Mérések beállításai 4.2.1 Perturbáció erősségének változtatása A perturbációt két paraméter befolyásolja, 𝛼𝐸 és 𝛼𝑉 . Ezek 0 és 1 közötti számok, a kívánt átfedési arányt mutatják az élek illetve a csúcsok között a forrás és cél gráfban. A 10. táblázatban látható, hogy a kívánt átfedés és a tényleges eltérnek egymástól. A csúcsok esetében ez azért van, mert a perturbáció során egyes csúcsok leszakadhatnak, nem kerülnek bele a legnagyobb összefüggő részgráfba. Ritkább hálózatoknál, mint például az Epinions, az eltérés jelentős lehet, sűrűbb hálózatoknál azonban elhanyagolható. Az élek esetében 𝛼𝐸 csak akkor határozza meg az átfedést közvetlenül, ha 𝛼𝑉 = 1. Egyéb esetben az egyes gráfokban nem megjelenő csúcsokhoz tartozó élek úgyszintén nem jelennek meg, így a tényleges átfedés az élek között csökken a következők szerint: 𝛼𝑉 2

𝑒𝑑𝑔𝑒 𝑜𝑣𝑒𝑟𝑙𝑎𝑝 = 𝛼𝐸

1 − 2(

1 − 𝛼𝑉 2 2 )

2𝛼𝑉 2 = 𝛼𝐸 1 + 2𝛼𝑉 − 𝛼𝑉 2

Tényleges átfedés Tényleges átfedés az Csúcsok

Élek

száma

száma

Epinions

75879

LiveJournal

a csúcsok között

élek között

(𝛼𝑉 = 0.5)

(𝛼𝐸 = 0.75, 𝛼𝑉 = 0.5)

405740

35,52%

23,42%

66752

619512

44,62%

23,49%

Slashdot

82168

504230

39,43%

23,66%

fb30k_1

30002

593476

48,95%

23,24%

pkc30k_1

30002

245790

48,93%

24,62%

dblp80k_2

80002

602096

47,51%

23,92%

Név

10. táblázat: A mérésekhez használt gráfok

A fentiek figyelembevételével az első vizsgálati szempont a perturbáció erőssége szerinti mérés. Ehhez 16 különböző perturbációs pontot vettem fel 𝛼𝑉 -t és 𝛼𝐸 -t 0.25 és 1.0 között változtatva 0.25-ös lépésekben. Minden perturbációs pontban 10 mérést végeztem, két perturbáción 5-5 mérést, 1000 méretű Rnd25 seed mellett. Ez igen 35

erős seednek számít, a nagyon erős perturbációk kivételével elegendő az algoritmusok indításához.

4.2.2 Deanonimizációs paraméterek beállítása Méréseim során a következő lépés az algoritmusok paramétereinek beállítása. A state-of-the-art algoritmus rendelkezik egy 𝜃 paraméterrel. Ez az algoritmus mohóságát szabályozza. Az ideális 𝜃 kiválasztása érdekében, 𝜃 változtatásával vizsgáltam a TP, az FP, az RC és az FP/RC értékeket egy megfelelően erős, 100 illetve 150 méretű Top seed mellett, minden mérési pontban 10 különböző perturbáción. Ezután a további mérésekhez rögzítettem 𝜃 értékét. Az új algoritmusok között van olyan is, melynek 𝜃-n kívül más paramétere is van, melyet 𝛿-nak neveztem el. Ebben az esetben hasonlóan jártam el, 𝛿 változtatása utána kiválasztottam a jellegzetes pontokat, majd ezeket rögzítettem (az egyes esetekben ezt ismertetem).

4.2.3 Különböző méretű és típusú seed hatásának vizsgálata A következő vizsgálati szempont az algoritmusok indulásához szükséges seed vizsgálata. 3.2-ban leírtak szerint háromféle seed típussal dolgoztam, ezek a Rnd seed, a Rnd25 seed illetve a Top seed. Mindhárom esetében a seed méretét változtatva vizsgáltam a TP, az FP, az RC és az FP/RC értékeket. Az TP értékekben ilyenkor megfigyelhető

fázisátmenet

jellemzése

érdekében

bevezettem

a

széleskörű

újraazonosítás (large scale propagation, LSP) definícióját. Akkor tekintem úgy, hogy bekövetkezett a széleskörű újraazonosítás, ha az algoritmussal nagyon erős seed mellett elérhető hozam 75%-át már elértük az aktuális seed mellett. Tehát ilyenkor a seed méretét növelve már nem növekszik jelentős mértékben a hozam. A perturbációs eljárás illetve a seed véletlenszerűségei miatt az LSP-hez szükséges seed méret változó, ezt az LSP gyakoriságával jellemeztem az egyes mérési pontokban. Mérési pontonként két perturbáción 5-5 mérést végeztem, mely alól a Top seed kivételt képez determinisztikussága miatt, ahol 10 perturbáción végeztem 1-1 mérést. További kivételt képeznek a nagyon kisméretű (1-20) Rnd és Rnd25 seedek, ahol a pontosabb eredmények érdekében 2-2 perturbáción 50-50 mérést végeztem.

4.2.4 Futási idő mérése Az utolsó vizsgálati szempont az algoritmus futási ideje, illetve ennek skálázódása. Ehhez a LiveJournal hálózat egy 250000 csúcsból álló verzióját vettem 36

alapul, melyből különböző méretű részgráfokat vágtam ki, 10000-től 250000-ig 10000es lépésekben. Ezután az egyes algoritmusok futási idejét mértem. Ilyenkor csak egy szálon futtattam az algoritmusokat, ugyanazon számítógépen. A mérésekhez használt számítógépek: 

Intel(R) Core(TM) i7-4700MQ CPU @ 2.40GHz, 16GB Ram



Intel(R) Xeon(R) CPU E5-2643 v2 @ 3.50GHz, 16GB Ram



Intel(R) Core(TM) i5 CPU 650 @3.20GHz, 8GB Ram

37

5 Grasshopper: Narayanan algoritmus fejlesztése 5.1 Fejlesztési célok Munkám következő részében a Narayanan algoritmus [1] továbbfejlesztésével, ezen belül is az algoritmus második fázisának fejlesztésével foglalkoztam. Érdemes már itt a fejlesztés elején kitűzni a fejlesztés céljait. Akkor tekinthetünk egy algoritmust jobbnak, ha működéséhez elég egy kisebb méretű seed, hozama magasabb, ez a hozam kevesebb FP-t tartalmaz vagy a futási idő kisebb. Mivel a fenti célok nem feltétlenül egyszerre teljesülnek, előfordulhat, hogy az egyik kárára sikerül egy másikat javítani. Fontos tehát kijelölni a fejlesztési célok fontossági sorrendjét. Ez nálam a következőképpen alakult: legfontosabb cél az FP csökkentése, majd a magas hozam elérése, ezután a szükséges seed méretének csökkentése. A futási idő mindaddig másodlagos kérdés, amíg a skálázhatóság megmarad.

5.2 A fejlesztés alapgondolata A Narayanan algoritmusban az egyes csúcsokat a közvetlen szomszédjaik alapján

azonosítjuk.

Tehát

az

úgynevezett

fingerprintjük

(ujjlenyomatuk)

a

szomszédokból áll. A pontosabb eredmények elérése érdekében ezt a fingerprintet terjesztettem ki, a szomszédok helyett a szomszédok szomszédjai jellemzik az egyes csúcsokat. Két csúcs összehasonlításánál a szomszédok szomszédjai alapján osztjuk ki a pontokat. Ez a mátrixos megfogalmazásban a következőt jelenti: 𝑀𝑛 = 𝑝𝑒𝑎𝑘(𝐷1 ∙ 𝐺1 ∙ 𝐺1 ∙ 𝑀𝑛−1 ∙ 𝐺2 ∙ 𝐺2 ∙ 𝐷2 ) Ahol 𝐺1 és 𝐺2 a két gráf szomszédossági mátrixai, 𝐷1 és 𝐷2 a csúcsok fokszáma reciprokjának gyökét tartalmazó főátló mátrixok, 𝑀𝑛−1 és 𝑀𝑛 a mapping iteráció előtti és utáni állapotát leíró mátrixok, míg a 𝑝𝑒𝑎𝑘(… ) művelet a soronként és oszloponként kiugró elemek keresése és a többi elem nullázása. Mivel a közbenső szomszéd kiléte bizonytalan lehet, csak azokat a második szomszédokat vettem figyelembe, ahol a közbenső szomszéd már azonosított. Ilyenkor tehát a mapping által összekapcsolt gráfban öt hosszú útvonalakat keresünk, melyeknél a második és negyedik csúcs a mapping szerint össze van kötve. Ez lehetővé teszi, hogy

38

azokat az utakat, ahol a második és negyedik csúcs azonos, összevonjuk és az utak számának megfelelő súllyal súlyozzuk. Ezt láthatjuk az 11. ábrán.

11. ábra: Útvonalak összevonása, a-b: egy párosításhoz kapcsolódó 5 hosszú útvonalak, c: az 5 hosszú útvonalak összevont változata a párosítás súlyozásával

Az ábra első és második részében egy azonosított csúcspárhoz (kék szaggatott vonal) tartozó 5 hosszú utakat látjuk (piros szaggatott vonal), majd az ábra harmadik részén ezek összevont változatát.

5.3 Súlyozásos helyettesítés A fentiek alapján a fingerprint ilyen módú kiterjesztése megfeleltethető egy hagyományos mapping elemeinek súlyozásával. Ezek a súlyok a vizsgálandó csúcsoktól függetlenül alakulnak ki, csak a mapping elemeinek kapcsolataitól függ. Mivel a magasabb fokszámú csúcsok ilyenkor sokkal nagyobb súlyt kapnak, és így torzítják a súlyozást, a súlyokat normalizáltam, leosztottam a mapping által összekötött két csúcs fokszámának mértani közepével. Ilyen módon az algoritmus két részre bontható. Az elsőben a mapping elemeinek súlyozását hajtjuk végre, majd a másodikban a súlyokat felhasználva a Narayanan algoritmushoz hasonlóan osztjuk ki a pontokat, de a bejárás során nem eggyel növeljük a pontszámokat, hanem az aktuális súllyal.

39

12. ábra: A Grasshopper szerinti pontszámítás

Mivel a súlyozás már tartalmaz egy fokszám szerinti normalizálást, ezért az algoritmus későbbi részéből ezt kihagytam. Az átalakítások után mátrixos megfogalmazásban a következőt kapjuk: 𝑀𝑛 = 𝑝𝑒𝑎𝑘(𝐺1 ∙ ((𝐷1 ∙ 𝐺1 ∙ 𝑀𝑛−1 ∙ 𝐺2 ∙ 𝐷2 ) ∗ 𝑀) ∙ 𝐺2 ) Ahol a ∗ művelet az elemenkénti szorzást jelenti. Mivel 𝑀 kizárólag 1-eseket és 0-ákat tartalmaz, ez a művelet a mappingen kívüli terület kimaszkolását jelenti. Az így kialakított súlyozási metrika egy koszinusz hasonlósági számítást valósít meg. Felfoghatjuk tehát úgy is, hogy azt vizsgáljuk, hogy az egyes összerendelések a mappingben mennyire konzisztensek a többi összerendeléssel, a súlyozásnál az összerendeléssel konzisztens összerendeléseket számoljuk össze. Annak érdekében, hogy az izolált összerendelések ne nulla súllyal szerepeljenek, a számlálás 1-ről kezdődik.

40

Az algoritmus pszeudokódja [12]: funtion Propagate(Gsrc,Gtar,μ) μ ← μ0 repeat (μ,Δ) ← PropagateStep (Gsrc,Gtar,μ) until Δ=0 end function function Propagate(Gsrc,Gtar,μ0) Δ ← 0 ωsrc ← {∀vsrc∈Vsrc: vsrc → 1.0} ωtar ← {∀vtar∈Vtar: vtar → 1.0} for all vsrc ∈Vsrc if ∃μ(vsrc) do for all v’src∈Gsrc.NBRS(vsrc) do if ∃μ(v’src)∈Gtar.NBRS(μ(vsrc)) then α ← SQRT(vsrc.DEGREE()*μ(vsrc).DEGREE()) ωsrc[vsrc] ← ωsrc[vsrc]+1.0/α ωtar[μ(vsrc)] ← ωtar[μ(vsrc)]+1.0/ α end if end for end for η = μ for all vsrc ∈Vsrc do vtc ← BestMatch(Gsrc,Gtar,ωtar,vsrc,μ) if vtc ≠ None then vsc ← BestMatch(Gtar,Gsrc,ωsrc,vtc,μ-1) if vsc = vtc and ((∄μ(vsrc)) or (∃μ(vsrc) ≠vtc)) then η[vsrc] ← vtc Δ ← Δ+1 end if end if end for μ = η return (μ, Δ) end function function BestMatch(Gsrc,Gtar,ω,vi,μ) S ←{} for all vi’∈Gsrc.NBRS(vi) if ∃ μ(vi’) do for all vj’∈Gtar.NBRS(μ(vi’)) do if vj’∉S.keys() then S[vj’] ← 0 end if S[vj’] ← S[vj’]+ ω[vj’] end for end for if S.Size()=0 then return None end if if Eccentricity (S.values()) ≥ Θ then vc ← Pick(∀v∈S.keys() : S[v] = max(S.values())) return vc end if reuturn None end function function Eccentricity(S) return (max(S) – max2(S)) / σ(S) end function

41

5.4 A

Grasshopper

összehasonlítása

a

state-of-the-art

algoritmussal 5.4.1 Perturbáció erősségének változtatása A támadó számára a két gráf adottnak tekinthető, a két gráf csúcsainak és éleinek átfedésén nem tud változtatni. Ezen mérésben tehát azt vizsgálom, hogy a két gráfnak milyen mértékben kell strukturálisan hasonlítani egymásra, hogy a támadás sikeres lehessen. A vizsgált hat hálózat közül két eseten mutatom be az algoritmusok viselkedését. Ezek a hálózatok a LiveJournal és az Epinions, a többi hálózat mindegyike az előző kettő eset valamelyikével hasonló. LiveJournal:

𝛼𝐸 TP

𝛼𝑉

0.25 Nar Grh 0.25 0,10% 1,66% 0.5 0,25% 6,82% 0.75 0,23% 14,46% 1.0 0,22% 20,41%

0.5 Nar Grh 3,89% 12,99% 23,78% 26,70% 33,76% 38,07% 37,56% 47,63%

0.75 Nar Grh 17,25% 22,71% 34,83% 43,41% 39,41% 56,58% 44,62% 63,99%

1.0 Nar Grh 25,34% 29,63% 38,69% 53,82% 74,17% 66,10% 85,41% 72,36%

𝛼𝐸 FP

𝛼𝑉

0.25 0.5 0.75 1.0 Nar Grh Nar Grh Nar Grh Nar Grh 0.25 4,61% 5,61% 4,80% 3,92% 5,48% 3,14% 4,91% 2,78% 0.5 2,11% 3,11% 3,48% 1,37% 2,25% 1,13% 1,55% 1,05% 0.75 1,40% 1,59% 1,70% 0,68% 0,77% 0,39% 0,85% 0,19% 1.0 1,01% 0,79% 0,93% 0,35% 0,39% 0,10% 0,00% 0,00%

𝛼𝐸 FP/RC

𝛼𝑉

0.25 0.5 0.75 1.0 Nar Grh Nar Grh Nar Grh Nar Grh 0.25 29,60% 30,98% 27,88% 15,44% 17,98% 9,34% 13,07% 7,00% 0.5 29,13% 21,00% 11,18% 4,30% 5,53% 2,35% 3,56% 1,80% 0.75 30,23% 8,34% 4,48% 1,66% 1,81% 0,65% 1,10% 0,28% 1.0 30,25% 3,41% 2,30% 0,70% 0,84% 0,16% 0,00% 0,00% 13. táblázat: Narayanan és Grasshopper algoritmusok TP, FP, FP/RC eredményei a LiveJournal hálózaton különböző perturbációs beállítások mellett

Az 13. és 14. táblázatokban láthatóak a Grasshopper és a Narayanan algoritmus eredményei különböző perturbációs paraméterek mellett. Az első táblázatban a TP 42

eredmények, vagyis a helyesen azonosított találatok száma látható a groundtruth méretéhez viszonyítva százalékosan. A második táblázatban a FP eredmények, vagyis a hibásan azonosított találatok száma látható, az előzőekhez hasonlóan a groundtruth méretéhez viszonyítva. Az utolsó táblázat azt mutatja, hogy az algoritmus eredményeként kijövő mapping hány százaléka hibás. A Grasshopper esetében zöld háttérrel jelöltem a kedvezőbb eredményt, pirossal a kedvezőtlenebbet. Epinions:

𝛼𝐸 TP

𝛼𝑉

0.25 Nar Grh 0.25 0,74% 0,73% 0.5 0,70% 4,99% 0.75 0,43% 8,42% 1.0 0,30% 10,54%

0.5 Nar Grh 4,16% 6,21% 16,42% 13,73% 24,15% 17,53% 29,98% 19,43%

0.75 Nar Grh 10,01% 10,23% 25,58% 18,95% 34,29% 22,54% 40,97% 24,73%

1.0 Nar Grh 14,53% 13,26% 30,81% 21,87% 41,85% 26,85% 49,50% 29,37%

𝛼𝐸 FP

𝛼𝑉

0.25 0.5 0.75 1.0 Nar Grh Nar Grh Nar Grh Nar Grh 0.25 4,51% 2,89% 3,32% 0,98% 3,83% 0,58% 4,01% 0,55% 0.5 1,94% 1,05% 2,88% 0,31% 2,65% 0,21% 2,04% 0,14% 0.75 1,13% 0,61% 2,17% 0,18% 1,35% 0,08% 0,60% 0,03% 1.0 0,78% 0,36% 1,69% 0,11% 0,62% 0,04% 0,00% 0,00%

𝛼𝐸 FP/RC

𝛼𝑉

0.25 0.5 0.75 1.0 Nar Grh Nar Grh Nar Grh Nar Grh 0.25 17,70% 12,12% 15,69% 4,70% 15,27% 2,64% 14,07% 2,32% 0.5 17,56% 7,27% 11,64% 1,59% 8,13% 0,91% 5,57% 0,53% 0.75 17,60% 4,36% 7,39% 0,87% 3,54% 0,32% 1,36% 0,10% 1.0 18,31% 2,58% 5,01% 0,52% 1,44% 0,14% 0,00% 0,00% 14. táblázat: Narayanan és Grasshopper algoritmusok TP, FP, FP/RC eredményei az Epinions hálózaton különböző perturbációs beállítások mellett

Mivel az erős perturbáció meggátolhatja az algoritmusok elindulását, ezért kiszürkítettem azokat a mezőket, ahol ez nem történt meg. A maradék mezőket vizsgálva láthatjuk, hogy a Grasshopper a hibaparaméterek tekintetében mindig jobban teljesít. Ez az eltérés szignifikáns egyes perturbációknál, akár egy nagyságrend is lehet. A helyesen azonosított csúcsok száma a két esetben különböző módon viselkedik. A LiveJournal esetében a Grasshopper mindig jobb eredményt produkált a 43

nagyon gyenge perturbációktól eltekintve, míg az Epinions esetében a Narayanan hoz kedvezőbb eredményeket. Ilyenkor a TP érték csökkenéséért cserébe kaphatunk tisztább, hibáktól mentesebb eredményt. A különbség azzal magyarázható, hogy az Epinions hálózat ritkább és ezért érzékenyebb a perturbációra. A fenti táblázatokban pirossal kereteztem az általam életszerűnek vélt perturbációt. Ehhez az 𝛼𝑉 = 0.5 illetve 𝛼𝐸 = 0.75 értékek tartoznak, ami egy elég erős perturbációt jelent. A továbbiakban ezeket a perturbációs paramétereket tekintem alapbeállításnak.

5.4.2 A θ paraméter vizsgálata A Narayanan féle algoritmusban szereplő 𝜃 paraméter egy konstans érték, mely azt határozza meg, hogy az algoritmus milyen mértékű kiugróság mellett fogadjon el egy pontszámot. A paraméter értékének növelésével az algoritmus egyre szigorúbb lesz, így egyre óvatosabb is, míg alacsony 𝜃 mellett az algoritmus mind inkább mohó. A Grasshopperben ezen mechanizmuson nem változtattam, szerepe továbbra is a hozam és a pontosság közötti kompromisszum beállítása. Különbség azonban mégis van a 𝜃 paraméter változtatása mellett, a két algoritmus különböző módon reagál. A következőkben ezt vizsgálom. A méréseket az Epinions és a LiveJournal hálózatokon mutatom be. Seednek a legmagasabb fokszámú csúcsok közül az első 150-et választottam (Top seed). Ez a groundtruth 0.5-0.65%-át teszi ki, mégis elég erős seednek számít a magas fokszámok miatt, így az algoritmus működésében ez nem lesz szűk keresztmetszet. A 15.a és 16.a ábrákon jól látszik, hogy 𝜃 növelése mellett mindkét algoritmus hozama csökken, ahogy ez várható is volt. Egy bizonyos 𝜃 érték felett a korábbiakban meghatározott erős seed sem elég az algoritmusok beindulásához, instabillá válik a működés. A 15.c és 16.c ábrákon látható továbbá, hogy 𝜃 növelésével a hibás összerendelések száma (FP) a Grasshopper esetében csak elhanyagolható mértékben változik, míg a Narayanan esetében a hiba ténylegesen csökkenthető. Azonban mielőtt a Narayanan elérné a Grasshopper értékét, instabillá válik.

44

15. ábra: A LiveJournal hálózatban helyesen és hibásan azonosított párosítások száma (TP, FP, FP/RC) θ függvényében, illetve TP és FP aránya

A 15.b és 16.b ábrákról azt olvashatjuk le, hogy egy hibaérték mellett az egyes algoritmusok mekkora TP értéket tudnak elérni. Illetve visszafelé, egy meghatározott minimális hozamot mekkora hibával tudnak elérni. Ezeken az ábrákon két pont közül mindig a balra és feljebb lévő az előnyösebb. A fenti hibaparamétereken egy másik fontos jellegzetesség is megfigyelhető. A hibák száma a 𝜃 = 0 és a 𝜃 nullától különböző értékei között jelentősen csökken. Érdemes tehát nullától különböző 𝜃 értéket választani, mivel ennek hatására a hozamban csak kis visszaesés történik, de az algoritmus kimenete sokkal tisztább lesz. A 𝜃 további növelése a Grasshopper esetében csak kis javulást hoz a hibák számában, de a hozamot csökkentheti, a Narayanannál pedig csak a hozam drasztikus csökkentése mellett lehet megközelíteni a Grasshopper hibaarányát, ezért a továbbiakban a 𝜃 = 0.1 értéket vettem alapbeálltásnak.

45

16. ábra: Az Epinions hálózatban helyesen és hibásan azonosított párosítások száma (TP, FP, FP/RC) θ függvényében, illetve TP és FP aránya

5.4.3 Különböző méretű és típusú seed hatásának vizsgálata A következőkben a Grasshopper viselkedését vizsgálom különböző méretű és fajtájú seed esetében. A módszertan szerint (4.2.3) három seed fajtát vizsgáltam. Az első a Top seed, mely esetben a legmagasabb fokszámú csúcsok alkotják a seedet. A második a Random seed (Rnd), ebben az esetben a csúcsok közül egyenletes eloszlás szerint sorsoljuk a seed elemeit. Végül a Random25 seed (Rnd25), mely esetben a fokszámok szerint sorba állított csúcsok felső 25%-ból választunk egyenletes eloszlás szerint. Sorrendben a Rnd seed a leggyengébb, majd a Rnd25 seed következik, végül a Top seed a legerősebb.

46

17. ábra: TP eredmények a LiveJournal hálózaton Rnd seed mellett

Az eredményeket most is két tipikus eseten mutatom be, az Epinions illetve a LiveJournal hálózatokon. A LiveJournal estében mért TP eredmények láthatóak az 17. 18. és 19. ábrákon. Az egyes színek az algoritmusokat jelölik, a színes sávok a minimális és maximális értékek közötti intervallumot reprezentálják, míg a középső vonal az átlagértéket jelöli.

18. ábra: TP eredmények a LiveJournal hálózaton Rnd25 seed mellett

47

19. ábra: TP eredmények a LiveJournal hálózaton Top seed mellett

Megfigyelhetjük, hogy az algoritmusok egy bizonyos seed érték alatt nulla közeli hozamot produkálnak. Ilyenkor a seeden kívül csak kevés csúcsról hoznak pozitív, elfogadó döntést. Nagyobb seed méreteknél kis szórással egy érték közelébe állnak be az algoritmusok. Ezekben az esetekben a kezdeti információ elégséges ahhoz, hogy az algoritmusokban lavinaszerűen elinduljon az újraazonosítás, nem a kezdeti információk mennyisége korlátozza az algoritmust, hanem annak milyensége. Ebből következően az egyes eredmények mind vagy a minimum vagy a maximum közelében helyezkednek el. Az átlag vonal azért halad át középen, mert az előző két csoport aránya változik. Látható, hogy a Grasshopper esetében már lényegesen alacsonyabb seed méret mellett minden esetben bekövetkezik a széleskörű újraazonosítás (LSP), ezért volt szükség az x tengely szétbontására több esetben is. Ez az előny csökken az erősebb seed típusoknál, de még a legerősebb, Top seed mellett is jelentős marad. A Narayanan és a Grasshopper sávjai a TP ábrák esetében nem érintkeznek, tehát a Grasshopper a legrosszabb esetekben is kedvezőbb eredményekkel szolgált, mint a Narayanan. Az FP értékeket csak ott érdemes vizsgálni, ahol volt széleskörű újraazonosítás, ezeken a helyeken ismét csak a Grasshopper eredményei jobbak.

48

20. ábra: TP eredmények az Epinions hálózaton Rnd seed mellett

Amennyiben a hálózat ritkább, illetve érzékenyebb a perturbációra, olyankor a fenti viszonyok részben megfordulhatnak. Ezt az Epinions hálózaton mutatom be.

21. ábra: TP eredmények az Epinions hálózaton Rnd25 seed mellett

A legszembetűnőbb különbség, hogy a Grasshopper itt már alacsonyabb TP értékeket produkált. Eközben az alacsony seed igény és az alacsony hiba megmaradt. Mivel a hiba arányaiban is kisebb, ezért az ilyen ritkább hálózatok esetén is előnyösebb lehet a Grasshopper.

49

22. ábra: TP eredmények az Epinions hálózaton Top seed mellett

5.4.4 Stabilitási tartományok vizsgálata A 4.2.3 fejezetben lévő LSP definíció segítségével három részre oszthatjuk a seed méret tartományt. A kezdeti szakaszon egy mérés esetében sem következett be széleskörű újraazonosítás. Ezt követően az esetek egy részében elérjük az LSP állapotot, de nem mindig. Ilyenkor beszélünk instabil működésről. Végül az utolsó tartományban minden esetben elérjük az LSP állapotot, ez a stabil működési tartomány.

23. ábra: Az instabil működési tartomány alsó határa

50

Fontos jellemzője az algoritmusok e három tartományának határa. Ilyen téren a Grasshopper jelentős javulást ér el. Top seed esetében 10 seedtől már instabilan indulhat az algoritmus és 18-tól stabilan működik, ez a Narayanan esetében 50 illetve 65. Rnd25 seednél nagyobb különbséget láthatunk, míg a Grasshopper esetében a határok 5 és 20, a Narayanan instabil tartományának alsó határa 400-ra, a stabil tartomány alsó határa pedig 600-ra tolódik ki. A leggyengébb, Rnd seed esetében már a Grasshopper határai is megnőnek, 8-ra illetve 55-re, míg a Narayanan határai 1300 és 2000. Az 23. ábrán mindkét tengelyen az instabil működéshez szükséges minimális seed méret látható, a függőleges tengelyen a Grasshopper, a vízszintes tengelyen a Narayanan algoritmus esetében. A különböző színek az egyes vizsgált hálózatokat jelölik, míg a pontok formája a seed típusát. A nagyságrendbeli eltérések szükségessé tették a logaritmikus skála alkalmazását. A sötétzöld átlós vonal az azonos értéket jelöli, a sávok egy-egy nagyságrendnyi javulást a Narayanan féle algoritmushoz képest. A 24. ábrán hasonló ábrázolásban látható a stabil működéshez szükséges seed mérete. Itt is legalább egy nagyságrendnyi javulás látható.

24. ábra: A stabil működési tartomány alsó határa

5.4.5 Futási idő mérése A Grasshopper nyilvánvaló hátránya a nagyobb számítási igény és ilyen módon a nagyobb futási idő. A lényegi különbséget a súlyozás számítása adja. Súlyozást a 51

Grasshopperben mindig csak a már azonosított csúcsokra számolok, ennek maximuma a kisebbik gráf mérete, de tipikusan kevesebb ilyen csúcs van. Egy súly kiszámítása, mivel egy koszinusz hasonlóságot valósít meg a számítás, hasonló ideig tart, mint a legjobb találatok keresése a Narayanan algoritmusban. Ezért olyan, mintha az azonosított csúcsokat kétszer vizsgálnánk. Ez konstansszoros futási időnövekedést von maga után. Mivel a jó skálázhatóság alapvető követelmény, ezért a futási időt ilyen szempontból mértem. A LiveJournal hálózatból különböző méretű részgráfokat vágtam ki, majd ezeket alapul véve végeztem el a méréseket. Seed gyanánt egy erős, Top seedet használtam, a stabil működés alsó határánál (kisebb biztonsági tényezővel). Erre azért volt szükség, mert ha nem indul el az algoritmus, akkor a futási idő minimális és ez torzíthatja az eredményeket.

25. ábra: Futási idő a LiveJournal hálózaton a kiindulási gráf méretének függvényében milliszekundumban mérve

Ahogy várható volt, az algoritmusok nagyjából lineárisan skálázódnak. A mért eredmények mérési pontonként jelentősen változhatnak, ráadásul az egyes pontokban a szórás is jelentős. Előbbire valószínűleg az a magyarázat, hogy a gráf struktúrájából fakadóan különböző módon reagál a különböző méretű részgráfok kivágására, de ez még további vizsgálatra szorul. Utóbbi abból fakad, hogy az algoritmusok sokszor úgy 52

érik el a leállási feltételt, hogy a széleskörű újraazonosítás után még pár iterációban találnak néhány új párosítást, de a RC nem nő jelentősen, tehát a konvergencia itt már igen kicsi. Ezek az iterációk a kevés RC növekedés ellenére futási időben azonos nagyságrendűek.

53

6 A Bumblebee algoritmus A következő fejezetben a Narayanan algoritmus egy másik fejlesztését mutatom be. Ehhez felhasználom a Grasshopper megalkotása során szerzett tapasztalatokat és mérési eredményeket.

6.1 Elfedési jelenségek bemutatása A Narayanan algoritmus a csúcsok hasonlóságát jellemző pontok számítása végén ezt a pontszámot normalizálja, a jelölt csúcs fokszámának gyökével leosztja. Ennek célja, hogy a kis fokszámú csúcsok ne kerüljenek hátrányba.

26. ábra: A nagy fokszámú A és a kis fokszámú B csúcs osztozik a mapping két elemén

A 26. ábrán lévő példában az 𝐴 és 𝐵 csúcsoknak az 𝐴′ illetve 𝐵 ′ csúcsok felelnek meg. 𝐴 fokszáma 100, 𝐵 fokszáma 2. 𝐴 szomszédjai közül 14-et már azonosított az algoritmus (vagy a seed részét képezték), 𝐵 mindkét szomszédja azonosítva van, ezek a szomszédok közösek 𝐴-val. Az egyszerűség kedvéért az elrendezés szimmetrikus. Ez akkor fordulhat elő, ha lokálisan, a gráf egy részén vagy 54

globálisan, a teljes gráfon nincs perturbáció. Ilyenkor 𝐴 és 𝐴′ csúcsok azonos strukturális környezetben vannak (ez 𝐵 és 𝐵 ′ csúcsokra is igaz). A Narayanan algoritmus hasonlósági metrikája ennek ellenére ezeket a csúcsokat nem rendeli össze. Grasshopper (egységnyi súlyokkal)

Narayanan 𝐴

𝐵

𝐴

-

-

𝐵

-

-

14

2

√100

√2

2

2

√100

√2

𝐴′ 𝐵′

𝐴′

𝐵′

14

2

√100

√2

2

2

√100

√2

-

-

Legjobb

Legjobb

𝐴

𝐵

𝐴′

𝐵′

𝐵′

-

-

14

2

𝐴′

𝐵′

-

-

2

2

-

-

𝐵

14

2

-

-

𝐴

-

𝐵

2

2

-

-

-

találat

találat

27. táblázat: A Narayanan és a Grasshopper találatai a nagy fokszámú A és a kis fokszámú B csúcs esetén

A 27. táblázatban láthatóak az egyes csúcsok közötti pontszámok illetve a csúcsokhoz a hasonlósági metrika alapján leghasonlóbb csúcs. A normalizálás miatt a kis fokszámú csúcsok könnyen kitakarhatják a nagy fokszámú csúcsokat. Bármely csúcs, mely szomszédjai között ott van 𝑀13 és 𝑀14 , csak akkor azonosítható, ha egymás között pontszámaik nagyobbak, mint 𝐵 − 𝐵 ′ pontszáma (√2). Ez 𝑛 fokszám esetén √𝑛 ∙ 2 már azonosított szomszédot tesz szükségessé. A Grasshopper esetében a súlyozás közben lévő normalizálás miatt a csúcsok közötti pontszámokat nem normalizáltam. A 27. táblázatban szerepelnek ezek a pontszámok is. A mapping súlyait az egyszerűség kedvéért egységnyinek választottam. Ilyenkor a nagy fokszámú csúcsok kerülnek előnybe. A példában 𝐵 csak akkor lehetne azonosítható, ha lenne még azonosított szomszédja és az nem esne 𝑀1 − 𝑀14 -be. Összességében tehát azt láthatjuk, hogy normalizálás esetén a kis fokszámú csúcsok elfedik a nagy fokszámúakat, normalizálás nélkül pedig a nagy fokszámúak fedik el a kis fokszámúakat. Szükség volna tehát egy olyan normalizálásra, mely adott

55

fokszámú csúcs esetén előnyben részesíti a hasonló fokszámú csúcsokat, de a nagy eltérést bünteti.

6.2 Az algoritmus működése, új normalizálási eljárás A 2.1.1 fejezethez hasonlóan legyen a két gráf 𝐺1 = (𝑉1 , 𝐸1 ) és 𝐺2 = (𝑉2 , 𝐸2 ), a két összehasonlítandó csúcs pedig rendre 𝑢 ∈ 𝑉1 és 𝑣 ∈ 𝑉2 . Illetve legyen 𝑉𝑛𝑏𝑟 v szomszédjainak halmaza 𝑉2–ben, 𝑈𝑛𝑏𝑟 u szomszédjainak halmaza 𝑉1-ben, míg 𝑈𝑛𝑏𝑟 ′ az 𝑈𝑛𝑏𝑟 elemeihez párosított 𝑉2–ben lévő csúcsok halmaza. Ilyenkor az új normalizálás mellett a pontszám: 𝛿

|𝑉𝑛𝑏𝑟 ∩ 𝑈𝑛𝑏𝑟

′

|𝑉𝑛𝑏𝑟 | |∗( ) , ℎ𝑎 |𝑉𝑛𝑏𝑟 | < |𝑈𝑛𝑏𝑟 | |𝑈𝑛𝑏𝑟 |

|𝑉𝑛𝑏𝑟 ∩ 𝑈𝑛𝑏𝑟 {

′

|𝑈𝑛𝑏𝑟 | |∗( ) , ℎ𝑎 |𝑉𝑛𝑏𝑟 | > |𝑈𝑛𝑏𝑟 | |𝑉𝑛𝑏𝑟 |

𝑠𝑐𝑜𝑟𝑒(𝑣, 𝑢) =

𝛿

Ahol 𝛿 az algoritmusnak paraméterként megadható konstans. A zárójelben lévő rész mindig kisebb vagy egyenlő, mint egy. Akkor lesz egyenlő eggyel, ha a két összehasonlított csúcs fokszáma azonos. 𝛿 ≠ 0 esetén, ha a két fokszám különbözik, akkor egy egynél kisebb számmal lesz beszorozva a pontszám, nagyobb eltérés esetén kisebb lesz ez a szám. 𝛿 = 0 esetén mindenképp eggyel szorzunk, tehát olyan, mintha nem is lenne normalizálás. A szorzó értékét különböző 𝛿 értékek esetén a 28. ábra mutatja.

28. ábra: A fokszám arányokhoz tartozó normalizáló szorzók különböző 𝜹 értékek mellett

56

Látható, hogy kisebb 𝛿-k esetén a fokszám eltéréseket jobban tolerálja, nagyobb 𝛿-k esetén pedig egyre súlyosabban bünteti. Az ilyen normalizálással készített algoritmust a Bumblebee nevet kapta. Az algoritmus pszeudokódja ([1] alapján): function propagationStep(lgraph, rgraph, mapping) for lnode in lgraph.nodes: scores[lnode] = matchScores(lgraph,rgraph,mapping,lnode) if eccentricity(scores[lnode]) < theta: continue rnode = (pick node from rgraph.nodes where scores[lnode][node] = max(scores[lnode])) scores[rnode] = matchScores(rgraph,lgraph,invert(mapping), rnode) if eccentricity(scores[rnode]) < theta: continue reverse_match = (pick node from lgraph.nodes where scores[rnode][node] = max(scores[rnode])) if reverse_match != lnode: continue mapping[lnode] = rnode function matchScores(lgraph, rgraph, mapping, lnode) initialize scores = [0 for rnode in rgraph.nodes] for (lnbr, lnode) in lgraph.edges: if lnbr not in mapping: continue rnbr = mapping[lnbr] for (rnbr, rnode) in rgraph.edges: if rnode in mapping.image: continue scores[rnode] += 1 for (lnode, lnbr) in lgraph.edges: if lnbr not in mapping: continue rnbr = mapping[lnbr] for (rnode, rnbr) in rgraph.edges: if rnode in mapping.image: continue scores[rnode] += 1 for (rnode, s) in scores: if rnode.degree > lnode.degree: s = s * (lnode.degree/rnode.degree)^delta else: s = s * (rnode.degree/lnode.degree)^delta return scores function eccentricity(items) return (max(items) - max2(items)) / std_dev(items) until convergence do: propagationStep(lgraph, rgraph, seed_mapping)

57

6.3 A

Bumblebee

összehasonlítása

a

state-of-the-art

algoritmussal és a Grasshopperrel 6.3.1 A δ paraméter beállítása A Bumblebee elkészítésekor nem határoztam meg 𝛿 értékét, paraméterként hagytam. A konkrét mérésekhez azonban konkrét 𝛿 értékekre van szükség. Ennek érdekében egy erős seed mellett 𝛿 értékét változtatva vizsgáltam az algoritmus TP, FP és FP/RC eredményeit. A támadónak több célja is lehet. Ezek közül az egyik a minél magasabb találati arány.

29. ábra: Helyesen azonosított csúcsok száma az Epinions hálózaton δ változtatása mellett

Ahogy a 29. ábrán is látszik, ehhez a találati arányhoz tartozik egy optimális 𝛿 érték. Ez az érték hálózatonként kismértékben változó, nagyjából a 𝛿 = 0.5 pontnál van. A többi hálózaton mért eredmények a függelékben találhatóak. Az algoritmus e verzióját Blb0.50-nek neveztem el.

58

30. ábra: Hibásan azonosított csúcsok száma az Epinions hálózaton δ változtatása mellett

Egy másik célja a minimális hiba lehet a támadónak. Ahogy a 30. ábrán látható, minél kisebb 𝛿, annál kisebb a hiba is, viszont 𝛿 nem lehet 0-nál kisebb, mert akkor a csúcsok fokszámai közötti eltérést már nem büntetné, hanem jutalmazná az algoritmus. Ezért ebben az esetben 𝛿 = 0 értéket állítottam be és ezt a verziót Blb0.00-nak neveztem el.

31. ábra: Hibásan azonosított csúcsok száma és a hozam aránya az Epinions hálózaton δ változtatása mellett

59

Elképzelhető az is, hogy a támadó a nagy hozam és a hibamentes eredmény között szeretne egy kompromisszumot. A 31. ábrán az látható, hogy a hozam mekkora része hibás (tehát nem a groundtruth méretéhez van viszonyítva). Természetesen a kisebb érték a kedvezőbb. A legkisebb érték az előzőekben tárgyalt 𝛿 = 0 értéknél van. Azonban a görbe nem szigorúan monoton, így van másik lokális minimumpontja. Ez a pont alkalmas lehet a kompromisszum megvalósítására. A lokális minimumpont előtt 𝛿 növelése mellett a helyesen azonosított csúcsok száma gyorsabban növekszik, mint a hibásan azonosítottaké. Az optimális 𝛿 ebben az esetben is hálózatonként kismértékben változik, nagyjából a 𝛿 = 0.01 pontnál van, ezért ezt a verziót Blb0.01-nek neveztem el.

6.3.2 Perturbáció erőssége szerinti mérések A 4.2.1 fejezethez hasonlóan, itt is a perturbáció erősségét befolyásoló 𝛼𝑉 és 𝛼𝐸 paraméterek változtatása mellett mértem a TP, FP és FP/RC értékeket. Mivel minden mérési pontban öt különböző algoritmus eredményeit hasonlítom össze, ezért a táblázatos megjelenítés nem áttekinthető. A 32. ábrán a különböző algoritmusok TP eredményei láthatóak. Mivel az igen erős seed (Rnd25 típusú, 1000 méretű seed) sem volt minden esetben elég a széleskörű újraazonosításhoz, ezért ezeken a helyeken az oszlopokat kiszürkítettem. A perturbáció hatására fellépő tényleges átfedést az élek illetve a csúcsok között az ábrák mellett zárójelben tüntettem fel. A 𝛿 paraméter beállításakor az egyik lehetséges cél a TP érték maximalizálása volt. Az erre optimalizált Bumblebee verzió, vagyis a Blb0.50 jól láthatóan minden perturbációs pontban a legmagasabb TP eredményeket produkálta. Érdemes még észrevenni, hogy a Blb0.00 együtt mozog a Grasshopperrel. Ez várható volt, mivel a 𝛿 = 0 mellett a Bumblebee pont a Grasshopper normalizálását valósítja meg, csak éppen a mapping súlyozása nélkül. Hasonlóan, a Blb0.01 kis lemaradással, de követi Blb0.50 értékeit.

60

32. ábra: Narayanan, Grasshopper és Bumblebee algoritmusok TP eredményei különböző perturbációs beállítások mellett

A Bumblebee mindhárom verziójára igaz, hogy erősebb perturbáció hatására kisebb mértékben csökkennek a TP értékek, mint a Narayanan esetében. Ez azt eredményezi, hogy a Narayanan algoritmus gyengébb perturbációknál megjelenő előnye a

hibaminimalizáló

Blb0.00-val

szemben

fokozatosan

eltűnik

a

perturbáció

erősödésével. A 33. ábrán az FP eredmények láthatóak. A nem releváns eredményeket itt is kiszürkítettem. Látható, hogy erős perturbációk hatására a Blb0.50 algoritmus nagyon sok hibát produkál. A Blb0.01 ezt is követi, de itt a hiba mindig jelentősen kisebb.

61

A Blb0.00 esetében a cél a hibák minimalizálása volt. Ez oly mértékben sikerült, hogy még a Grasshopper rendkívül alacsony hibaértékeinél is minden esetben jobbat produkált.

33. ábra: Narayanan, Grasshopper és Bumblebee algoritmusok FP eredményei különböző perturbációs beállítások mellett

A 34. ábrán az algoritmusok által produkált eredmények tisztaságát láthatjuk. A szinte hibamentes Blb0.00 és Grasshopper természetesen ebben a mutatóban is a legjobb eredményekkel rendelkeznek. A Blb0.01 esetében a 𝛿 = 0.01 egy kompromisszumos megoldás volt a TP növelése és az FP/RC érték alacsonyan tartása

62

között. A fenti eredmények alapján ezt tekinthetjük sikeresnek, mivel a Blb0.01 amellett hogy FP/RC értékekben a Narayanan algoritmussal hasonló, TP értékekben jobb. Ahogy az 5.4.1 fejezetben szerepel, továbbra is az 𝛼𝐸 = 0.75 illetve 𝛼𝑉 = 0.5 értékekhez tartozó perturbációt tartom életszerűnek. A továbbiakban ezeket a perturbációs paramétereket tekintem alapbeállításnak.

34. ábra: Narayanan, Grasshopper és Bumblebee algoritmusok FP/RC eredményei különböző perturbációs beállítások mellett

63

6.3.3 A θ paraméter vizsgálata A 𝜃 paraméternek a Bumblebee algoritmusban is a mohóság beállítása a szerepe, vagyis a nagy hozam és a kis hiba közötti kompromisszumot ezzel állíthatjuk be. Nagy 𝜃 esetén kevesebb hibát illetve kisebb hozamot várunk. A Bumblebee algoritmus ilyen jellegű viselkedését vizsgálom a következőkben. A 4.2.2 fejezet szerint ezt úgy végzem, hogy egy erős seed (Top típusú, 150 méretű) mellett, mely garantálja a széleskörű újraazonosítás elindulását, 𝜃-t változtatva mérem az algoritmus TP, FP és FP/RC eredményeit. A dblp80k_2 hálózat esetében Narayanan algoritmussal ez a seed sem volt elegendő, ezért itt ezek az adatok hiányoznak. Ahogy azt az 24. ábra is mutatja, a stabil indításhoz nagyjából 2000 méretű seed lett volna szükséges, ez viszont már erősen torzította volna a méréseket. A Bumblebee tulajdonságait az Epinions és a LiveJournal hálózatokon mutatom be. A többi hálózat mérési eredményei a függelékben találhatóak.

35. ábra: TP, FP és FP/RC eredmények az Epinions hálózaton a θ paraméter változtatása mellett

64

A 35.a és 35.c ábra igazolja várakozásainkat a hozam és a hiba közötti kompromisszum tekintetében. A Blb0.50 és a Blb0.01 FP értékei 𝜃 növelésével jelentősen csökkenthetőek, akár elérhetik a Blb0.00 és a Grasshopper hibaszintjét is. Az eközben bekövetkezett hozamveszteség felméréséhez egyszerre kell vizsgálni a TP és FP értékeket. Ez a 35.b ábrán látható. Itt két pont közül mindig a balra és feljebb lévő az előnyösebb. Látható, hogy rögzített FP vagy TP érték mellett megfelelő 𝜃 választásával a Blb0.50 mindig jobb eredményt produkál, mint a többi algoritmus. Sorrendben ezután a Grasshopper, a Blb0.00, majd a Blb0.01 végül a Narayanan következik.

36. ábra: TP, FP és FP/RC eredmények a LiveJournal hálózaton a θ paraméter változtatása mellett

Ez a sorrend más hálózatok esetében változhat, ahogy ezt a 36.b ábrán láthatjuk. Itt látható, hogy egyes szakaszokon a Grasshopper, máshol a Blb0.00 megint máshol a Blb0.01 vagy éppen a Blb0.50 a legideálisabb. Ebből kifolyólag ezeknek mind van létjogosultsága. A Narayanan algoritmus sehol sem tör az élre, minden helyzetben van jobb alternatíva. 65

A továbbiakban a korábbi mérésekkel való konzisztencia érdekében a 𝜃 = 0.1 értéket tekintem alapbeállításnak.

6.3.4 Különböző méretű és típusú seed hatásának vizsgálata A Bumblebee esetében is változhat a széleskörű újraazonosításhoz szükséges seed mérete hálózatonként és seed típusonként. A következőkben ennek mikéntjét vizsgálom.

37. ábra: TP értékek az Epinions hálózaton különböző méretű Rnd25 seed mellett

A 37. ábrán látszik, hogy a Grasshopperhez hasonlóan a Bumblebee-nek is csak egy igen kisméretű seedre van szüksége. A Blb0.00 esetében a szükséges seed méretek a Grasshopperével megegyeznek, a fázisátmenet hasonlóan zajlik le. A két görbe együtt mozog, de a Blb0.00 végig alacsonyabb hozamot produkál. A Blb0.50 és a Blb0.01 esetében szignifikáns a változás az előzőekhez képest. Már akkor is van esély a széleskörű újraazonosításra, ha csak egyetlen párosításból áll a seed. Nincsen tehát olyan szakasza a seed méret tartománynak, melynél biztosan nem indulnak el ezek az algoritmusok. Ebből kifolyólag a fázisátmenet sem valósul meg teljesen, hiányzik az első fázis. Azonban továbbra is érvényes, hogy a stabil működéshez szükséges seed méret felett a helyesen azonosított csúcsok száma nem változik. A görbék gyenge lejtése a TP értékek seed mérettel való kompenzálásával magyarázható.

66

38. ábra: Széleskörű újraazonosítás gyakorisága az Epinions hálózaton különböző méretű Rnd25 seed mellett

A 4.2.3 fejezet alapján a legjobb elért hozam 75%-ától számítom a széleskörű újraazonosítás bekövetkeztét. Ez látható a 38. ábrán. A Blb0.01 egyetlen párosításból álló seed esetén 19%, a Blb0.50 pedig 61% eséllyel indul el. Ezek az értékek a különböző hálózatok esetén változhatnak, a függelékben szerepel az összes mérési eredmény.

39. ábra: FP értékek az Epinions hálózaton különböző méretű Rnd25 seed mellett

A hibásan azonosított csúcsok száma, ahogy az a 39. ábrán is látható, a stabil működéshez szükséges seed méret felett a seed méretétől független. A Grasshopper és a Blb0.00 továbbra is a legjobb eredményeket mutatják. A Blb0.01 és a Narayanan esetében az is megfigyelhető, hogy ha nem következik be a széleskörű újraazonosítás, akkor az eredményben kevesebb hiba szerepel. Ezek az értékek az átlagot lehúzzák. A 67

kevés hiba ezeken a szakaszokon azonban nem jelent előnyt, hiszen a TP értékek nagyon kicsik. A Blb0.50 az előzőekkel ellentétben, ha nem következik be a széleskörű újraazonosítás, akkor több hibát produkál, mint ha bekövetkezik. Ez a görbe kezdeti szakaszán jelent egy emelkedést, azonban ez megint csak nem releváns. Amennyiben az algoritmus elindul az instabil tartományban, akkor eredményei mind TP, mind FP tekintetében a stabil szakaszon mutatott eredményekkel azonosak.

40. ábra: FP/RC értékek az Epinions hálózaton különböző méretű Rnd25 seed mellett

A 40. ábra az algoritmusok eredményeinek tisztaságát mutatja. A kezdeti szakaszon látható igen magas hibaarány annak köszönhető, hogy itt a stabil tartománynál magasabb a hibák száma, ellenben sokkal alacsonyabb a helyesen azonosított csúcsoké.

6.3.5 Futási idő mérése Mivel a Bumblebee működése szerkezetileg nagyon hasonló a Narayanan algoritmuséval, ezért az iterációnkénti futási időt azonosnak várjuk. A különbség a normalizálásnál jelentkezik, ahol egy gyökvonás és egy osztás helyett egy osztás egy hatványozás és egy szorzás szerepel. Ez még nem indokolna nagy eltérést a végleges futási időben.

68

41. ábra: Futási idő a LiveJournal hálózaton a kiindulási gráf méretének függvényében milliszekundumban mérve

A futási idő értéke az iterációnkénti futási idők összege, ezért az is jelentősen befolyásolja a végeredményt, hogy mennyi iterációra van szükség a konvergencia eléréséhez. A mérések azt mutatják, hogy a Bumblebee lineárisan skálázódik a gráf méretével, a futási időben nincs akkora ingadozás, mint a Narayanan vagy a Grasshopper esetében, illetve ezeknél mindig gyorsabb volt.

69

7 Összefoglalás A dolgozat célja deanonimizációs algoritmusok vizsgálata és fejlesztése volt. Ennek jegyében a dolgozat elején a probléma felvezetése után bemutattam az irodalomban fellelhető algoritmusok közül négy jelentősebbet. Ezek közül kerestem a legjobbat, ami nem szorul speciális körülményekre, általános esetben is működőképes, nagy hálózatokon is működik, illetve széleskörű újraazonosítást teszt lehetővé. Az így kiválasztott state-of-the-art algoritmus, vagyis a Narayanan algoritmus vizsgálatára és más algoritmusokkal való összehasonlítására kidolgoztam egy mérési módszertant, melyben valós közösségi hálókon mérem az algoritmusok különböző tulajdonságait. Ehhez létrehoztam egy keretrendszert, mely képes ezekből a valós hálózatokból egy perturbációs eljárás segítségével két hálózatot létrehozni, melyeken már futtathatóak az algoritmusok. A keretrendszerbe bekerült a Narayanan algoritmus, illetve minden új algoritmus implementálásra került, melyeket a state-of-the-art algoritmus fejlesztéseként hoztam létre. Az első ilyen fejlesztés a Grasshopper volt. Itt kidolgoztam egy eljárást, mely a két gráf közötti összerendeléseket súlyozza úgy, hogy a biztosabb összerendeléseknek nagyobb súlyt ad, a bizonytalanoknak kisebbet. A második fejlesztésben a Narayanan hasonlósági metrikájában lévő normalizálási eljárást alakítottam át úgy, hogy a hasonló fokszámú csúcsok előnyt élvezzenek, a jelentősen eltérő fokszámúak pedig hátrányt. Méréseim során vizsgáltam az algoritmusok viselkedését a hálózatok különböző perturbációs szintjein. Majd vizsgáltam az algoritmusok mohóságát befolyásoló 𝜃 paraméter hatását, illetve a különböző típusú és méretű seedek hatását. Végül a futási idő skálázhatóságát ellenőriztem le. Az eredményekből kiderül, hogy a Grasshopper jelentősen javított a Narayanan algoritmus hibaarányán. Ez a hiba már annyira kicsi volt, hogy a 𝜃 paraméter állításával sem lehetett jelentősen csökkenteni. Az algoritmus indításához szükséges seed mérete a Narayanannál mértekhez képest egy, néhol két nagyságrenddel csökkent. Mindeközben a futási idő nőtt ugyan, de még mindig lineáris viszonyban maradt a gráf méretével.

70

A Bumblebee esetében a normalizálásban szereplő 𝛿 paraméter szerint három verzió hoztam létre. Ezek a támadó különböző lehetséges céljai szerint vannak optimalizálva. A mérések azt mutatták, hogy a hozamra fókuszáló verzió jelentős növekedést tudott elérni a helyesen azonosított csúcsok számában, de ennek a hibák növekedése volt az ára. A hibamentességre fókuszáló verzió a Grasshopper hibaarányát is tovább tudta csökkenteni. A harmadik verzió jó alternatíva a hiba és a hozam közötti kompromisszumban. Továbbá bemutattam, hogy ha a támadó célja egy konkrét hozam elérése, akkor a 𝜃 paraméter megfelelő beállítása mellett a Bumblebee adja a legkevesebb hibát, illetve egy konkrét maximális hibaérték mellett a megfelelő 𝜃-val a Bumblebee adja a legnagyobb hozamot. Bár az előzőek is igen jelentős javulást jelentenek, a Bumblebee legnagyobb előnye, hogy akár egyetlen összerendelésből álló seed esetén is képes lehet elindulni, akár Rnd seed esetén is. Ennek valószínűsége a seed méretével meredeken nő, Rnd seed estében 10 és 25 között, Rnd25 seed esetében 8 és 15 között, Top seed esetében 3 és 5 között éri el 100%-ot. Ez azt jelenti, hogy az összes eddig vizsgált hálózaton a mindössze 5 összerendelésből álló Top seed minden esetben elegendő volt az algoritmus indításához. A jövőben további fejlesztéseket tervezek megvalósítani. Ezek között szerepel a leállási feltétel javítása a konvergencia gyorsabb elérése érdekében, mivel ezek az algoritmusok az utolsó iterációkban már csak kevés új azonosítást találnak. Továbbá a Bumblebee alacsony seed igénye lehetővé teheti, hogy új seed keresési eljárást dolgozzunk ki, mely kevesebb összerendelést hoz, de robusztusabb. Harmadik jövőbeni fejlesztés lehet a jelenleg fixen tartott paraméterek, mint a 𝜃 vagy a 𝛿, futási időben történő dinamikus változtatása. Így az algoritmus a futás elején mohóbb lehet a könnyű indítás miatt, majd később óvatosabb lesz az alacsony hibaarány érdekében. Az algoritmusok bemenete és kimenete azonos formátumú, ezért láncba lehet kötni őket. Például a Bumblebee eredményét adjuk a Grasshopper bemeneteként. Az ilyen módon létrehozott hibrid algoritmusok is ötvözhetik az alacsony seed igényt az kis hibaaránnyal.

71

Irodalomjegyzék [1]

Narayanan, Arvind, and Vitaly Shmatikov. "De-anonymizing social networks." Security and Privacy, 2009 30th IEEE Symposium on. IEEE, 2009.

[2]

Peng, Wei, et al. "A Two-Stage Deanonymization Attack against Anonymized Social Networks." (2012): 1-1.

[3]

Pedarsani, Pedram, Daniel R. Figueiredo, and Matthias Grossglauser. "IC, EPFL, Switzerland." Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on. IEEE, 2013.

[4]

Bringmann, Karl, Tobias Friedrich, and Anton Krohmer. "De-anonymization of Heterogeneous Random Graphs in Quasilinear Time." Algorithms-ESA 2014. Springer Berlin Heidelberg, 2014. 197-208.

[5]

Narayanan, Arvind, Elaine Shi, and Benjamin IP Rubinstein. "Link prediction by de-anonymization: How we won the kaggle social network challenge." Neural Networks (IJCNN), The 2011 International Joint Conference on. IEEE, 2011.

[6]

Kuhn, H. W. "The Hungarian method for the assignment problem." Naval Research Logistics (NRL) 52.1 (2005): 7-21.

[7]

Aiello, William, Fan Chung, and Linyuan Lu. "A random graph model for massive graphs." Proceedings of the thirty-second annual ACM symposium on Theory of computing. Acm, 2000.

[8]

CNN money: Facebook friends could change your credit score, http://money.cnn.com/2013/08/26/technology/social/facebook-credit-score/ (revision 17:27, 20 May 2015)

[9]

Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.

[10] Lattanzi, Silvio, and D. Sivakumar. "Affiliation networks." Proceedings of the forty-first annual ACM symposium on Theory of computing. ACM, 2009. [11] Narayanan, Arvind, and Vitaly Shmatikov. "Robust de-anonymization of large sparse datasets." Security and Privacy, 2008. SP 2008. IEEE Symposium on. IEEE, 2008. [12] Simon, Benedek, Gábor György Gulyás, and Sándor Imre. "Analysis of grasshopper, a novel social network de-anonymization algorithm." Periodica Polytechnica. Electrical Engineering and Computer Science 58.4 (2014): 161. [13] Wasserman, Stanley. Social network analysis: Methods and applications. Vol. 8. Cambridge university press, 1994.

72

[14] Srivatsa, Mudhakar, and Mike Hicks. "Deanonymizing mobility traces: Using social network as a side-channel." Proceedings of the 2012 ACM conference on Computer and communications security. ACM, 2012. [15] Vesdapunt, Norases, and Hector Garcia-Molina. "Identifying Users in Social Networks with Limited Information." (2014). [16] Zhou, Bin, and Jian Pei. "Preserving privacy in social networks against neighborhood attacks." Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on. IEEE, 2008. [17] Hay, Michael, et al. "Resisting structural re-identification in anonymized social networks." Proceedings of the VLDB Endowment 1.1 (2008): 102-114. [18] Liu, Kun, and Evimaria Terzi. "Towards identity anonymization on graphs." Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM, 2008.

73

Függelék

TP,FP és FP/RC értékek δ függvényében a dblp80k_2 hálózaton

74

TP,FP és FP/RC értékek δ függvényében az Epinions hálózaton

75

TP,FP és FP/RC értékek δ függvényében a fb30k_1 hálózaton

76

TP,FP és FP/RC értékek δ függvényében a LiveJournal hálózaton

77

TP,FP és FP/RC értékek δ függvényében a pkc30k_1 hálózaton

78

TP,FP és FP/RC értékek δ függvényében a Slashdot hálózaton

79

TP, FP és FP/RC eredmények a dblp80k_2 hálózaton a θ paraméter változtatása mellett

80

TP, FP és FP/RC eredmények az Epinions hálózaton a θ paraméter változtatása mellett

81

TP, FP és FP/RC eredmények a fb30k_1 hálózaton a θ paraméter változtatása mellett

82

TP, FP és FP/RC eredmények a LiveJournal hálózaton a θ paraméter változtatása mellett

83

TP, FP és FP/RC eredmények a pkc30k_1 hálózaton a θ paraméter változtatása mellett

84

TP, FP és FP/RC eredmények a Slashdot hálózaton a θ paraméter változtatása mellett

85

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a dblp80k_2 hálózaton Rnd seed mellett

86

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a dblp80k_2 hálózaton Rnd25 seed mellett

87

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a dblp80k_2 hálózaton Top seed mellett

88

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében az Epinions hálózaton Rnd seed mellett

89

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében az Epinions hálózaton Rnd25 seed mellett

90

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében az Epinions hálózaton Top seed mellett

91

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a fb30k_1 hálózaton Rnd seed mellett

92

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a fb30k_1 hálózaton Rnd25 seed mellett

93

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a fb30k_1 hálózaton Top seed mellett

94

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a LiveJournal hálózaton Rnd seed mellett

95

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a LiveJournal hálózaton Rnd25 seed mellett

96

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a LiveJournal hálózaton Top seed mellett

97

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a pkc30k_1 hálózaton Rnd seed mellett

98

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a pkc30k_1 hálózaton Rnd25 seed mellett

99

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a pkc30k_1 hálózaton Top seed mellett

100

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a Slashdot hálózaton Rnd seed mellett

101

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a Slashdot hálózaton Rnd25 seed mellett

102

A széleskörű újraazonosítás valószínűsége, illetve a helyesen és a hibásan azonosított csúcsok száma a seed méret függvényében a Slashdot hálózaton Top seed mellett

103