增量的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)匿名化技術(shù)

郭彩華　王　斌　朱懷杰　楊曉春

(東北大學(xué)信息科學(xué)與工程學(xué)院　沈陽(yáng)　110004)(zhuhjneu@gmail.com)

?

增量的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)匿名化技術(shù)

郭彩華王斌朱懷杰楊曉春

(東北大學(xué)信息科學(xué)與工程學(xué)院沈陽(yáng)110004)(zhuhjneu@gmail.com)

摘要隨著社會(huì)網(wǎng)絡(luò)的快速發(fā)展和普及，如何保護(hù)社會(huì)網(wǎng)絡(luò)中的敏感信息已成為當(dāng)前數(shù)據(jù)隱私保護(hù)研究領(lǐng)域的熱點(diǎn)問(wèn)題.對(duì)此，近年來(lái)出現(xiàn)了多種社會(huì)網(wǎng)絡(luò)匿名化技術(shù). 現(xiàn)有的匿名技術(shù)大多把社會(huì)網(wǎng)絡(luò)抽象成簡(jiǎn)單圖，然而實(shí)際生活中存在大量增量變化的社會(huì)網(wǎng)絡(luò)，例如email通信網(wǎng)絡(luò)，簡(jiǎn)單圖并不能很好地刻畫(huà)這種增量變化，因此，將社會(huì)網(wǎng)絡(luò)抽象成增量序列具有現(xiàn)實(shí)意義.同時(shí)，在實(shí)際生活中大部分網(wǎng)絡(luò)是帶有權(quán)重信息的，即很多社會(huì)網(wǎng)絡(luò)以加權(quán)圖的形式出現(xiàn)，加權(quán)圖與簡(jiǎn)單圖相比攜帶了更多社會(huì)網(wǎng)絡(luò)中的信息，也會(huì)帶來(lái)更多的隱私泄露. 將增量的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)抽象成一個(gè)加權(quán)圖的增量序列. 為了匿名加權(quán)圖增量序列，提出了加權(quán)圖增量序列k-匿名隱私保護(hù)模型，并設(shè)計(jì)了基于權(quán)重鏈表的baseline匿名算法WLKA和基于超圖的匿名算法HVKA來(lái)防止基于結(jié)點(diǎn)標(biāo)簽和權(quán)重鏈表的攻擊. 最后，通過(guò)在真實(shí)數(shù)據(jù)集上的大量測(cè)試，證明了WLKA算法能夠保證加權(quán)圖增量序列隱私保護(hù)的有效性，HVKA算法則在WLKA的基礎(chǔ)上更好地保留了原圖的結(jié)構(gòu)性質(zhì)并提高了權(quán)重信息的可用性，同時(shí)還降低了匿名過(guò)程的時(shí)間代價(jià).

關(guān)鍵詞動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)；增量序列；數(shù)據(jù)隱私；權(quán)重鏈表；超圖；信息損失

隨著互聯(lián)網(wǎng)的發(fā)展，出現(xiàn)了越來(lái)越多的網(wǎng)絡(luò)平臺(tái)，用戶在網(wǎng)絡(luò)上共享信息并參加各種各樣的活動(dòng).社會(huì)網(wǎng)絡(luò)的出現(xiàn)給人們的生活帶來(lái)了極大的便利，但隨之而來(lái)的是越來(lái)越多的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)被發(fā)布到網(wǎng)絡(luò)上，導(dǎo)致隱私泄露.近年來(lái)，如何在發(fā)布網(wǎng)絡(luò)數(shù)據(jù)的同時(shí)保護(hù)敏感信息成為了研究熱點(diǎn).目前大部分社會(huì)網(wǎng)絡(luò)隱私保護(hù)技術(shù)主要針對(duì)簡(jiǎn)單圖，然而實(shí)際生活中存在大量增量變化的社會(huì)網(wǎng)絡(luò)，例如email通信網(wǎng)絡(luò)，簡(jiǎn)單圖并不能很好地刻畫(huà)這種增量變化，因此，將社會(huì)網(wǎng)絡(luò)抽象成增量序列具有現(xiàn)實(shí)意義.

文獻(xiàn)[1]考慮了社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)性，將社會(huì)網(wǎng)絡(luò)抽象成一系列圖組成的增量序列，即下一時(shí)刻圖中結(jié)點(diǎn)和邊都是增加的，并針對(duì)簡(jiǎn)單圖增量序列的隱私問(wèn)題進(jìn)行了研究.該文把簡(jiǎn)單圖增量序列定義為g=〈G0,G1,…,GT〉，時(shí)刻t的社會(huì)網(wǎng)絡(luò)圖表示為Gt=(Vt,Et,Lt)，其中Vt代表時(shí)刻t結(jié)點(diǎn)的集合，Et代表時(shí)刻t邊的集合，Lt代表時(shí)刻t結(jié)點(diǎn)標(biāo)簽的集合.由于它是一個(gè)增量序列，因此，Vt-1?Vt，Et-1?Et，Lt-1?Lt.

文獻(xiàn)[1]中的匿名方法保證Gt(t=0,1,…,T)符合k匿名，即攻擊者以結(jié)點(diǎn)標(biāo)簽為背景知識(shí)識(shí)別任意結(jié)點(diǎn)的概率不大于1k.它不僅考慮了攻擊者將結(jié)點(diǎn)標(biāo)簽作為背景知識(shí)，同時(shí)也將社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)變化視為背景知識(shí).圖1(a)(b)分別是簡(jiǎn)單圖增量序列g(shù)=〈G0,G1〉在時(shí)刻t為0或1的原始圖，時(shí)刻t=1新增加的結(jié)點(diǎn)和邊用虛線標(biāo)出.在文獻(xiàn)[1]的匿名算法中通過(guò)將標(biāo)簽相近的結(jié)點(diǎn)分為一組，使得同組結(jié)點(diǎn)基于標(biāo)簽不可區(qū)分，k=2時(shí)，時(shí)刻t為0或1的分組結(jié)果分別如圖2(a)(b)所示，匿名圖分別如圖1(c)(d)所示.每個(gè)標(biāo)簽均對(duì)應(yīng)2個(gè)結(jié)點(diǎn)，所以攻擊者以結(jié)點(diǎn)標(biāo)簽為背景知識(shí)準(zhǔn)確識(shí)別任意1個(gè)結(jié)點(diǎn)的概率均不大于50%.例如，攻擊者知道Alice的標(biāo)簽是{25,M,TW}，首先單獨(dú)針對(duì)圖2(a)(或圖2(b))所示的分組結(jié)果中均有2個(gè)結(jié)點(diǎn)v5,v8與標(biāo)簽{25,M,TW}對(duì)應(yīng)，所以攻擊者識(shí)別Alice的概率為50%.另外，再聯(lián)合不同時(shí)刻t為0或1的分組結(jié)果同樣不能正確識(shí)別結(jié)點(diǎn)身份，所以攻擊者仍然無(wú)法正確識(shí)別Alice.

