社會網(wǎng)絡(luò)數(shù)據(jù)隱私保護研究綜述

社會網(wǎng)絡(luò)數(shù)據(jù)隱私保護研究綜述

隨著網(wǎng)絡(luò)技術(shù)和社交媒體的快速發(fā)展，如社交網(wǎng)絡(luò)、mystrawork、com和其他人。2013年1月，超過10億用戶通過社交網(wǎng)絡(luò)進行了交流、連接和互動。隨著社會網(wǎng)絡(luò)的繁榮和廣泛應(yīng)用，越來越多的研究人員和開發(fā)人員專注于社會網(wǎng)絡(luò)的新世界。社會網(wǎng)絡(luò)的分析已成為社會學(xué)、地理學(xué)、經(jīng)濟學(xué)、計算機科學(xué)和其他許多研究領(lǐng)域的熱點。基于社會網(wǎng)絡(luò)數(shù)據(jù)進行數(shù)據(jù)挖掘和分析潛在模式比傳統(tǒng)關(guān)系數(shù)據(jù)更加科學(xué)、效果更好,社會網(wǎng)絡(luò)分析又稱為鏈接挖掘(linkmining).通過對社會網(wǎng)絡(luò)進行鏈接挖掘可以獲得實體更豐富(如某實體在整個網(wǎng)絡(luò)中的重要性)、更準(zhǔn)確(如預(yù)測某實體所屬類別)的信息.因此,亟待發(fā)布和共享更多的社會網(wǎng)絡(luò)數(shù)據(jù),為數(shù)據(jù)挖掘和模式分析提供更豐富的數(shù)據(jù)來源.然而,發(fā)布和共享社會網(wǎng)絡(luò)數(shù)據(jù)會導(dǎo)致隱私泄露,并且社會網(wǎng)絡(luò)中的隱私信息類型廣泛,潛在隱私泄露方式更加多樣化.例如:在電話網(wǎng)絡(luò)中,Ada和Bob之間頻繁的電話和短信聯(lián)系可能被視為敏感關(guān)系,因為他們不希望別人得知他們之間的親密關(guān)系;在醫(yī)療網(wǎng)絡(luò)中,某人與肺癌醫(yī)生之間的聯(lián)系可能被其視為敏感信息.大量研究工作為關(guān)系數(shù)據(jù)提供隱私保護,其中,文獻(xiàn)[2,3]首先提出K-匿名隱私保護模型,繼而出現(xiàn)了一系列基于K-匿名模型的關(guān)系數(shù)據(jù)隱私保護技術(shù)[4uf02d14].但是,關(guān)系數(shù)據(jù)隱私保護技術(shù)[2uf02d12]不能為社會網(wǎng)絡(luò)數(shù)據(jù)提供隱私保護,這是因為關(guān)系數(shù)據(jù)隱私保護模型僅考慮攻擊者將關(guān)系數(shù)據(jù)中每條記錄的屬性值作為背景知識進行隱私攻擊,忽略了社會網(wǎng)絡(luò)中結(jié)點之間的關(guān)系、社會網(wǎng)絡(luò)圖結(jié)構(gòu)、結(jié)點在圖中的結(jié)構(gòu)和位置重要性等均可作為攻擊者的背景知識進行隱私攻擊.文獻(xiàn)[13,15]基于真實數(shù)據(jù),通過實驗證明了社會網(wǎng)絡(luò)面臨很大的隱私攻擊和泄露的威脅.可以看出,關(guān)系數(shù)據(jù)只是社會網(wǎng)絡(luò)數(shù)據(jù)中結(jié)點之間相互獨立時的特例,因此,關(guān)系數(shù)據(jù)隱私保護技術(shù)不能夠滿足社會網(wǎng)絡(luò)數(shù)據(jù)的隱私保護要求,需要基于社會網(wǎng)絡(luò)數(shù)據(jù)的特點研究相應(yīng)的數(shù)據(jù)隱私保護技術(shù).本文對近年來社會網(wǎng)絡(luò)數(shù)據(jù)隱私保護研究工作[13uf02d42]進行了歸納總結(jié),指出了當(dāng)前社會網(wǎng)絡(luò)隱私保護的不足以及不同隱私保護技術(shù)間的對比和優(yōu)缺點.本文第1節(jié)介紹社會網(wǎng)絡(luò)中涉及的隱私信息,基于當(dāng)前研究工作,指出其社會網(wǎng)絡(luò)隱私保護的不足.第2節(jié)對攻擊者的背景知識進行總結(jié)歸納和分類,包括社會網(wǎng)絡(luò)圖結(jié)構(gòu)信息、結(jié)點信息、邊信息、預(yù)測模型等均可被攻擊者作為背景知識進行隱私攻擊.第3節(jié)分別從隱私保護方法、動態(tài)性、并行性等方面介紹當(dāng)前社會網(wǎng)絡(luò)隱私保護技術(shù),并指出不同隱私保護技術(shù)的優(yōu)缺點.第4節(jié)歸納常用的社會網(wǎng)絡(luò)隱私保護技術(shù)的實驗評測指標(biāo),其中包括結(jié)點數(shù)據(jù)可用性、邊數(shù)據(jù)可用性、圖結(jié)構(gòu)及性質(zhì)、圖查詢、執(zhí)行效率等方面.第5節(jié)展望未來研究趨勢.第6節(jié)總結(jié)全文.1社會網(wǎng)絡(luò)隱私的分類在社會網(wǎng)絡(luò)中,組成社會網(wǎng)絡(luò)的各個元素均可能涉及到隱私信息,包括結(jié)點、邊、圖性質(zhì)等.在本文中,社會網(wǎng)絡(luò)隱私分類為結(jié)點隱私、邊隱私、圖性質(zhì)隱私,表1給出了具體的分類結(jié)果以及為每種隱私提供保護的研究參考文獻(xiàn).1.1結(jié)論隱私信息在社會網(wǎng)絡(luò)中,每個結(jié)點代表了社會中的真實個體,而與結(jié)點相關(guān)的任何信息均有可能成為隱私.本文將結(jié)點隱私具體分類為結(jié)點存在性、結(jié)點再識別、結(jié)點屬性值、結(jié)點圖結(jié)構(gòu)等隱私信息.保持隱私信息的保護所謂結(jié)點存在性,是指某個人是否以結(jié)點的形式出現(xiàn)在某個社會網(wǎng)絡(luò)中.在某些情況下,某些人會將自己出現(xiàn)在某特定社會網(wǎng)絡(luò)視為隱私信息.如果某人將此視為隱私信息,發(fā)布數(shù)據(jù)時應(yīng)防止攻擊者結(jié)合背景知識推測出該人存在此社會網(wǎng)絡(luò)中.例如,傳染病傳播網(wǎng)絡(luò)對于研究公共健康和疾病傳播途徑等方面具有很大價值,然而在發(fā)布傳染病傳播網(wǎng)絡(luò)數(shù)據(jù)的同時,如果攻擊者能夠推斷出某攻擊目標(biāo)存在于此傳染病傳播網(wǎng)絡(luò)中,則導(dǎo)致了該攻擊目標(biāo)隱私信息的泄露.從表1中可以看出,目前針對保護結(jié)點存在性隱私信息的研究工作尚屬空白.背景知識匹配識別在發(fā)布社會網(wǎng)絡(luò)數(shù)據(jù)時,為了保護網(wǎng)絡(luò)中實體的隱私信息,通常將所有結(jié)點的身份信息刪除,使得攻擊者不能識別和推測出攻擊目標(biāo)在社會網(wǎng)絡(luò)中的準(zhǔn)確位置.但是攻擊者可以基于與攻擊目標(biāo)相關(guān)的背景知識對社會網(wǎng)絡(luò)中的結(jié)點進行匹配識別[13,16,17,19,22,24,25,29,31,37uf02d39,41],從而準(zhǔn)確地或者以一定概率識別攻擊目標(biāo)在社會網(wǎng)絡(luò)中的位置.在社會網(wǎng)絡(luò)中,攻擊者基于背景知識對攻擊目標(biāo)的位置進行匹配識別的過程稱為結(jié)點再識別.例如,圖1(b)是圖1(a)刪除身份信息后的發(fā)布數(shù)據(jù),如果攻擊者掌握了Ada的1-鄰居子圖(如圖1(c)所示),則可以推斷出圖1(b)中的結(jié)點6是Ada,從而準(zhǔn)確地識別出Ada在社會網(wǎng)絡(luò)中的位置,導(dǎo)致Ada隱私信息泄露.結(jié)論的敏感屬性信息社會網(wǎng)絡(luò)中的每個結(jié)點具有屬性值,這些屬性值描述了社會中每個人的真實信息,其中某些屬性信息會涉及到個人隱私,例如收入信息、醫(yī)療記錄中的患病信息等.發(fā)布社會網(wǎng)絡(luò)數(shù)據(jù)時,結(jié)點之間的相互關(guān)系使得攻擊者具有更多的背景知識推測目標(biāo)結(jié)點的敏感屬性信息.例如在家族遺傳病史社會網(wǎng)絡(luò)中,即使刪除了某個重要結(jié)點的疾病信息,但是攻擊者還可以基于其親戚患有遺傳疾病的情況,推測該目標(biāo)結(jié)點可能患有的疾病.文獻(xiàn)提出采用結(jié)點K-匿名的方法來保護結(jié)點的敏感屬性值,而文獻(xiàn)[33uf02d35]顯示了基于社會網(wǎng)絡(luò)基本常識即可準(zhǔn)確地推測出大部分結(jié)點的敏感屬性信息.用于網(wǎng)絡(luò)保護控制控制深度的信息不僅結(jié)點的某些屬性值是敏感的,結(jié)點在社會網(wǎng)絡(luò)中的圖結(jié)構(gòu)性質(zhì)在某些情況下也被視為敏感和隱私,例如結(jié)點的度、兩個結(jié)點間的最短距離、結(jié)點到社會網(wǎng)絡(luò)中某個社區(qū)中心的距離等.例如在商品供貨網(wǎng)絡(luò)中,每個結(jié)點的入度和出度分別表示其供貨渠道數(shù)目和銷售渠道的數(shù)目,這些信息屬于需要保護的敏感信息而防止其被競爭對手獲得.表1所示了目前尚無相關(guān)工作針對保護結(jié)點的圖結(jié)構(gòu)隱私信息進行深入研究.1.2基于關(guān)系敏感的邊隱私在社會網(wǎng)絡(luò)中,一條邊表示其兩端結(jié)點具有某種關(guān)系,結(jié)點由于相互間具有各種關(guān)系從而形成龐大的網(wǎng)絡(luò)圖.在某些情況下,邊相關(guān)信息可能是敏感的,例如兩點之間是否具有某種關(guān)系、參與某種敏感關(guān)系的結(jié)點信息、邊權(quán)重、邊的相關(guān)屬性等.本文將邊隱私具體分類為邊存在性、邊再識別、邊權(quán)重、邊屬性值等隱私信息.基于鏈接推演的敏感邊估計所謂邊存在性,是指社會網(wǎng)絡(luò)中的兩個指定結(jié)點是否具有某種關(guān)系.如果某兩個結(jié)點的邊是敏感的,簡單地將此兩個目標(biāo)結(jié)點的敏感邊刪除并不能很好地保護隱私信息,攻擊者可以通過背景知識推測兩個目標(biāo)結(jié)點是否具有敏感邊.文獻(xiàn)假設(shè)攻擊者采用noisy-or概率模型并基于現(xiàn)有結(jié)點之間的邊連接來計算目標(biāo)結(jié)點間具有敏感關(guān)系的概率,從而對可能被刪除的敏感邊進行恢復(fù).在文獻(xiàn)中,通過實驗驗證了在真實社會網(wǎng)絡(luò)數(shù)據(jù)上采用鏈接推演技術(shù)可以高概率地預(yù)測兩個目標(biāo)結(jié)點之間是否具有邊連接.結(jié)論:+a類對于社會網(wǎng)絡(luò)中的某條邊,識別該邊兩端結(jié)點的過程稱為邊再識別.在社會網(wǎng)絡(luò)中,每條邊的兩端連接著社會網(wǎng)絡(luò)中的兩個結(jié)點,表明兩個結(jié)點所代表的個人具有某種關(guān)系,該關(guān)系可能被視為敏感信息.例如在異性交友網(wǎng)絡(luò)中,兩個結(jié)點之間的邊表示了兩個結(jié)點所代表的個人曾經(jīng)具有男女朋友關(guān)系,顯然,此種關(guān)系可能涉及個人隱私.文獻(xiàn)[18,23,30,41]研究了如何使邊再識別概率小于指定閾值.文獻(xiàn)同樣將兩結(jié)點之間的邊連接視為隱私信息,并提出技術(shù)保證在不得知結(jié)點之間邊連接情況的同時,較準(zhǔn)確地計算任意兩點之間的最短路徑長度.間反蒸發(fā)正常電子數(shù)在不同應(yīng)用背景中,社會網(wǎng)絡(luò)中的邊具有權(quán)重.在電子郵件通信網(wǎng)絡(luò)中,邊權(quán)重可以表示兩個人之間收發(fā)電子郵件數(shù)目;在商業(yè)網(wǎng)絡(luò)中,邊權(quán)重可以表示兩個商業(yè)公司之間的貿(mào)易額.類似商業(yè)公司之間的貿(mào)易額等邊權(quán)重信息可能被視為敏感信息.在文獻(xiàn)中,研究了在防止邊權(quán)重值泄露的同時保持某些重要結(jié)點間的最短路徑不變;而文獻(xiàn)提出的技術(shù)在對邊權(quán)重提供隱私保護的同時保證線性圖性質(zhì)不變.注意邊界的位置關(guān)系和社會知識與結(jié)點屬性值相似,社會網(wǎng)絡(luò)中的邊也可以具有屬性值,例如邊上的標(biāo)簽可以表示邊兩端結(jié)點的關(guān)系類型.邊的敏感屬性值對于邊的兩端結(jié)點所代表的個人來說屬于隱私信息.文獻(xiàn)[14,17]研究了在社會網(wǎng)絡(luò)中,如何防止攻擊者基于背景知識推測出邊的敏感屬性值.1.3用于社會網(wǎng)絡(luò)的隱私信息分類很多圖性質(zhì)是社會網(wǎng)絡(luò)分析的重要評估標(biāo)準(zhǔn),例如中間性(結(jié)點位于其他結(jié)點連接路徑上的度)、中心性(結(jié)點與其他結(jié)點具有關(guān)系的數(shù)目)、路徑長度(網(wǎng)絡(luò)中兩結(jié)點間的最短距離)、可達(dá)性(任意結(jié)點與其他結(jié)點聯(lián)通的度)等.某些結(jié)點的圖性質(zhì)亦被視為個人隱私信息,目前尚無相關(guān)工作對結(jié)點圖性質(zhì)提供隱私保護.對社會網(wǎng)絡(luò)中的隱私信息進行分類歸納意義重大,因為社會網(wǎng)絡(luò)中,不同類型隱私信息泄露均會威脅到個人隱私信息安全,只有對社會網(wǎng)絡(luò)中的隱私信息做好辨識和分類工作,才能對不同隱私信息提出相應(yīng)保護技術(shù).從表1可以看出,社會網(wǎng)絡(luò)中很多方面的隱私信息需要深入研究來為其提供保護.2知識攻擊分類由于社會網(wǎng)絡(luò)蘊含的信息具有多樣化的特點,攻擊者可以采用多種類型知識發(fā)動隱私攻擊,對進行社會網(wǎng)絡(luò)隱私保護提出很大挑戰(zhàn).本文將攻擊者背景知識分類為社會網(wǎng)絡(luò)圖結(jié)構(gòu)、結(jié)點信息、邊信息、預(yù)測模型等方面,表2給出了具體分類結(jié)果以及每項研究工作所涉及的參考文獻(xiàn).2.1社會網(wǎng)絡(luò)圖結(jié)構(gòu)攻擊者可以將結(jié)點間連接情況,即社會網(wǎng)絡(luò)圖結(jié)構(gòu),作為背景知識來進行隱私攻擊.社會網(wǎng)絡(luò)圖結(jié)構(gòu)可具體分類為結(jié)點鄰居圖、社會網(wǎng)絡(luò)子圖、圖查詢等方面,為攻擊者提供圖結(jié)構(gòu)背景知識.ada的d--d-d-d-d-d-d-d-d-d-d-da在社會網(wǎng)絡(luò)中,將距離結(jié)點u長度d之內(nèi)的所有結(jié)點稱為u的d-鄰居結(jié)點,u的d-鄰居結(jié)點及其相互之間的邊構(gòu)成的子圖稱為結(jié)點u的d-鄰居子圖.結(jié)點鄰居圖是一種常見的圖結(jié)構(gòu)背景知識.圖1給出采用1-鄰居子圖進行隱私攻擊的實例,例如:圖1(c)顯示了Ada的1-鄰居子圖,而圖1(b)中只有結(jié)點6的1-鄰居子圖與Ada相同,因此,攻擊者可以在圖1(b)中唯一識別出結(jié)點6是Ada,從而導(dǎo)致Ada隱私泄露.嵌入子圖的識別在社會網(wǎng)絡(luò)圖中,攻擊者可以將具有特殊連接模式的子圖作為背景知識,從而為其進行隱私攻擊提供結(jié)構(gòu)唯一性的識別標(biāo)記.文獻(xiàn)針對結(jié)構(gòu)唯一性子圖導(dǎo)致隱私泄露的可行性進行了研究:在發(fā)布社會網(wǎng)絡(luò)數(shù)據(jù)前,攻擊者嵌入具有結(jié)構(gòu)唯一性的子圖,并建立該子圖與目標(biāo)結(jié)點之間的連接,當(dāng)匿名化的社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布后,攻擊者首先識別嵌入子圖,然后基于嵌入子圖和目標(biāo)結(jié)點之間的聯(lián)系來識別目標(biāo)結(jié)點.通過實驗顯示,嵌入由7個結(jié)點構(gòu)建的特殊子圖平均可以識別出70個目標(biāo)結(jié)點.查詢qv為v在社會網(wǎng)絡(luò)中可以執(zhí)行多種圖查詢,而針對某些結(jié)點或者邊的圖查詢結(jié)果具有唯一性,從而為攻擊者提供了進行隱私攻擊的背景知識.例如:對于結(jié)點v,定義查詢Q(v)為v的所有鄰居結(jié)點度的升序序列.在圖1(a)中,Q(Fred)=[2,2,4].如果攻擊者將Fred的朋友的度信息作為背景知識,則可以在圖1(b)中識別出結(jié)點5即是Fred,因為只有結(jié)點5的度序列與Fred相同.文獻(xiàn)評估了不同圖查詢作為背景知識的隱私攻擊能力;而文獻(xiàn)[24,25,29]雖然沒有定義可導(dǎo)致隱私泄露的圖查詢,但其提供的隱私保護技術(shù)可以防御部分或者全部圖查詢導(dǎo)致的隱私泄露.2.2基于結(jié)論屬性值的分類對于某些社會網(wǎng)絡(luò)隱私攻擊,尤其是結(jié)點隱私攻擊,攻擊者會將結(jié)點自身的一些相關(guān)信息作為背景知識.社會網(wǎng)絡(luò)中結(jié)點的屬性值可以分類為標(biāo)識屬性和敏感屬性.標(biāo)識屬性為攻擊者提供了結(jié)點識別的背景知識,例如年齡、性別、籍貫、學(xué)歷等,攻擊者可以將網(wǎng)絡(luò)中的結(jié)點標(biāo)識屬性值和其掌握的實體屬性值進行鏈接匹配,從而識別結(jié)點的真實身份.文獻(xiàn)[17,30]研究了如何防范基于結(jié)點屬性值的結(jié)點再識別隱私攻擊,而文獻(xiàn)側(cè)重研究攻擊者基于結(jié)點屬性值進行邊再識別隱私攻擊.隱私攻擊的模擬在社會網(wǎng)絡(luò)中,結(jié)點度表示了該結(jié)點所代表的實體與社會中的其他實體之間的關(guān)系數(shù)目,在現(xiàn)實中,攻擊者很容易收集到目標(biāo)的度信息,并作為背景知識進行結(jié)點再識別[16,19,24,25,29,30]、邊再識別等隱私攻擊.圖2描述了如何基于結(jié)點度進行結(jié)點再識別攻擊.圖2(a)只有結(jié)點A的度為2,其他結(jié)點的度均為1,因此,當(dāng)攻擊者掌握A的度為2的背景知識時,可以很容易地識別出A在社會網(wǎng)絡(luò)中的位置.相似地,攻擊者可以基于目標(biāo)結(jié)點的度進行邊再識別攻擊.在文獻(xiàn)中,假設(shè)攻擊者背景知識為互為鄰居的兩個結(jié)點的度,例如圖2(a)中結(jié)點C,D的度對(1,1).由于圖2(a)中具有度對(1,1)的邊只有一條,所以攻擊者識別出邊CD的成功概率為100%.2.3作為背景知識的攻擊社會網(wǎng)絡(luò)中,連接結(jié)點的邊是其重要的組成部分,攻擊者可以將邊的相關(guān)信息作為背景知識,包括邊連接關(guān)系、邊屬性值[30,37uf02d39]等.隱私信息的獲得如果攻擊者事先掌握了某些目標(biāo)的邊連接關(guān)系,則可以根據(jù)這些連接關(guān)系進行推演,從而獲得隱私信息.文獻(xiàn)[17,18,23]研究了連接關(guān)系可能導(dǎo)致的隱私泄露.參照表示基于連接關(guān)系的隱私攻擊的圖3,如果朋友關(guān)系被視為敏感關(guān)系,則可以基于圖3(a)中u1和u2與結(jié)點friend1的連接關(guān)系推斷出u1和u2具有朋友關(guān)系的隱私信息.基于背景知識的攻擊識別邊上的屬性值(標(biāo)簽、權(quán)重等)可以為攻擊者提供隱私攻擊的背景知識.例如在朋友網(wǎng)絡(luò)中,邊標(biāo)簽表示朋友之間的聯(lián)系方式,可以是電話、短信、電子郵件等.如果攻擊者知道某目標(biāo)基本上僅采用電子郵件與其他朋友聯(lián)系,基于此背景知識,攻擊者能夠以很大概率在社會網(wǎng)絡(luò)中識別出這個目標(biāo)結(jié)點.在加權(quán)社會網(wǎng)絡(luò)圖中,邊權(quán)重可以作為攻擊者的背景知識.文獻(xiàn)[37uf02d39]研究了加權(quán)圖中目標(biāo)結(jié)點與其他結(jié)點相連接的邊權(quán)重信息如何導(dǎo)致身份泄露.對于結(jié)點v,將與v相連接的邊權(quán)重按照降序排序得到的序列定義為結(jié)點v的權(quán)重包,記作wv.例如,圖4(a)中結(jié)點A權(quán)重包為wA=[wAB,wAD]=[2,1].如果攻擊者掌握了結(jié)點A的權(quán)重包信息,則可以識別出圖4(b)中的結(jié)點1即為A,從而導(dǎo)致了身份泄露.2.4社會網(wǎng)絡(luò)的預(yù)測模型主要來源于社會網(wǎng)絡(luò)的學(xué)習(xí)攻擊者可以基于社會網(wǎng)絡(luò)常識構(gòu)建預(yù)測模型,從而推演目標(biāo)的隱私信息.當(dāng)前,社會網(wǎng)絡(luò)中的預(yù)測模型主要分為兩類:基于鄰居的預(yù)測模型和基于興趣組的預(yù)測模型.noisy-or概率模型的正確預(yù)測率所謂物以類聚,人以群分,在社會網(wǎng)絡(luò)中,此種現(xiàn)象尤為明顯.一般情況下,具有朋友關(guān)系的實體具有相同或相似的屬性值,攻擊者可以根據(jù)鄰居屬性值來推斷目標(biāo)的敏感屬性值.在文獻(xiàn)中,研究了采用貝葉斯網(wǎng)絡(luò)來推演目標(biāo)的敏感屬性值.相似地,可以通過鏈接推演技術(shù)來預(yù)測和恢復(fù)社會網(wǎng)絡(luò)中的敏感關(guān)系.很多鏈接推演技術(shù)均是基于社會人際交往常識,其中一項常識是:如果兩個人具有很多共同朋友,則他們也很有可能是朋友.文獻(xiàn)評估了在真實數(shù)據(jù)集Email-1和LiveJ-1上采用鏈接推演技術(shù)預(yù)測敏感關(guān)系的可行性.在實驗測試中,如果兩個結(jié)點的共同鄰居數(shù)目大于閾值uf064,則認(rèn)為兩者在圖中具有邊連接.實驗結(jié)果表明:當(dāng)uf064增大時,正確預(yù)測率逐漸增高;當(dāng)uf064=20時,Email-1和LiveJ-1數(shù)據(jù)集上的正確預(yù)測率分別達(dá)到了91.06%和66.5%.可以看出:攻擊者可以憑借鏈接推演技術(shù),以較高的概率推斷出社會網(wǎng)絡(luò)中的敏感關(guān)系.在社會網(wǎng)絡(luò)中,結(jié)點之間具有不同的關(guān)系.基于常識可以知道,各種關(guān)系之間不是相互獨立而是相關(guān)的.例如,具有同學(xué)關(guān)系的兩個人是朋友的概率比沒有任何關(guān)系的兩個人是朋友的概率大.在文獻(xiàn)中,研究了通過非敏感關(guān)系邊采用noisy-or概率預(yù)測模型來預(yù)測敏感關(guān)系.eisj=1表示結(jié)點i和j具有敏感關(guān)系s,如果邊ek(k=1,…,n)的影響參數(shù)是λk,ek對于eisj的影響是相互獨立的,并且所有觀察邊對于eisj的影響參數(shù)是λ0,則基于noisy-or概率模型得到結(jié)點i和j具有敏感關(guān)系s的概率為基于公式(1)計算的概率,即可對i和j是否存在敏感關(guān)系進行推測.在社會網(wǎng)絡(luò)中,實體加入不同的興趣組,比如在豆瓣網(wǎng)中,每個用戶可以憑借自己愛好加入諸如攝影、影視等方面的興趣組.利用實體之間的朋友關(guān)系、加入興趣組情況,可以對實體的隱私屬性進行推測.其基本思想是:參加相同興趣組的兩個實體具有相同屬性值的概率較大;參加相同興趣組的數(shù)目越多,則兩個實體具有相同屬性值的概率越大.在文獻(xiàn)中,基于實體參加興趣組的情況,采用貝葉斯法則來推測未知屬性值.由于每個興趣組中組員屬性值分布不同,即每個興趣組對屬性值的預(yù)測能力不同,文獻(xiàn)提出了興趣組細(xì)化的貝葉斯分類器,可以較高概率地預(yù)測未知屬性值.在文獻(xiàn)中提出的預(yù)測模型中,不僅考慮了實體參與興趣組情況,也結(jié)合了實體之間的朋友關(guān)系,其屬性值預(yù)測準(zhǔn)確率高于文獻(xiàn)中的預(yù)測模型.3社會網(wǎng)絡(luò)隱私保護技術(shù)針對不同背景知識可能導(dǎo)致的隱私泄露,提出了相應(yīng)的社會網(wǎng)絡(luò)隱私保護技術(shù).本節(jié)分別從隱私保護方法、動態(tài)性、并行性等方面介紹當(dāng)前社會網(wǎng)絡(luò)隱私保護技術(shù),并指出不同隱私保護技術(shù)的優(yōu)缺點.表3給出了當(dāng)前社會網(wǎng)絡(luò)隱私保護技術(shù)的具體分類結(jié)果.3.1隱私泄露和數(shù)據(jù)擾擾社會網(wǎng)絡(luò)隱私保護方法主要分為結(jié)點K-匿名、子圖K-匿名、數(shù)據(jù)擾亂、推演控制這4種.結(jié)點K-匿名[17uf02d19,23,42]和子圖K-匿名[16,22,24,25,29uf02d31,37uf02d39,41]的主要思想是:攻擊者基于目標(biāo)背景知識在匿名化社會網(wǎng)絡(luò)數(shù)據(jù)中進行匹配識別時,至少有K個候選符合,即目標(biāo)的隱私泄露概率小于1/K;數(shù)據(jù)擾亂的主要思想是:對社會網(wǎng)絡(luò)進行隨機化修改,使得攻擊者不能準(zhǔn)確地推測出原始真實數(shù)據(jù),數(shù)據(jù)擾亂方法具體分為數(shù)值擾亂和圖結(jié)構(gòu)擾亂;推演控制的主要思想是:對于不同隱私預(yù)測模型,通過對社會網(wǎng)絡(luò)進行針對性地修改,使得攻擊者采用預(yù)測模型不能推演出隱私信息,從而起到保護社會網(wǎng)絡(luò)隱私的目的.3.1.1基于結(jié)論k-匿名的結(jié)論所謂結(jié)點K-匿名,是指通過將社會網(wǎng)絡(luò)中所有結(jié)點聚類成若干超點,其中每個超點至少包含K個結(jié)點,由于在超點中結(jié)點相互之間不可區(qū)分,因此在該社會網(wǎng)絡(luò)中,受結(jié)點再識別攻擊而導(dǎo)致隱私泄露的概率小于1/K.圖5顯示了結(jié)點聚類與可能社會網(wǎng)絡(luò),圖5(b)給出了圖5(a)的一個結(jié)點聚類圖,每個超點記錄了其內(nèi)部結(jié)點間邊連接數(shù)目,兩個超點之間邊的數(shù)目等于端點分別為兩個超點內(nèi)部結(jié)點的邊的數(shù)目.顯然,結(jié)點聚類成超點導(dǎo)致了邊兩端結(jié)點的信息損失,增加了圖結(jié)構(gòu)不確定性,降低了數(shù)據(jù)可用性.假設(shè)匿名圖G的超點集為V,則G的可能社會網(wǎng)絡(luò)數(shù)目W(G)可以通過公式(2)計算得到,其中,d(X,X)表示超點X內(nèi)的邊數(shù)目,d(X,Y)表示超點X和Y之間的邊數(shù)目.例如,圖5(b)表示了960個可能社會網(wǎng)絡(luò),圖5(c)為圖5(a)的一個可能社會網(wǎng)絡(luò).在文獻(xiàn)中,研究如何通過結(jié)點聚類實現(xiàn)結(jié)點K-匿名的同時最小化|W(G)|,其提出的技術(shù)主要基于模擬退火思想.文獻(xiàn)在文獻(xiàn)基礎(chǔ)上做了改進,與文獻(xiàn)中研究簡單社會網(wǎng)絡(luò)不同,文獻(xiàn)假設(shè)社會網(wǎng)絡(luò)中的每個結(jié)點具有屬性信息,通過結(jié)點聚類生成超點時,每個超點內(nèi)所有結(jié)點的屬性信息還需要進行匿名化處理使得屬性值相等,因此不僅會造成圖結(jié)構(gòu)信息損失,也會造成結(jié)點屬性值的信息損失.文獻(xiàn)提出一種貪心聚類方法來實現(xiàn)復(fù)雜社會網(wǎng)絡(luò)的結(jié)點K-匿名.由于文獻(xiàn)提出的匿名算法需要數(shù)據(jù)發(fā)布者通過設(shè)定權(quán)重來決定圖匿名過程側(cè)重于減少圖結(jié)構(gòu)信息損失還是結(jié)點屬性信息損失,而兩者的數(shù)據(jù)可用性難以量化,使得在實際應(yīng)用中無法設(shè)定所需的權(quán)重,導(dǎo)致文獻(xiàn)中方法的實用性較差.文獻(xiàn)[18,23]采用結(jié)點K-匿名來隱藏二部圖社會網(wǎng)絡(luò)中的敏感關(guān)系.圖3(b)給出了基于圖3(a)進行結(jié)點K-匿名化后的二部圖社會網(wǎng)絡(luò)數(shù)據(jù).結(jié)點K-匿名隱私保護能力強,具有很好的通用性,可以防止多種類型隱私泄露.然而,結(jié)點K-匿名在提供強隱私保護的同時,導(dǎo)致了圖數(shù)據(jù)可用性降低,并且結(jié)點K-匿名的執(zhí)行效率低,不適用于大型社會網(wǎng)絡(luò)數(shù)據(jù).3.1.2社會網(wǎng)絡(luò)匿名化方法所謂子圖K-匿名,是指當(dāng)攻擊者將目標(biāo)所在的特定子圖作為背景知識進行隱私攻擊時,社會網(wǎng)絡(luò)中至少有K個子圖可作為候選,則目標(biāo)子圖導(dǎo)致隱私泄露的概率小于1/K.與目標(biāo)相關(guān)的標(biāo)識性子圖均可作為攻擊者的背景知識,例如結(jié)點的度、鄰居圖等.通過在社會網(wǎng)絡(luò)中加偽點、加偽邊、刪除邊、概括等,可實現(xiàn)子圖K-匿名.文獻(xiàn)研究了攻擊者將結(jié)點的度作為背景知識時如何進行子圖K-匿名,提出了采用K-度匿名圖來防止此類攻擊.所謂K-度匿名圖,是指對于該圖中的任意結(jié)點,至少有Kuf02d1個結(jié)點與該點的度相同.例如,圖2(b)、圖2(c)均為2-度匿名圖.文獻(xiàn)通過采用動態(tài)規(guī)劃的方法實現(xiàn)了通過加入最少數(shù)目的邊來生成K-度匿名圖.在文獻(xiàn)中,每個結(jié)點可以設(shè)定所需的隱私保護級別:第1級別為防止結(jié)點標(biāo)簽導(dǎo)致身份泄露;第2級別為防止結(jié)點標(biāo)簽、度導(dǎo)致身份泄露;第3級別為防止結(jié)點標(biāo)簽、度、結(jié)點邊標(biāo)簽導(dǎo)致身份泄露.對于需要第2級別和第3級別隱私保護的結(jié)點,文獻(xiàn)對其進行K-度匿名化操作.文獻(xiàn)在生成K-度匿名圖的同時,最小化社團結(jié)構(gòu)信息損失.由于攻擊者能夠獲得比結(jié)點度更復(fù)雜的目標(biāo)子圖背景知識,因此K-度匿名的隱私保護能力較差.當(dāng)攻擊者將目標(biāo)的1-鄰居圖作為背景知識時,文獻(xiàn)提出的匿名化方法使得對于任意結(jié)點的1-鄰居圖,至少有Kuf02d1個結(jié)點的1-鄰居圖與其同構(gòu).在匿名過程中,需要加入偽邊和概括結(jié)點標(biāo)簽.圖1(d)給出了K=2時圖1(a)的匿名圖.可以看出:具有唯一鄰居圖的結(jié)點6在匿名后與結(jié)點2和結(jié)點9具有相同的鄰居圖,因此攻擊者基于結(jié)點6的1-鄰居圖獲得其真實身份的概率小于1/2.為了防范攻擊者將任意目標(biāo)子圖作為背景知識,文獻(xiàn)提出將社會網(wǎng)絡(luò)匿名化為K-對稱圖.所謂K-對稱圖,是指對于圖中的任意結(jié)點v,在圖中至少存在Kuf02d1個結(jié)點與v是結(jié)構(gòu)對等的.例如,圖6(b)是圖6(a)的2-對稱圖,其中添加的偽點vuf0a23與v3結(jié)構(gòu)對等,因此攻擊者識別出v3的真實身份概率為1/2.顯然,為了構(gòu)建K-對稱圖,匿名化時需要在社會網(wǎng)絡(luò)數(shù)據(jù)中加入偽點和偽邊.K-對稱圖的潛在隱私威脅是:當(dāng)攻擊者獲知K-對稱圖生成算法時,可以將發(fā)布的K-對稱圖中結(jié)構(gòu)對等的結(jié)點進行合并,還原出部分原始圖,從而導(dǎo)致隱私泄露.文獻(xiàn)提出K-自同構(gòu)來進行隱私保護.所謂K-自同構(gòu),是指圖自身存在著K個同構(gòu)映射.K-自同構(gòu)能夠阻止結(jié)點再識別隱私攻擊,但是不能防范敏感關(guān)系隱私攻擊.為了能夠同時保護結(jié)點和邊隱私,文獻(xiàn)提出K-同構(gòu)隱私保護模型.所謂K-同構(gòu),是指社會網(wǎng)絡(luò)圖分為K個子圖,子圖之間相互同構(gòu).為了實現(xiàn)K-同構(gòu),首先需要將社會網(wǎng)絡(luò)圖分割為K個包含相同數(shù)目結(jié)點的子圖,然后通過加入偽邊和刪除邊的方法使得K個子圖同構(gòu),增刪邊的數(shù)目和圖數(shù)據(jù)可用性的大小主要取決于圖分割策略.例如,圖6(d)為圖6(c)的4-同構(gòu)圖.K-同構(gòu)雖然能夠很好地保護結(jié)點和邊隱私,但是同構(gòu)子圖之間的邊連接會被刪除,導(dǎo)致位于同構(gòu)子圖之間的圖模式會受到影響.目標(biāo)與鄰居連接邊上的屬性值序列可以作為隱私攻擊的背景知識[30,37uf02d39].在文獻(xiàn)中,通過加入偽點、偽邊、設(shè)置邊標(biāo)簽來弱化鄰居連接邊標(biāo)簽序列的標(biāo)識作用.文獻(xiàn)[37uf02d39]研究了如何阻止權(quán)重包導(dǎo)致的隱私泄露.文獻(xiàn)提出的加權(quán)圖匿名化方法可以使得對于任意結(jié)點的權(quán)重包,至少有Kuf02d1個其他結(jié)點的權(quán)重包與其距離小于預(yù)先設(shè)定閾值,而不是完全相同;而文獻(xiàn)提出的HA(histogramanonymization)算法使得至少有Kuf02d1個其他結(jié)點的權(quán)重包與其相同.對圖4(a)中的G采用HA算法匿名化后得到圖4(c)中的GHA.顯然,HA算法對于邊及權(quán)重值的修改導(dǎo)致了圖數(shù)據(jù)的統(tǒng)計特性的改變.例如,對于圖查詢Q:SELECTCOUNT(uf022edgeuf0ceG)WHEREedge.weight≥2,在GHA中Q的查詢結(jié)果是4,而Q在原圖G中的查詢結(jié)果是2,兩者具有一定的偏差.為了提高匿名加權(quán)圖的數(shù)據(jù)可用性,文獻(xiàn)提出邊權(quán)重概括技術(shù)(記作GA算法)來實現(xiàn)K-可能圖.所謂K-可能圖,是指對于任意結(jié)點的權(quán)重包,在K-可能圖中可以找到至少K個為其概括實例的權(quán)重包.例如在圖4(d)的GGA中,w12=[1,2]表示邊e12的權(quán)重值位于區(qū)間[1,2],邊e13上的50%表示e13的存在概率,因此,GGA中權(quán)重包w1可以表示為[([1,2],100%),(1,50%),(1,100%)].在圖GGA中,結(jié)點1可被推測為圖4(a)中G的A,因為A的權(quán)重包wA是w1的一個可能實例;相似的,wA也是w4的一個可能實例;因此,A被準(zhǔn)確識別的概率小于等于1/2.在GGA中執(zhí)行查詢Q時,邊e23符合Q的查詢條件,邊e12和e34可能符合Q的查詢條件,其他邊不符合Q的查詢條件,則Q的查詢結(jié)果為區(qū)間[1,3],包含了Q在原圖G上的查詢結(jié)果2.實驗結(jié)果證明,GA算法很好地保持了加權(quán)圖數(shù)據(jù)可用性.3.1.3基于數(shù)據(jù)擾動思想的社會網(wǎng)絡(luò)隱私保護技術(shù)圖數(shù)據(jù)擾亂隱私保護方法的基本思想是:通過對社會網(wǎng)絡(luò)圖進行隨機化修改,使得攻擊者不能準(zhǔn)確推測出原始真實數(shù)據(jù),從而起到保護社會網(wǎng)絡(luò)數(shù)據(jù)隱私的作用.本文分別從數(shù)值擾亂和圖結(jié)構(gòu)擾亂等方面介紹基于數(shù)據(jù)擾亂思想的社會網(wǎng)絡(luò)隱私保護技術(shù).動態(tài)社會網(wǎng)絡(luò)的穩(wěn)定性社會網(wǎng)絡(luò)中可以記錄大量的數(shù)值信息,通過對數(shù)值信息進行隨機化的擾亂和修改,可以使得攻擊者不能猜測出原始真實數(shù)值.目前,數(shù)值擾亂方法主要用于為加權(quán)圖中的邊權(quán)重提供隱私保護.文獻(xiàn)研究了通過擾亂技術(shù)保護社會網(wǎng)絡(luò)邊權(quán)重隱私的同時,降低擾亂噪聲對于社會網(wǎng)絡(luò)中兩點間的最短路徑序列及最短路徑大小的影響.對于動態(tài)社會網(wǎng)絡(luò),文獻(xiàn)提出在邊權(quán)重中加入高斯噪聲進行擾亂:其中,i和wi*分別表示邊i的初始權(quán)重、擾亂后權(quán)重;xi表示加入的高斯噪聲,xi服從高斯分布N(0,uf0642).例如,圖4(e)顯示了對圖4(a)采用服從N(0,0.152)分布的高斯噪聲擾亂邊權(quán)重后的社會網(wǎng)絡(luò).在靜態(tài)社會網(wǎng)絡(luò)中,為了保持指定結(jié)點對的最短路徑序列及其大小不變,文獻(xiàn)通過將社會網(wǎng)絡(luò)數(shù)據(jù)中的邊分類從而提出貪心擾亂算法,側(cè)重擾亂其他邊的權(quán)重.文獻(xiàn)中的擾亂方法可以高效率地在邊權(quán)重中加入噪聲,并保證指定結(jié)點對的最短路徑及其大小不變,但是噪聲對于邊權(quán)重的影響不大,仍然會泄露邊權(quán)重隱私,而且不能保證所有結(jié)點間的最短路徑保持不變,數(shù)據(jù)可用性不高.文獻(xiàn)提出線性規(guī)劃模型構(gòu)建方法,在對邊權(quán)重進行擾亂的同時,保持加權(quán)圖的線性圖性質(zhì),例如最短路徑、K-最近鄰等.與文獻(xiàn)中僅能保持指定結(jié)點對的最短路徑相比,文獻(xiàn)中的方法較大程度地保證了加權(quán)圖的數(shù)據(jù)可用性.隨機圖擾動技術(shù)通過隨機進行圖數(shù)據(jù)擾亂和修改,可以阻止攻擊者獲知原始圖結(jié)構(gòu),從而保護社會網(wǎng)絡(luò)數(shù)據(jù)隱私.圖擾亂的主要方法是隨機添加、刪除邊和交換邊端點等.例如,參照圖2,圖2(a)隨機添加(B,D)、刪除邊(B,A)后得到圖2(d),隨機交換邊(B,A),(C,D)的端點A和D得到圖2(e).很多圖性質(zhì)均與圖譜相關(guān),例如平均最短路徑、社團結(jié)構(gòu)、傳遞性等.為了保持圖性質(zhì)和圖數(shù)據(jù)可用性,文獻(xiàn)研究了如何進行圖擾亂的同時保持圖譜基本不變.文獻(xiàn)指出,圖譜主要由兩個參數(shù)所決定:(1)圖鄰接矩陣最大特征值λ1;(2)圖拉普拉斯矩陣次最小特征值μ2.通過研究圖修改操作對于λ1和μ2的影響,文獻(xiàn)提出的隨機圖擾亂技術(shù)總是選擇保持λ1和μ2基本不變的圖修改操作執(zhí)行,從而保持圖譜不變.雖然擾亂圖在一定程度上保護了圖數(shù)據(jù)隱私,但是存在明顯缺陷:(1)與K-匿名圖提供量化隱私保護不同(隱私泄露概率不大于1/K),圖隨機擾亂方法無法保證量化隱私保護,擾亂圖中仍然存在隱私泄露威脅;(2)采用文獻(xiàn)提出的圖擾亂方法的必要條件是社會網(wǎng)絡(luò)圖是連通的,然而實際社會網(wǎng)絡(luò)圖一般不具有連通性,因此需要加入新邊將圖中的獨立部分連接起來,使其具有連通性,引入了圖噪聲;(3)圖特征值的計算代價很高,然而一次隨機邊修改操作需要多次圖特征值的計算,導(dǎo)致邊修改操作計算代價高,圖擾亂需要大量的邊修改操作,因此,文獻(xiàn)的圖擾亂算法的實際應(yīng)用性不高.3.1.4社會網(wǎng)絡(luò)推演所謂推演控制,是指對于不同隱私預(yù)測和推演模型,針對性地修改社會網(wǎng)絡(luò),使得攻擊者采用預(yù)測模型不能推演出隱私信息,起到保護社會網(wǎng)絡(luò)隱私的目的.在第2.4節(jié)中分別給出了基于鄰居的預(yù)測模型和基于興趣組的預(yù)測模型,然而,只有文獻(xiàn)給出相應(yīng)的推演控制技術(shù)來防止隱私泄露,因此,社會網(wǎng)絡(luò)推演控制技術(shù)需要引起更多的關(guān)注.在文獻(xiàn)中,首先提出了基于共同鄰居數(shù)目的敏感關(guān)系預(yù)測模型,并定義了兩種鏈接推演攻擊:單步鏈接推演攻擊和級聯(lián)鏈接推演攻擊.單步鏈接推演是指對于圖上的所有無邊連接的結(jié)點對執(zhí)行鏈接推演操作;級聯(lián)鏈接推演,是指在圖上執(zhí)行多次單步鏈接推演操作.其次,為了阻止鏈接推演攻擊,提出了一種基于鏈接世系溯源的防推演機制來切斷敏感鏈接的推演路徑,在保護社會網(wǎng)絡(luò)中敏感關(guān)系的同時,保持了圖數(shù)據(jù)可用性.推演控制技術(shù)能夠有效地防止特定預(yù)測模型導(dǎo)致的隱私泄露,由于其針對性地修改社會網(wǎng)絡(luò),可以保持圖數(shù)據(jù)的高可用性.但是推演控制技術(shù)的隱私保護能力有限,對于圖數(shù)據(jù)隱私保護不具有通用性.3.2動態(tài)社會網(wǎng)絡(luò)動態(tài)性當(dāng)社會網(wǎng)絡(luò)靜止不變時,稱該社會網(wǎng)絡(luò)是靜態(tài)社會網(wǎng)絡(luò);當(dāng)社會網(wǎng)絡(luò)是不斷發(fā)展和變化時,該社會網(wǎng)絡(luò)是動態(tài)社會網(wǎng)絡(luò),具有動態(tài)性.社會網(wǎng)絡(luò)的動態(tài)性具體表現(xiàn)在:(1)不斷有新結(jié)點加入社會網(wǎng)絡(luò)中,原有結(jié)點從社會網(wǎng)絡(luò)中退出,即結(jié)點的添加和刪除;(2)社會網(wǎng)絡(luò)中,兩個無關(guān)系的實體建立新的邊連接,網(wǎng)絡(luò)中的某條邊會被兩個端點(實體)刪除,即邊的添加和刪除.當(dāng)前,社會網(wǎng)絡(luò)隱私保護技術(shù)主要面向靜態(tài)社會網(wǎng)絡(luò),而在現(xiàn)實中,幾乎所有的社會網(wǎng)絡(luò)都是動態(tài)的、不是靜止不變的.從表3中可以看出,僅有少數(shù)隱私保護技術(shù)考慮了社會網(wǎng)絡(luò)的動態(tài)性.在文獻(xiàn)[24,29]中,除了給出面向社會網(wǎng)絡(luò)的子圖K-匿名技術(shù),還研究了如何防止社會網(wǎng)絡(luò)動態(tài)性和多次發(fā)布可能導(dǎo)致的隱私泄露.文獻(xiàn)[24,29]提出采用隨機結(jié)點ID編碼來保證動態(tài)發(fā)布匿名社會網(wǎng)絡(luò)的安全性,其基本思想是:每次發(fā)布匿名社會網(wǎng)絡(luò)時,同一結(jié)點被賦予不同的ID,從而阻止了攻擊者基于網(wǎng)絡(luò)變化信息獲得數(shù)據(jù)隱私.顯然,結(jié)點ID的重新編碼不利于觀察和分析網(wǎng)絡(luò)的變化趨勢,降低了動態(tài)網(wǎng)絡(luò)的數(shù)據(jù)可用性.與文獻(xiàn)[24,29]中研究如何防止網(wǎng)絡(luò)動態(tài)性導(dǎo)致隱私泄露不同,文獻(xiàn)研究了如何利用網(wǎng)絡(luò)動態(tài)性來提高圖匿名算法的執(zhí)行效率.對于動態(tài)社會網(wǎng)絡(luò),當(dāng)發(fā)布最新版本圖數(shù)據(jù)時,基本做法是在當(dāng)前圖數(shù)據(jù)上重新運行圖匿名化算法,當(dāng)數(shù)據(jù)發(fā)布比較頻繁時,則導(dǎo)致較低的執(zhí)行效率.為了提高動態(tài)社會網(wǎng)絡(luò)匿名算法的執(zhí)行效率,文獻(xiàn)提出采用動態(tài)網(wǎng)絡(luò)預(yù)測技術(shù)來預(yù)測網(wǎng)絡(luò)的變化趨勢,例如某些無邊連接的結(jié)點對在未來可能會增加邊連接等,用于指導(dǎo)當(dāng)前圖數(shù)據(jù)的匿名化過程,目的在于減少未來圖匿名化的重新計算量和負(fù)擔(dān),從而提高了動態(tài)發(fā)布過程中圖匿名化的執(zhí)行效率.3.3云環(huán)境下的隱私保護最短路徑查詢技術(shù)隨著網(wǎng)絡(luò)技術(shù)的發(fā)展,社會網(wǎng)絡(luò)數(shù)據(jù)的數(shù)量和規(guī)模都在不斷地增長,呈現(xiàn)海量化趨勢.對于海量社會網(wǎng)絡(luò)數(shù)據(jù),采用并行算法進行分析和處理,是提高效率的有效途徑.從表3中可以看出,目前,僅文獻(xiàn)研究了云環(huán)境中社會網(wǎng)絡(luò)隱私保護,而其他研究工作主要面向單工作站的社會網(wǎng)絡(luò)隱私保護技術(shù),不適用于海量社會網(wǎng)絡(luò)數(shù)據(jù).在文獻(xiàn)中,研究了在云環(huán)境中進行最短路徑查詢的同時保護圖數(shù)據(jù)隱私,其研究目標(biāo)是:攻擊者不能推演出加權(quán)圖中每個結(jié)點的鄰居,數(shù)據(jù)查詢者可以得到任意兩點間的近似最短路徑.文獻(xiàn)中提出的云環(huán)境中隱私保護最短路徑查詢技術(shù)的基本思想是:將加權(quán)圖G轉(zhuǎn)換為鏈接圖Gl和外包圖集Go,其中,Gl相當(dāng)于加權(quán)圖的索引;而Go中的每個外包圖符合“1-鄰居-d-半徑”安全要求,即攻擊者無法獲知任意結(jié)點的鄰居以及距離小于d的結(jié)點對,對于輸入的最短路徑查詢,基于Gl找到相應(yīng)的外包圖進行最短路徑的求解;每個外包圖存儲在云環(huán)境的節(jié)點中,記錄了符合安全條件的結(jié)點對之間的最短路徑距離,通過采用三角不等式來逐步求精最短路徑查詢結(jié)果.由于在構(gòu)建鏈接圖Gl和外包圖集Go時需要計算大量結(jié)點對之間的最短路徑,使得大型加權(quán)圖的分割和預(yù)計算的工作量很大,當(dāng)網(wǎng)絡(luò)動態(tài)變化時,鏈接圖Gl和外包圖集Go均需要重新計算,而文獻(xiàn)沒有考慮如何動態(tài)更新鏈接圖Gl和外包圖集Go.4圖結(jié)構(gòu)及性質(zhì)社會網(wǎng)絡(luò)圖匿名化會導(dǎo)致一定的信息損失,影響圖數(shù)據(jù)可用性.不同社會網(wǎng)絡(luò)隱私保護技術(shù)對圖數(shù)據(jù)可用性產(chǎn)生不同的影響,需要通過實驗測試來分析和評估匿名化對數(shù)據(jù)的影響.本節(jié)歸納了常用的社會網(wǎng)絡(luò)隱私保護技術(shù)的實驗評測指標(biāo),其中包括結(jié)點數(shù)據(jù)可用性、邊數(shù)據(jù)可用性、圖結(jié)構(gòu)及性質(zhì)、圖查詢、執(zhí)行效率等方面,具體結(jié)果見表4.在社會網(wǎng)絡(luò)中,結(jié)點可能會具有表示類別的標(biāo)簽、與實體相關(guān)的屬性值等信息,邊可能會具有標(biāo)簽、權(quán)重等信息,而圖匿名技術(shù)通常會對這些屬性值進行修改、概括(generalization)等匿名化操作,因此需要評估圖匿名化導(dǎo)致的結(jié)點和邊[17,37uf02d39]的屬性值信息的損失.如第3節(jié)中,添加和刪除邊是圖匿名化中最基本的圖修改操作,可以將圖匿名化過程中的邊增加和刪除數(shù)目作為一種圖信息損失的度量.特殊地,文獻(xiàn)通過加入結(jié)點來獲得K-對稱圖,因此不僅評測了邊的添加數(shù)目,同時也測試了不同隱私要求下加入結(jié)點的數(shù)目.在圖結(jié)構(gòu)及性質(zhì)的實驗測評中,結(jié)點度分布[14,16,17,19,24,25,29,30,37,41]、最短路徑[16,19uf02d21,24,25,29,31,36,37,39uf02d41]、傳遞性[16,19,21,24,25,29,31,39uf02d41]是比較常見的圖數(shù)據(jù)可用性度量標(biāo)準(zhǔn).結(jié)點度分布是圖中不同結(jié)點度的頻率統(tǒng)計,是描述圖狀態(tài)的一種基本圖性質(zhì).最短路徑分布統(tǒng)計了圖中兩點間最短距離的分布,由于社會網(wǎng)絡(luò)中結(jié)點數(shù)目巨大并且最短路徑計算代價大,因此在實驗測試中計算最短路徑分布時,通常隨機選取指定數(shù)目的結(jié)點對來進行計算.所謂傳遞性(又稱聚集系數(shù)),是指一個結(jié)點所有鄰居對中具有邊連接的比例,即描述了“一個人的兩個朋友也是朋友的概率”.當(dāng)按照度由大自小刪除圖中結(jié)點時,網(wǎng)絡(luò)適應(yīng)力表示圖中最大社區(qū)所包含的結(jié)點數(shù)目,網(wǎng)絡(luò)適應(yīng)力描述了由于網(wǎng)絡(luò)攻擊導(dǎo)致部分結(jié)點通信不暢時網(wǎng)絡(luò)的連通性.所謂傳染性,是指對于一種假想疾病,當(dāng)隨機選擇某個結(jié)點作為傳染源時,在指定傳染率下被傳染結(jié)點的比例.為了測量社會網(wǎng)絡(luò)圖中社區(qū)結(jié)構(gòu)變化大小,在文獻(xiàn)中定義了層次社區(qū)熵(hierarchicalcommunityentropy)來計算圖匿名化所導(dǎo)致的社區(qū)結(jié)構(gòu)的變化.圖的很多性質(zhì)均與圖譜相關(guān),可以通過圖譜的變化來衡量圖匿名化對于圖數(shù)據(jù)可用性的影響,在實驗測試中,主要關(guān)注圖鄰接矩陣最大特征值uf06c1和拉普拉斯矩陣次最小特征值uf06d2的變化情況.在社會網(wǎng)絡(luò)圖中進行圖查詢是一項重要應(yīng)