然而，在現(xiàn)實(shí)中進(jìn)行社會(huì)網(wǎng)絡(luò)分析時(shí)，發(fā)現(xiàn)結(jié)點(diǎn)之間的邊是帶有權(quán)重信息的，即存在許多加權(quán)社會(huì)網(wǎng)絡(luò)圖.例如在金融交易網(wǎng)絡(luò)中，邊權(quán)重表示企業(yè)之間交易金額的大小.在文獻(xiàn)合作關(guān)系網(wǎng)中，邊權(quán)重表示作者之間合作的次數(shù).在email通信網(wǎng)絡(luò)中，邊權(quán)重表示實(shí)體之間發(fā)送郵件的次數(shù).在朋友關(guān)系網(wǎng)中，邊權(quán)重表示朋友之間關(guān)系的密切程度.跟簡(jiǎn)單圖相比，加權(quán)圖攜帶了更多社會(huì)網(wǎng)絡(luò)中的信息，更能準(zhǔn)確地表示現(xiàn)實(shí)世界中的社會(huì)網(wǎng)絡(luò)，具有更強(qiáng)的描述能力，同時(shí)也會(huì)帶來(lái)更多的隱私泄露，因此對(duì)于加權(quán)社會(huì)網(wǎng)絡(luò)的隱私保護(hù)更為重要.文獻(xiàn)[1]中并沒(méi)有考慮權(quán)重信息對(duì)結(jié)點(diǎn)隱私的影響.圖1(f)是G1的加權(quán)圖，假設(shè)攻擊者知道結(jié)點(diǎn)Alice的標(biāo)簽{25,M,TW}及權(quán)重鏈表〈3,1〉(權(quán)重鏈表是指結(jié)點(diǎn)與鄰居連接邊上的權(quán)值按降序排列得到的權(quán)重序列).攻擊者根據(jù)標(biāo)簽得到2個(gè)候選結(jié)點(diǎn)v5,v8，再根據(jù)權(quán)重鏈表則可得到唯一的候選結(jié)點(diǎn)v8，正確識(shí)別結(jié)點(diǎn)的概率為100%，這就導(dǎo)致了用戶身份信息泄露.

現(xiàn)有的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)模型只考慮了簡(jiǎn)單的無(wú)權(quán)圖，并沒(méi)有考慮加權(quán)圖.對(duì)此，本文將社會(huì)網(wǎng)絡(luò)抽象成加權(quán)圖增量序列，并對(duì)加權(quán)圖增量序列上的隱私問(wèn)題進(jìn)行研究.本文是第1篇解決加權(quán)圖增量序列隱私保護(hù)問(wèn)題的文章.本文的方法包括3部分：

1) 對(duì)加權(quán)圖增量序列最后一時(shí)刻的原始圖中所有結(jié)點(diǎn)分組，分組方法采用文獻(xiàn)[1]中對(duì)結(jié)點(diǎn)分組的方法，使得同一分組中的結(jié)點(diǎn)基于標(biāo)簽不可區(qū)分；

2) 對(duì)每個(gè)分組中所有結(jié)點(diǎn)的權(quán)重鏈表匿名，使得同一分組中所有結(jié)點(diǎn)基于權(quán)重鏈表不可區(qū)分；

3) 根據(jù)時(shí)刻t(t=0,1,…,T)的匿名圖推出時(shí)刻t-1的匿名圖，重復(fù)這個(gè)過(guò)程直到所有時(shí)刻的圖都完成匿名.

Fig. 1　An example of anonymity incremental sequence g=〈G0,G1〉(k=2).圖1　增量序列g(shù)=〈G0,G1〉的匿名化實(shí)例(k=2)

v1,v2v3,v4v5,v8v6,v9v7,v1025,F,TW22,M,TW24,M,TW24,M,TW18,M,US25,M,TW35,M,US33,F,US28,F,JP30,F,JPv1,v2v3,v4v5,v8v6,v925,F,TW22,M,TW24,M,TW24,M,TW18,M,US25,M,TW35,M,US33,F,US(a)Groupingresults(t=0)(b)Groupingresults(t=1)

Fig. 2Grouping results of g=〈G0,G1〉(k=2).
圖2增量序列g(shù)=〈G0,G1〉的分組結(jié)果(k=2)

本文的主要貢獻(xiàn)如下：

1) 引入了增量序列分類安全條件(ISCSC)來(lái)指導(dǎo)匿名過(guò)程，并在此基礎(chǔ)上提出了加權(quán)圖增量序列k-匿名隱私保護(hù)模型，從而有效地防止攻擊者以標(biāo)簽及權(quán)重鏈表為背景知識(shí)的隱私攻擊；

2) 設(shè)計(jì)了一個(gè)基于權(quán)重鏈表的baseline匿名算法WLKA，WLKA算法能夠保證加權(quán)圖增量序列隱私保護(hù)的有效性；

3) 設(shè)計(jì)了基于超圖的HVKA隱私保護(hù)算法，在生成匿名圖的同時(shí)，能夠提高圖數(shù)據(jù)的可用性并減少匿名的時(shí)間代價(jià)；

4) 通過(guò)在真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)測(cè)試和分析，驗(yàn)證了加權(quán)圖增量序列k-匿名隱私保護(hù)模型的有效性以及發(fā)布圖數(shù)據(jù)的高可用性.

1相關(guān)工作

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，社會(huì)網(wǎng)絡(luò)應(yīng)用不斷涌現(xiàn)，管理和分析社會(huì)網(wǎng)絡(luò)數(shù)據(jù)成了研究熱點(diǎn).然而在社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中隱藏著大量的敏感信息，發(fā)布和共享社會(huì)網(wǎng)絡(luò)數(shù)據(jù)會(huì)導(dǎo)致隱私泄露，由此，近年來(lái)越來(lái)越多的研究學(xué)者開(kāi)始把注意力集中到社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)問(wèn)題上，并提出了多種匿名方法.

文獻(xiàn)[2]提出了k-度匿名，用來(lái)防止攻擊者基于結(jié)點(diǎn)度的隱私攻擊，該方法使得匿名圖中對(duì)任意1個(gè)結(jié)點(diǎn)，至少存在k-1個(gè)其他結(jié)點(diǎn)與其度相同.文獻(xiàn)[3]設(shè)計(jì)了k-鄰居匿名方法，用來(lái)防止基于1-鄰居圖的隱私攻擊，該方法使得匿名圖中對(duì)任意一個(gè)結(jié)點(diǎn)的1-鄰居圖，至少存在k-1個(gè)結(jié)點(diǎn)的1-鄰居圖與其同構(gòu).文獻(xiàn)[4]提出了k-自同構(gòu)，是指圖自身存在著k個(gè)同構(gòu)映射，使得攻擊者進(jìn)行結(jié)點(diǎn)身份識(shí)別時(shí)，至少存在k個(gè)候選符合.文獻(xiàn)[5]提出了k-同構(gòu)模型，把社會(huì)網(wǎng)絡(luò)分為k個(gè)子圖，使子圖之間互相同構(gòu)，從而防止隱私泄露.

文獻(xiàn)[6-10]把結(jié)點(diǎn)與鄰居連接邊上的屬性值序列作為背景知識(shí).文獻(xiàn)[6]中把結(jié)點(diǎn)與鄰居連接邊上的屬性值序列定義為權(quán)重包，并提出k-直方匿名，使得對(duì)任意一個(gè)結(jié)點(diǎn)，至少存在k-1個(gè)其他結(jié)點(diǎn)與其權(quán)重包相同；文獻(xiàn)[7]提出的加權(quán)圖匿名化方法是使得對(duì)于任意結(jié)點(diǎn)的權(quán)重包，至少存在k-1個(gè)其他結(jié)點(diǎn)的權(quán)重包與其距離小于閾值，而不是相等；文獻(xiàn)[8]提出了k-可能隱私保護(hù)模型，并通過(guò)邊權(quán)重概括將加權(quán)圖匿名化為k-可能圖；文獻(xiàn)[9]討論了社會(huì)網(wǎng)絡(luò)上的隱私問(wèn)題，并允許用戶設(shè)定個(gè)性化隱私；文獻(xiàn)[10]針對(duì)加權(quán)社會(huì)網(wǎng)絡(luò)中最短路徑識(shí)別提出了加權(quán)圖k-可能路徑匿名隱私保護(hù)模型來(lái)防止基于最短路徑隱私攻擊；文獻(xiàn)[11]針對(duì)障礙空間中保持位置隱私的最近鄰查詢問(wèn)題提出了一種第三方可靠服務(wù)器的方法，該方法能夠保證用戶在享受基于位置服務(wù)所提供的實(shí)際準(zhǔn)確答案的同時(shí)保證位置信息不被泄露.

文獻(xiàn)[12]針對(duì)攻擊者基于結(jié)點(diǎn)屬性值進(jìn)行邊再識(shí)別隱私攻擊，提出了基于聚類的模型.文獻(xiàn)[1]中用帶標(biāo)簽的無(wú)向圖表示社會(huì)網(wǎng)絡(luò)，并把社會(huì)網(wǎng)絡(luò)的演變抽象成一個(gè)增量序列，解決了增量序列上的結(jié)點(diǎn)身份再識(shí)別問(wèn)題.但在現(xiàn)實(shí)世界中存在大量的加權(quán)圖，文獻(xiàn)[1]忽略了權(quán)重對(duì)隱私的影響.因此，本文主要研究動(dòng)態(tài)變化的加權(quán)社會(huì)網(wǎng)絡(luò)上的結(jié)點(diǎn)身份再識(shí)別問(wèn)題.

2背景知識(shí)及問(wèn)題定義

本文主要考慮加權(quán)社會(huì)網(wǎng)絡(luò)增量序列的隱私保護(hù)問(wèn)題.下面對(duì)文中用到的基本概念進(jìn)行詳細(xì)地介紹，為后續(xù)工作奠定基礎(chǔ).

定義1. 加權(quán)圖增量序列.隨時(shí)間增量變化的加權(quán)社會(huì)網(wǎng)絡(luò)表示為gW=〈GW0,GW1,…,GWT〉，時(shí)刻t的社會(huì)網(wǎng)絡(luò)GWt=(Vt,Et,Lt,Wt)，其中，Vt代表時(shí)刻t的結(jié)點(diǎn)集合，Et代表時(shí)刻t結(jié)點(diǎn)間邊的集合，Lt代表時(shí)刻t結(jié)點(diǎn)標(biāo)簽的集合，Wt代表時(shí)刻t權(quán)重鏈表的集合.假設(shè)在t(t=0,1,…,T)的下一時(shí)刻社會(huì)網(wǎng)絡(luò)中頂點(diǎn)和邊的數(shù)量非遞減，即Vt-1?Vt，Et-1?Et，Lt-1?Lt，那么稱gW為加權(quán)圖增量序列.

圖3(a)(b)分別為加權(quán)圖增量序列g(shù)W=〈GW0,GW1〉在時(shí)刻t=0和t=1的快照，時(shí)刻t=1增加的結(jié)點(diǎn)和邊用虛線給出.

Fig. 3　Weighted graph increment sequence gW=〈GW0,GW1〉.圖3　加權(quán)圖增量序列g(shù)W=〈GW0, GW1〉

定義2. 結(jié)點(diǎn)權(quán)重鏈表.?v∈V，把v鄰邊上的權(quán)重值降序排列，就得到v的權(quán)重鏈表，記為w=〈w1,w2,…,wd〉，(w1≥w2≥…≥wd)，其中d是結(jié)點(diǎn)v的度.

定義3. 權(quán)重鏈表統(tǒng)一化.對(duì)圖G(V,E,L,W)中所有結(jié)點(diǎn)進(jìn)行分組得到分組集合C，每個(gè)分組中至少包含k個(gè)結(jié)點(diǎn)，?c∈C，保證c中所有結(jié)點(diǎn)的權(quán)重鏈表相同，則稱這個(gè)過(guò)程為權(quán)重鏈表統(tǒng)一化.

對(duì)圖3(b)所示的加權(quán)圖進(jìn)行分組得到的結(jié)果如圖2(b)所示，結(jié)點(diǎn)v3，v4被分為一組，權(quán)重鏈表分別為w3=〈5,3,2〉，w4=〈3,3,2〉，進(jìn)行權(quán)重鏈表統(tǒng)一化后w3=w4=〈5,3,2〉.

定義4. 結(jié)點(diǎn)身份泄露.給定加權(quán)圖增量序列g(shù)W=〈GW0,GW1,…,GWT〉，如果攻擊者以結(jié)點(diǎn)標(biāo)簽及權(quán)重鏈表為背景知識(shí)能夠準(zhǔn)確識(shí)別出結(jié)點(diǎn)v，則結(jié)點(diǎn)v存在結(jié)點(diǎn)身份泄露.

如圖1(f)，攻擊者根據(jù)結(jié)點(diǎn)Alice的標(biāo)簽{25,M,TW}和權(quán)重鏈表〈3,1〉能以100%的概率識(shí)別出結(jié)點(diǎn)v8是Alice，這說(shuō)明結(jié)點(diǎn)v8存在結(jié)點(diǎn)身份泄露問(wèn)題.

問(wèn)題定義. 加權(quán)圖增量序列匿名化問(wèn)題.

1) 對(duì)匿名圖中任意一條邊e，攻擊者正確識(shí)別其端結(jié)點(diǎn)的概率不大于1k.

2) 對(duì)匿名圖中任意2個(gè)結(jié)點(diǎn)，攻擊者正確判斷該結(jié)點(diǎn)間存在連接的概率不大于1k.

3) 在匿名圖中，攻擊者以結(jié)點(diǎn)標(biāo)簽及權(quán)重鏈表為背景知識(shí)準(zhǔn)確識(shí)別某結(jié)點(diǎn)的概率不大于1k.

3加權(quán)圖增量序列k-匿名隱私保護(hù)模型

為了防止加權(quán)圖增量序列中結(jié)點(diǎn)身份泄露問(wèn)題，本文提出了基于增量序列分類安全條件的k-匿名隱私保護(hù)模型.為了得到滿足隱私目標(biāo)的k-匿名隱私保護(hù)模型，先給出一些例子和性質(zhì).

例1. 如圖3(b)中假設(shè)v1和v3被分為1組，攻擊者可以確定出v1和v3之間存在連接，違反了隱私目標(biāo).另外，對(duì)如圖4所示的圖分組，得到的分組結(jié)果為C={{v1,v2},{v3,v4}}，2個(gè)分組間存在4條邊，攻擊者可以確定v1和v2具有相同的朋友v3和v4，從而造成共同朋友關(guān)系泄露.

Fig. 4　An example of dense links (k=2).圖4　分組間存在大量邊的例子(k=2)

根據(jù)例1的分析，我們可以得到性質(zhì)1.

性質(zhì)1. 對(duì)于gW中任意時(shí)刻原始圖的匿名，同一分組及2個(gè)分組間均不能存在大量的邊，否則會(huì)造成隱私泄露.

例2. 如圖3為加權(quán)圖增量序列g(shù)W=〈GW0,GW1〉，首先對(duì)GW1進(jìn)行匿名，假設(shè)得到的分組結(jié)果為C={{v1,v2},{v3,v4},{v5,v8},{v6,v7},{v9,v10}}.接下來(lái)，通過(guò)移除時(shí)刻t=1添加的結(jié)點(diǎn)和邊得到時(shí)刻t=0的匿名圖，分組結(jié)果變?yōu)镃={{v1,v2},{v3,v4},{v5,v8},{v6}, {v9}}，分組{v6}和{v9}不符合k=2的匿名約束條件，造成隱私泄露. 這樣可以分析得到，時(shí)刻t-1的匿名圖是通過(guò)移除時(shí)刻t(t=1,2,…,T)添加的結(jié)點(diǎn)和邊得到的，由于在移除結(jié)點(diǎn)后，包含移除結(jié)點(diǎn)的分組的大小有可能小于k，所以結(jié)點(diǎn)的移除將會(huì)造成隱私泄露.

根據(jù)例2的分析，我們可以得到性質(zhì)2.

性質(zhì)2. 對(duì)于gW中任意時(shí)刻原始圖的匿名，同一分組中的結(jié)點(diǎn)必須來(lái)自同一時(shí)間戳，否則會(huì)造成隱私泄露.

為了防止上述性質(zhì)1和性質(zhì)2中情況的發(fā)生，本文引入文獻(xiàn)[1]中指導(dǎo)結(jié)點(diǎn)分組過(guò)程的時(shí)間序列分類安全條件，定義加權(quán)圖增量序列匿名的增量序列分類安全條件(incremental sequence class safety condition， ISCSC)，對(duì)結(jié)點(diǎn)分組的過(guò)程中，必須滿足ISCSC.

定義5. 增量序列分類安全條件(ISCSC).對(duì)結(jié)點(diǎn)集Vt的分組滿足ISCSC，當(dāng)且僅當(dāng)?v∈Vt及?C?Vt滿足如下條件：

1) ?v∈Vt′，?w∈Vt′：v∈C∧w∈C?t=t′.

2) ?(v,w)∈Et：v∈C∧w∈C?v=w.

3) ?Ca,Cb?Vt，ne是Ca和Cb之間邊的個(gè)數(shù)?ne≤k.

條件1表明了同一分組中的結(jié)點(diǎn)來(lái)自同一時(shí)間戳；條件2限制了對(duì)任一時(shí)間戳同一分組中不含邊；條件3限制了對(duì)任一時(shí)間戳2個(gè)分組之間邊的數(shù)量.

定理1. 對(duì)加權(quán)圖增量序列g(shù)W=〈GW0,GW1,…,GWT〉的匿名過(guò)程中，滿足增量序列分類安全條件(ISCSC)是實(shí)現(xiàn)隱私目標(biāo)的充分條件.

證明. ISCSC的條件1(?v∈Vt′，?w∈Vt′：v∈C∧w∈C?t=t′)保證了在?時(shí)刻t(t=0,1,…,T)的匿名圖中同一類中的結(jié)點(diǎn)屬于同一時(shí)間戳，也就是說(shuō)，在時(shí)刻t-1(t=1,2,…,T)刪除的結(jié)點(diǎn)都屬于同一個(gè)類，因此刪除后剩余的每個(gè)類中仍包含k個(gè)結(jié)點(diǎn).攻擊者不能根據(jù)多重發(fā)布識(shí)別用戶的身份信息.

ISCSC的條件2(?(v,w)∈Et：v∈C∧w∈C?v=w)限制了對(duì)任一時(shí)間戳同一類中不含邊.如果在時(shí)刻t(t=0,1,…,T)的匿名圖中2個(gè)結(jié)點(diǎn)間存在一個(gè)邊，那么這2個(gè)結(jié)點(diǎn)的真實(shí)標(biāo)簽必然屬于不同的類.此外，匿名后每個(gè)類有k個(gè)標(biāo)簽并且各個(gè)類的標(biāo)簽不重疊.因此，對(duì)于任意一條邊，它的2個(gè)端點(diǎn)都存在k個(gè)候選標(biāo)簽，保證了隱私目標(biāo)1.

ISCSC的條件3(?Ca,Cb?Vt，ne是Ca和Cb之間邊的個(gè)數(shù)?ne≤k)限制了對(duì)任一時(shí)間戳2個(gè)類之間邊的數(shù)量小于或等于k.假設(shè)時(shí)刻t存在2個(gè)類class1和class2，并且用戶user1屬于class1，user2屬于class2，那么用戶user1和user2之間存在邊的概率可表示為

P(edge(user1,user2))=

因?yàn)閏lass1和class2的大小是k，并且概率P(edge(user1,user2))應(yīng)該小于或等于1k，因此可推導(dǎo)出ne≤k.所以2個(gè)類之間邊的數(shù)量小于或等于k保證了隱私目標(biāo)2.

綜合以上3點(diǎn)可知，要想實(shí)現(xiàn)隱私目標(biāo)就必須在分組的過(guò)程中滿足ISCSC，所以滿足ISCSC是實(shí)現(xiàn)隱私目標(biāo)的充分條件.

證畢.

定義6. 加權(quán)圖增量序列k-匿名隱私保護(hù)模型.給定加權(quán)圖增量序列g(shù)W=〈GW0,GW1,…,GWT〉，參數(shù)k.

1) 將圖GWT中所有結(jié)點(diǎn)分成大小至少為k的若干分組，分組過(guò)程滿足ISCSC；

為了提高匿名圖的可用性，將屬性相近的結(jié)點(diǎn)分到同一組或者相鄰組中，對(duì)此我們定義屬性優(yōu)先列表，在分組前根據(jù)屬性優(yōu)先列表將結(jié)點(diǎn)進(jìn)行排序.排序的順序和ISCSC共同決定了結(jié)點(diǎn)的分組.

定義7. 屬性優(yōu)先列表.給定一個(gè)屬性列表a0,a1,…,an，按屬性對(duì)查詢的重要程度降序排列，得到屬性優(yōu)先列表，記為listap={a0,a1,…,an}，對(duì)于任意i

listap=〈location,gender,age〉.

4加權(quán)圖增量序列的隱私保護(hù)算法

為了獲得符合加權(quán)圖增量序列k-匿名隱私保護(hù)模型的匿名序列，本節(jié)首先給出一種基于權(quán)重鏈表的baseline算法WLKA.隨后，為了提高匿名圖的可用性，給出一種基于超圖的高效匿名算法HVKA.

4.1基于權(quán)重鏈表的baseline算法

在研究動(dòng)機(jī)中分析到如果直接采用文獻(xiàn)[1]的方法，也可能會(huì)造成隱私泄露問(wèn)題.本文首先借鑒文獻(xiàn)[1]中對(duì)結(jié)點(diǎn)分組的方法給出了滿足ISCSC的分組算法Grouping，然后在分組算法的基礎(chǔ)上給出基于權(quán)重鏈表的baseline算法WLKA.

算法1. 分組算法(Grouping).

輸入：原始圖GWT、參數(shù)k、屬性優(yōu)先列表listap;

輸出：分組集合C.

① 初始化：有序表Vlist=?，分組集合C=?；

② 根據(jù)listap排序GWT中結(jié)點(diǎn)，返回有序表Vlist；

③ 創(chuàng)建只包含Vlist中第1個(gè)結(jié)點(diǎn)的分組c,C=C∪{c}；

④ FOR ?v∈Vlist

⑤ FOR ?c∈C

⑥ IFSize(c)

⑦c=c∪{v}, break;

⑧ END IF

⑨ END FOR

⑩ IF沒(méi)找到小于k的分組或者不滿足ISCSC THEN

c=c∪{v}；

根據(jù)文獻(xiàn)[1]以及加權(quán)圖增量序列k-匿名隱私保護(hù)模型，可以得到性質(zhì)3.

性質(zhì)3. 分組算法Grouping利用屬性優(yōu)先列表以及ISCSC指導(dǎo)分組得到集合C；再對(duì)C中每個(gè)分組進(jìn)行權(quán)重鏈表統(tǒng)一化.由此得到匿名圖是安全的.

結(jié)合性質(zhì)3和定義5，本文提出了基于權(quán)重鏈表的k-匿名算法(WLKA)，如算法2所示.

算法2. 基于權(quán)重鏈表的k-匿名算法(WLKA).

輸入：加權(quán)圖增量序列g(shù)W=〈GW0,GW1,…,GWT〉；

① 基于Grouping算法生成GWT的分組集合C；

② FOR ?c∈C

③ 對(duì)c中每個(gè)結(jié)點(diǎn)進(jìn)行權(quán)重鏈表統(tǒng)一化；

④ END FOR

⑥ WHILEt!=0

⑦ 移除v∈VtVt-1及與其相連的虛擬結(jié)點(diǎn)，e∈EtEt-1；

⑧ 再次對(duì)每個(gè)分組c中的結(jié)點(diǎn)進(jìn)行權(quán)重鏈表統(tǒng)一化；

⑩t=t-1；

以圖3(a)(b)所示的加權(quán)圖增量序列g(shù)W=〈GW0,GW1〉為例描述WLKA的匿名過(guò)程，匿名結(jié)果如圖5所示.由于對(duì)GW1進(jìn)行權(quán)重鏈表統(tǒng)一化過(guò)程中v6和v9的權(quán)重鏈表維數(shù)不同，因此在v9上添加了虛擬結(jié)點(diǎn)v11，同理也在v10上添加了虛擬結(jié)點(diǎn)v12.

Fig. 5　Anonymous results of WLKA on g=〈GW0,GW1〉.圖5　gW=〈GW0,GW1〉的WLKA匿名結(jié)果

4.2基于超圖的k-匿名算法

算法2為加權(quán)圖增量序列提供了一種有效的匿名算法.WLKA算法為了實(shí)現(xiàn)權(quán)重鏈表統(tǒng)一化，會(huì)添加虛擬結(jié)點(diǎn)，并改變邊權(quán)重，這將導(dǎo)致可用性下降，而且WLKA算法需要對(duì)每一時(shí)刻單獨(dú)進(jìn)行權(quán)重鏈表統(tǒng)一化，帶來(lái)了較大的時(shí)間代價(jià).為了提高匿名序列的可用性和減少時(shí)間代價(jià)，本節(jié)提出一種基于超圖的k-匿名算法HVKA.

給出基于超圖的k-匿名算法HVKA之前，先給出超圖的基本定義以及超圖可用性的性質(zhì).

定義8. 超圖、超邊、超點(diǎn).超圖是指將原圖中所有結(jié)點(diǎn)和邊聚合成若干超點(diǎn)和超邊后構(gòu)成的圖.其中超點(diǎn)hvi代表圖中的一組結(jié)點(diǎn),超邊ehvi,hvj代表超點(diǎn)hvi和hvj間所有可能的邊.

例如，對(duì)圖3(b)所示的GW1中所有結(jié)點(diǎn)聚合得到圖6(a)所示的超圖，結(jié)點(diǎn)v1,v2聚類成超點(diǎn)hv1，結(jié)點(diǎn)v3,v4聚類成超點(diǎn)hv2，超邊ehv1,hv2代表了hv1和hv2間所有的邊ev1,v3，ev2,v4.

Fig. 6　Anonymous results of HVKA on g=〈GW0,GW1〉.圖6　gW=〈GW0,GW1〉的HVKA匿名結(jié)果

下面給出計(jì)算超邊的權(quán)重定義.

超邊的權(quán)重定義為原始圖邊權(quán)重的平均值：

(1)

其中，IJ=E∩(hvi×hvj).

例如，由圖3(b)所示的GW1經(jīng)聚合得到圖6(a)所示的超圖，結(jié)點(diǎn)v1,v2聚類成超點(diǎn)hv1，結(jié)點(diǎn)v3,v4聚類成超點(diǎn)hv2.根據(jù)等式(1)可算得hv1和hv2間的權(quán)重為

w′(hv1,hv2)=[w(v1,v3)+w(v2,v4)]2=3.0.

同理可得：

w′(hv1,hv3)=1.5,

w′(hv1,hv5)=2.5,

w′(hv2,hv3)=4.0,

w′(hv2,hv4)=2.0，

w′(hv2,hv5)=2.0.

算法3給出了聚合算法Aggregating的偽代碼.聚合算法Aggregating的作用是將分組集合C中同一分組中的結(jié)點(diǎn)聚類成超點(diǎn)，不同分組間的邊聚類成超邊，同時(shí)計(jì)算超邊上的權(quán)重，從而得到超圖，也就是匿名圖.

算法3. 聚合算法(Aggregating).

輸入：原始圖GWT及分組集合C；

① FOR ?ci∈C

②hvi={vi}；*建立包含ci中一個(gè)結(jié)點(diǎn)的超點(diǎn)*

③ FOR ?vj∈ci

④hvj={vj}；*建立包含ci中另一個(gè)結(jié)點(diǎn)的超點(diǎn)*

⑤hvnew=hvi∪hvj；*將2個(gè)超點(diǎn)合并*

⑥ui=hvi的鄰結(jié)點(diǎn)；*記錄2個(gè)超點(diǎn)的鄰結(jié)點(diǎn)*

⑦uj=hvj的鄰結(jié)點(diǎn)；

⑧ FOR ?u∈ui∪uj

⑨ 建立超邊eu,hvnew；*建超點(diǎn)與鄰結(jié)點(diǎn)間超邊*

算法4. 基于超圖的k-匿名算法(HVKA).

輸入：加權(quán)圖增量序列g(shù)W=〈GW0,GW1,…,GWT〉；

① 基于Grouping算法生成GWT的分組集合C；

④ WHILEt!=0

⑦t=t-1；

⑧ END WHILE

定理2. 在匿名過(guò)程中，邊權(quán)重改變量越小，匿名圖就能更好地保留原圖的性質(zhì)，可用性就越高.

HVKA算法借助超圖的思想在匿名過(guò)程中對(duì)權(quán)重的改變量較小，并且不需要添加大量虛擬結(jié)點(diǎn).根據(jù)定理2可知，經(jīng)HVKA匿名得到的匿名圖具有高可用性.

(2)

其中，w′(i,j)為匿名后的權(quán)重，W(GWT)為原始圖GWT中所有邊權(quán)重取值之和.

5性能分析與評(píng)價(jià)

本節(jié)對(duì)WLKA和HVKA隱私保護(hù)算法進(jìn)行性能分析和評(píng)價(jià)，采用真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集Cond-Mat-200*http://www.cise.ufl.edu/research/sparse/matrices/Newman/cond-mat-2005和Astro-Ph*https://snap.stanford.edu/data/ca-AstroPh.html進(jìn)行實(shí)驗(yàn)分析和測(cè)試，數(shù)據(jù)集的描述如表1和表2所示.

數(shù)據(jù)集Cond-Mat-2005為科研人員在凝聚態(tài)物理研究領(lǐng)域合作發(fā)表論文的加權(quán)網(wǎng)絡(luò)，分別獲取該網(wǎng)絡(luò)在1995-12-03,1998-03-03,2001-04-03,2005-05-18的圖數(shù)據(jù)，作為加權(quán)圖增量序列的時(shí)刻t=0,1,2,3的社會(huì)網(wǎng)絡(luò)圖.表1展示了每一時(shí)刻增加的結(jié)點(diǎn)和邊的數(shù)目，總共包含了40 421個(gè)結(jié)點(diǎn)和175 692條邊.每條邊的權(quán)重表示科研人員之間合作發(fā)表論文的數(shù)目[13]，Cond-Mat-2005的平均邊權(quán)重值為0.28.

Astro-Ph描述了天體物理學(xué)研究領(lǐng)域中科研人員之間的合作發(fā)表論文的加權(quán)網(wǎng)絡(luò)，表2所示的時(shí)刻t=0,1的社會(huì)網(wǎng)絡(luò)圖是該網(wǎng)絡(luò)在1998-11-06和1999-02-01的圖數(shù)據(jù)，總共包含了16 706個(gè)結(jié)點(diǎn)和121 251條邊.Astro-Ph的平均邊權(quán)重值為0.51.

Table 1　Cond-Mat-2005 Datasets Description

Table 2　Astro-Ph Datasets Description

由于數(shù)據(jù)集Cond-Mat-2005和Astro-Ph都不含標(biāo)簽，所以本文中人工生成了標(biāo)簽和權(quán)重，所有值滿足統(tǒng)一分布.其中標(biāo)簽含有3個(gè)屬性：年齡(10～60)、性別(男或女)以及位置(50個(gè)國(guó)家).實(shí)驗(yàn)測(cè)試的軟硬件環(huán)境如下：1)硬件環(huán)境. Intel Core 2 Quad 2.66 GHz CPU，4 GB DRAM內(nèi)存.2)操作系統(tǒng)平臺(tái).Microsoft Windows 7.3)編程環(huán)境. Java，Eclipse.

5.1執(zhí)行時(shí)間

圖7顯示了在不同數(shù)據(jù)集上，WLKA和HVKA算法的執(zhí)行時(shí)間隨k值大小的變化情況. 從實(shí)驗(yàn)結(jié)果可以看出，HVKA算法的執(zhí)行時(shí)間小于WLKA算法，這是因?yàn)閃LKA算法要單獨(dú)為每一時(shí)刻進(jìn)行權(quán)重鏈表統(tǒng)一化，而HVKA算法則只需在時(shí)刻t=T對(duì)結(jié)點(diǎn)和邊進(jìn)行處理，這就大大減少了匿名邊權(quán)重造成的時(shí)間代價(jià).隨著k值的增大，WLKA和HVKA算法的執(zhí)行時(shí)間均逐漸減少，這是由于k越大分組數(shù)量越少，驗(yàn)證是否符合ISCSC的次數(shù)也越少. 但HVKA算法的執(zhí)行時(shí)間始終小于WLKA算法的執(zhí)行時(shí)間.

Fig. 7　Running time for different k values.圖7　執(zhí)行時(shí)間隨k值的變化

首先考慮匿名權(quán)重對(duì)圖數(shù)據(jù)可用性的影響，即發(fā)布的匿名加權(quán)圖增量序列中邊權(quán)重信息的保持程度.

圖8分別顯示了在2個(gè)數(shù)據(jù)集上不同時(shí)刻邊權(quán)重取值的分布情況.對(duì)于HVKA算法生成的匿名序列中與結(jié)點(diǎn)相連的邊及邊權(quán)重都是不確定的，對(duì)此采用抽樣一致圖方法隨機(jī)抽取與匿名圖一致的圖，然后在此抽樣圖上進(jìn)行分析.主要的做法是為每個(gè)結(jié)點(diǎn)分配候選邊及邊權(quán)重得到抽樣圖，然后統(tǒng)計(jì)抽樣圖的權(quán)重分布，重復(fù)這個(gè)步驟得到多個(gè)抽樣圖的權(quán)重分布，最后取這些權(quán)重分布的平均值作為最終結(jié)果.當(dāng)k=20時(shí)，在圖8(a)～(f)中，經(jīng)過(guò)HVKA算法生成的匿名圖和原始圖的權(quán)重分布十分接近，WLKA算法生成的匿名圖與原始圖有較大的偏差.當(dāng)k=50時(shí)，在圖8(g)(h)中，經(jīng)過(guò)HVKA算法生成的匿名圖和原始圖的權(quán)重分布仍然非常接近，而WLKA算法生成的匿名圖與原始圖有了更大的偏差.

本文利用單跳查詢來(lái)評(píng)估匿名加權(quán)圖增量序列的可用性.單跳查詢涉及同一周期中一對(duì)不同屬性的結(jié)點(diǎn)，形式化描述為：在一個(gè)時(shí)間周期具有某一屬性的結(jié)點(diǎn)和另一屬性結(jié)點(diǎn)間存在多少連接. 例如，

Fig. 8Distribution of edge weight and frequency.
圖8邊權(quán)重與頻率分布情況

在一個(gè)測(cè)量周期，美國(guó)的用戶和日本的用戶間存在多少朋友關(guān)系.本文通過(guò)計(jì)算查詢結(jié)果的平均相對(duì)誤差來(lái)度量匿名方法的可用性.定義相對(duì)誤差為

其中，q是在原始圖上的查詢結(jié)果，q′是匿名圖上的查詢結(jié)果.由于匿名圖中結(jié)點(diǎn)標(biāo)簽是不確定的，所以無(wú)法在匿名圖中執(zhí)行查詢操作，對(duì)此同樣使用抽樣一致圖方法隨機(jī)抽取與匿名圖一致的圖，然后在此抽樣圖上進(jìn)行查詢.

圖9展示了在不同的屬性優(yōu)先隊(duì)列下，對(duì)WLKA算法在2個(gè)數(shù)據(jù)集上得到的匿名序列進(jìn)行單跳查詢所得結(jié)果的相對(duì)誤差隨k值的變化情況.從圖9的4幅圖中均可看出，k越大，每一時(shí)刻單跳查詢的相對(duì)誤差就越大，這是由于隨著k的增加，結(jié)點(diǎn)的候選標(biāo)簽數(shù)隨之增加，從而造成了查詢結(jié)果的相對(duì)誤差越來(lái)越大.圖9(a)為沒(méi)有考慮屬性優(yōu)先隊(duì)列的情況，所有時(shí)間戳的平均相對(duì)誤差都超過(guò)3.2%.圖9(b)則為匿名前按屬性優(yōu)先隊(duì)列l(wèi)istap=〈location,gender,age〉(LGA)對(duì)結(jié)點(diǎn)進(jìn)行排序的情況，平均相對(duì)誤差降到0.4%以下，這是因?yàn)榕判蚝笸环纸M中結(jié)點(diǎn)具有相似的屬性，從而導(dǎo)致單跳查詢的相對(duì)誤差變小.屬性優(yōu)先隊(duì)列對(duì)數(shù)據(jù)集Astro-Ph的影響如圖9(c)(d)所示，再次驗(yàn)證了屬性優(yōu)先隊(duì)列對(duì)減小查詢結(jié)果相對(duì)誤差的重要性.

圖10為對(duì)2個(gè)數(shù)據(jù)集的HVKA匿名序列進(jìn)行單跳查詢所得結(jié)果的相對(duì)誤差隨k值的變化情況.對(duì)比圖9(b)和圖10(a)、圖9(d)和圖10(b)可以看出，HVKA匿名序列單跳查詢的相對(duì)誤差要比WLKA匿名序列單跳查詢的相對(duì)誤差小.這是由于單跳查詢只考慮不同屬性結(jié)點(diǎn)間的關(guān)聯(lián)，HVKA算法的匿名過(guò)程中添加的虛擬結(jié)點(diǎn)不包含邊，所以添加虛擬結(jié)點(diǎn)并沒(méi)有改變匿名序列中邊的總數(shù)，因此對(duì)單跳查詢結(jié)果的影響并不大；而WLKA算法的匿名過(guò)程中為了實(shí)現(xiàn)權(quán)重鏈表統(tǒng)一化會(huì)添加虛擬邊，導(dǎo)致單跳查詢結(jié)果的相對(duì)誤差增大.

Fig. 9　The relative error of single hop query on WLKA anonymous sequences.圖9　WLKA匿名序列單跳查詢的相對(duì)誤差

Fig. 10　The relative error of single hop query on HVKA anonymous sequences.圖10　HVKA匿名序列單跳查詢的相對(duì)誤差

6結(jié)束語(yǔ)

本文研究了加權(quán)圖增量序列的隱私保護(hù)問(wèn)題.為了匿名加權(quán)圖增量序列，本文提出了加權(quán)圖增量序列k-匿名隱私保護(hù)模型，并在此基礎(chǔ)上設(shè)計(jì)了基于權(quán)重鏈表的baseline算法WLKA和基于超圖的k-匿名算法HVKA，從而有效地防止結(jié)點(diǎn)身份再識(shí)別和邊權(quán)重泄露等隱私攻擊.最后基于大量實(shí)驗(yàn)測(cè)試和分析，驗(yàn)證了WLKA算法能夠有效地防止結(jié)點(diǎn)身份泄露和邊權(quán)重泄露；HVKA算法則在保證了加權(quán)圖增量序列隱私保護(hù)有效性的基礎(chǔ)上提高了匿名圖的可用性，同時(shí)也降低了匿名過(guò)程的時(shí)間代價(jià).

參考文獻(xiàn)

[1]Wang C J L, Wang E T, Chen A L P. Anonymization for Multiple Released Social Network Graphs[M] //Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2013: 99-110

[2]Liu K, Terzi E. Towards identity anonymization on graphs[C] //Proc of the 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 93-106

[3]Zhou B, Pei J. Preserving privacy in social networks against neighborhood attacks[C] //Proc of the 24th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2008: 506-515

[4]Zou L, Chen L, ?zsu M T. K-automorphism: A general framework for privacy preserving network publication[J]. The VLDB Journal, 2009, 2(1): 946-957

[5]Cheng J, Fu A W, Liu J. K-isomorphism: Privacy preserving network publication against structural attacks[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 459-470

[6]Yuan M, Chen L. Node protection in weighted social networks[C] //Proc of Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2011: 123-137

[7]Li Y, Shen H. Anonymizing graphs against weight-based attacks[C] //Proc of the Int Conf on Data Mining Workshops (ICDMW). Piscataway, NJ: IEEE, 2010: 491-498

[8]Liu X, Yang X. A generalization based approach for anonymizing weighted social network graphs[C] //Proc of Int Conf on Web-Age Information Management. Berlin: Springer, 2011: 118-130

[9]Yuan M, Chen L, Yu P S. Personalized privacy protection in social networks[J]. The VLDB Journal, 2010, 4(2): 141-150

[10]Chen Ke, Liu Xiangyu, Wang Bin, et al. Anonymizing weighted social network graph against path-based attacks[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(11): 961-972 (in Chinese)(陳可, 劉向宇, 王斌, 等. 防止路徑攻擊的加權(quán)社會(huì)網(wǎng)絡(luò)匿名化技術(shù)[J]. 計(jì)算機(jī)科學(xué)與探索, 2013, 7(11): 961-972)

[11]Zhu Huaijie, Wang Jiaying, Wang Bin, et al. Location privacy preserving obstructed nearest neighbor queries[J]. Journal of Computer Research and Development, 2014, 51(1): 115-125 (in Chinese)

(朱懷杰, 王佳英, 王斌, 等. 障礙空間中保持位置隱私的最近鄰查詢方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 115-125)

[12]Bhagat S, Cormode G, Krishnamurthy B, et al. Class-based graph anonymization for social network data[J]. The VLDB Journal, 2009, 2(1): 766-777

[13]Newman M E J. The structure of scientific collaboration networks[J]. Journal of the National Academy of Sciences, 2001, 98(2): 404-409

Guo Caihua, born in 1990. Master. Her main research interests include social network privacy protect.

Wang Bin, born in 1972. Associate professor. His main research interests include query processing and optimization, and distributed data management.

Zhu Huaijie, born in 1988. PhD candidate. Student member of China Computer Federation. His main research interests include spatial database and management, location privacy.

Yang Xiaochun, born in 1973. Professor and PhD supervisor. Senior member of China Computer Federation. Her main research interests include database technique and theory, and data quality analysis.

Incremental Dynamic Social Network Anonymity Technology

Guo Caihua, Wang Bin, Zhu Huaijie, and Yang Xiaochun

(CollegeofInformationScienceandEngineering,NortheasternUniversity,Shenyang110004)

AbstractWith the rapid development and popularity of social networks, how to protect privacy in social networks has become a hot topic in the realm of data privacy. However, in most of existing anonymity technologies in recent years, the social network is abstracted into a simple graph. In fact, there are a lot of incremental changes of social networks in real life and a simple graph can not reflect incremental society network well, so abstracting the social network into the incremental sequences becomes more realistic. Meanwhile, in real life most of the network contains weight information, that is, a lot of social networks are weighted graphs. Compared with the simple graph, weighted graphs carry more information of the social network and will leak more privacy. In this paper, incremental dynamic social network is abstracted into a weighted graph incremental sequence. In order to anonymize weighted graph incremental sequence, we propose a weighted graph incremental sequencek-anonymous privacy protection model, and design a baseline anonymity algorithm (called WLKA) based on weight list and HVKA algorithm based on hypergraph, which prevents the attacks from node point labels and weight packages. Finally, through a lot of tests on real data sets, it proves that WLKA can guarantee the validity of the privacy protection on weighted graph incremental sequence. Compared with WLKA, HVKA is better to retain the original structure properties and improves the availability of weight information, but it also reduces the time cost of anonymous process.

Key wordsdynamic social network; incremental sequence; data privacy; weight list; hypergraph; loss of information

收稿日期：2014-07-25；修回日期：2015-08-11

基金項(xiàng)目：國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB316201)；國(guó)家自然科學(xué)基金項(xiàng)目(61173031,61272178)；國(guó)家自然科學(xué)基金海外及港澳學(xué)者合作基金項(xiàng)目(61129002)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目(20110042110028)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(N120504001)

通信作者：王斌(binwang@mail.neu.edu.cn)

中圖法分類號(hào)TP311

This work was supported by the National Basic Research Program of China (973 Program) (2012CB316201), the National Natural Science Foundation of China (61173031,61272178), the National Natural Science Foundation of China Grant on International Cooperation (61129002), the Research Fund for the Doctoral Program of Higher Education of China (20110042110028), and the Specialized Fund for the Basic Research Operating Expenses Program of Central College (N120504001).