增量的動態社會網絡匿名化技術

郭彩華　王　斌　朱懷杰　楊曉春

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

?

增量的動態社會網絡匿名化技術

郭彩華王斌朱懷杰楊曉春

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

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

關鍵詞動態社會網絡；增量序列；數據隱私；權重鏈表；超圖；信息損失

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

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

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

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

現有的動態社會網絡隱私保護模型只考慮了簡單的無權圖，并沒有考慮加權圖.對此，本文將社會網絡抽象成加權圖增量序列，并對加權圖增量序列上的隱私問題進行研究.本文是第1篇解決加權圖增量序列隱私保護問題的文章.本文的方法包括3部分：

1) 對加權圖增量序列最后一時刻的原始圖中所有結點分組，分組方法采用文獻[1]中對結點分組的方法，使得同一分組中的結點基于標簽不可區分；

2) 對每個分組中所有結點的權重鏈表匿名，使得同一分組中所有結點基于權重鏈表不可區分；

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

Fig. 1　An example of anonymity incremental sequence g=〈G0,G1〉(k=2).圖1　增量序列g=〈G0,G1〉的匿名化實例(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=〈G0,G1〉的分組結果(k=2)

本文的主要貢獻如下：

1) 引入了增量序列分類安全條件(ISCSC)來指導匿名過程，并在此基礎上提出了加權圖增量序列k-匿名隱私保護模型，從而有效地防止攻擊者以標簽及權重鏈表為背景知識的隱私攻擊；

2) 設計了一個基于權重鏈表的baseline匿名算法WLKA，WLKA算法能夠保證加權圖增量序列隱私保護的有效性；

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

4) 通過在真實數據集上的大量實驗測試和分析，驗證了加權圖增量序列k-匿名隱私保護模型的有效性以及發布圖數據的高可用性.

1相關工作

隨著互聯網技術的迅速發展，社會網絡應用不斷涌現，管理和分析社會網絡數據成了研究熱點.然而在社會網絡數據中隱藏著大量的敏感信息，發布和共享社會網絡數據會導致隱私泄露，由此，近年來越來越多的研究學者開始把注意力集中到社會網絡數據的隱私保護問題上，并提出了多種匿名方法.

文獻[2]提出了k-度匿名，用來防止攻擊者基于結點度的隱私攻擊，該方法使得匿名圖中對任意1個結點，至少存在k-1個其他結點與其度相同.文獻[3]設計了k-鄰居匿名方法，用來防止基于1-鄰居圖的隱私攻擊，該方法使得匿名圖中對任意一個結點的1-鄰居圖，至少存在k-1個結點的1-鄰居圖與其同構.文獻[4]提出了k-自同構，是指圖自身存在著k個同構映射，使得攻擊者進行結點身份識別時，至少存在k個候選符合.文獻[5]提出了k-同構模型，把社會網絡分為k個子圖，使子圖之間互相同構，從而防止隱私泄露.

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

文獻[12]針對攻擊者基于結點屬性值進行邊再識別隱私攻擊，提出了基于聚類的模型.文獻[1]中用帶標簽的無向圖表示社會網絡，并把社會網絡的演變抽象成一個增量序列，解決了增量序列上的結點身份再識別問題.但在現實世界中存在大量的加權圖，文獻[1]忽略了權重對隱私的影響.因此，本文主要研究動態變化的加權社會網絡上的結點身份再識別問題.

2背景知識及問題定義

本文主要考慮加權社會網絡增量序列的隱私保護問題.下面對文中用到的基本概念進行詳細地介紹，為后續工作奠定基礎.

定義1. 加權圖增量序列.隨時間增量變化的加權社會網絡表示為gW=〈GW0,GW1,…,GWT〉，時刻t的社會網絡GWt=(Vt,Et,Lt,Wt)，其中，Vt代表時刻t的結點集合，Et代表時刻t結點間邊的集合，Lt代表時刻t結點標簽的集合，Wt代表時刻t權重鏈表的集合.假設在t(t=0,1,…,T)的下一時刻社會網絡中頂點和邊的數量非遞減，即Vt-1?Vt，Et-1?Et，Lt-1?Lt，那么稱gW為加權圖增量序列.

圖3(a)(b)分別為加權圖增量序列gW=〈GW0,GW1〉在時刻t=0和t=1的快照，時刻t=1增加的結點和邊用虛線給出.

Fig. 3　Weighted graph increment sequence gW=〈GW0,GW1〉.圖3　加權圖增量序列gW=〈GW0, GW1〉

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

定義3. 權重鏈表統一化.對圖G(V,E,L,W)中所有結點進行分組得到分組集合C，每個分組中至少包含k個結點，?c∈C，保證c中所有結點的權重鏈表相同，則稱這個過程為權重鏈表統一化.

對圖3(b)所示的加權圖進行分組得到的結果如圖2(b)所示，結點v3，v4被分為一組，權重鏈表分別為w3=〈5,3,2〉，w4=〈3,3,2〉，進行權重鏈表統一化后w3=w4=〈5,3,2〉.

定義4. 結點身份泄露.給定加權圖增量序列gW=〈GW0,GW1,…,GWT〉，如果攻擊者以結點標簽及權重鏈表為背景知識能夠準確識別出結點v，則結點v存在結點身份泄露.

如圖1(f)，攻擊者根據結點Alice的標簽{25,M,TW}和權重鏈表〈3,1〉能以100%的概率識別出結點v8是Alice，這說明結點v8存在結點身份泄露問題.

問題定義. 加權圖增量序列匿名化問題.

1) 對匿名圖中任意一條邊e，攻擊者正確識別其端結點的概率不大于1k.

2) 對匿名圖中任意2個結點，攻擊者正確判斷該結點間存在連接的概率不大于1k.

3) 在匿名圖中，攻擊者以結點標簽及權重鏈表為背景知識準確識別某結點的概率不大于1k.

3加權圖增量序列k-匿名隱私保護模型

為了防止加權圖增量序列中結點身份泄露問題，本文提出了基于增量序列分類安全條件的k-匿名隱私保護模型.為了得到滿足隱私目標的k-匿名隱私保護模型，先給出一些例子和性質.

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

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

根據例1的分析，我們可以得到性質1.

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

例2. 如圖3為加權圖增量序列gW=〈GW0,GW1〉，首先對GW1進行匿名，假設得到的分組結果為C={{v1,v2},{v3,v4},{v5,v8},{v6,v7},{v9,v10}}.接下來，通過移除時刻t=1添加的結點和邊得到時刻t=0的匿名圖，分組結果變為C={{v1,v2},{v3,v4},{v5,v8},{v6}, {v9}}，分組{v6}和{v9}不符合k=2的匿名約束條件，造成隱私泄露. 這樣可以分析得到，時刻t-1的匿名圖是通過移除時刻t(t=1,2,…,T)添加的結點和邊得到的，由于在移除結點后，包含移除結點的分組的大小有可能小于k，所以結點的移除將會造成隱私泄露.

根據例2的分析，我們可以得到性質2.

性質2. 對于gW中任意時刻原始圖的匿名，同一分組中的結點必須來自同一時間戳，否則會造成隱私泄露.

為了防止上述性質1和性質2中情況的發生，本文引入文獻[1]中指導結點分組過程的時間序列分類安全條件，定義加權圖增量序列匿名的增量序列分類安全條件(incremental sequence class safety condition， ISCSC)，對結點分組的過程中，必須滿足ISCSC.

定義5. 增量序列分類安全條件(ISCSC).對結點集Vt的分組滿足ISCSC，當且僅當?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之間邊的個數?ne≤k.

條件1表明了同一分組中的結點來自同一時間戳；條件2限制了對任一時間戳同一分組中不含邊；條件3限制了對任一時間戳2個分組之間邊的數量.

定理1. 對加權圖增量序列gW=〈GW0,GW1,…,GWT〉的匿名過程中，滿足增量序列分類安全條件(ISCSC)是實現隱私目標的充分條件.

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

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

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

P(edge(user1,user2))=

因為class1和class2的大小是k，并且概率P(edge(user1,user2))應該小于或等于1k，因此可推導出ne≤k.所以2個類之間邊的數量小于或等于k保證了隱私目標2.

綜合以上3點可知，要想實現隱私目標就必須在分組的過程中滿足ISCSC，所以滿足ISCSC是實現隱私目標的充分條件.

證畢.

定義6. 加權圖增量序列k-匿名隱私保護模型.給定加權圖增量序列gW=〈GW0,GW1,…,GWT〉，參數k.

1) 將圖GWT中所有結點分成大小至少為k的若干分組，分組過程滿足ISCSC；

為了提高匿名圖的可用性，將屬性相近的結點分到同一組或者相鄰組中，對此我們定義屬性優先列表，在分組前根據屬性優先列表將結點進行排序.排序的順序和ISCSC共同決定了結點的分組.

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

listap=〈location,gender,age〉.

4加權圖增量序列的隱私保護算法

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

4.1基于權重鏈表的baseline算法

在研究動機中分析到如果直接采用文獻[1]的方法，也可能會造成隱私泄露問題.本文首先借鑒文獻[1]中對結點分組的方法給出了滿足ISCSC的分組算法Grouping，然后在分組算法的基礎上給出基于權重鏈表的baseline算法WLKA.

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

輸入：原始圖GWT、參數k、屬性優先列表listap;

輸出：分組集合C.

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

② 根據listap排序GWT中結點，返回有序表Vlist；

③ 創建只包含Vlist中第1個結點的分組c,C=C∪{c}；

④ FOR ?v∈Vlist

⑤ FOR ?c∈C

⑥ IFSize(c)

⑦c=c∪{v}, break;

⑧ END IF

⑨ END FOR

⑩ IF沒找到小于k的分組或者不滿足ISCSC THEN

c=c∪{v}；

根據文獻[1]以及加權圖增量序列k-匿名隱私保護模型，可以得到性質3.

性質3. 分組算法Grouping利用屬性優先列表以及ISCSC指導分組得到集合C；再對C中每個分組進行權重鏈表統一化.由此得到匿名圖是安全的.

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

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

輸入：加權圖增量序列gW=〈GW0,GW1,…,GWT〉；

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

② FOR ?c∈C

③ 對c中每個結點進行權重鏈表統一化；

④ END FOR

⑥ WHILEt!=0

⑦ 移除v∈VtVt-1及與其相連的虛擬結點，e∈EtEt-1；

⑧ 再次對每個分組c中的結點進行權重鏈表統一化；

⑩t=t-1；

以圖3(a)(b)所示的加權圖增量序列gW=〈GW0,GW1〉為例描述WLKA的匿名過程，匿名結果如圖5所示.由于對GW1進行權重鏈表統一化過程中v6和v9的權重鏈表維數不同，因此在v9上添加了虛擬結點v11，同理也在v10上添加了虛擬結點v12.

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

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

算法2為加權圖增量序列提供了一種有效的匿名算法.WLKA算法為了實現權重鏈表統一化，會添加虛擬結點，并改變邊權重，這將導致可用性下降，而且WLKA算法需要對每一時刻單獨進行權重鏈表統一化，帶來了較大的時間代價.為了提高匿名序列的可用性和減少時間代價，本節提出一種基于超圖的k-匿名算法HVKA.

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

定義8. 超圖、超邊、超點.超圖是指將原圖中所有結點和邊聚合成若干超點和超邊后構成的圖.其中超點hvi代表圖中的一組結點,超邊ehvi,hvj代表超點hvi和hvj間所有可能的邊.

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

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

下面給出計算超邊的權重定義.

超邊的權重定義為原始圖邊權重的平均值：

(1)

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

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

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中同一分組中的結點聚類成超點，不同分組間的邊聚類成超邊，同時計算超邊上的權重，從而得到超圖，也就是匿名圖.

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

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

① FOR ?ci∈C

②hvi={vi}；*建立包含ci中一個結點的超點*

③ FOR ?vj∈ci

④hvj={vj}；*建立包含ci中另一個結點的超點*

⑤hvnew=hvi∪hvj；*將2個超點合并*

⑥ui=hvi的鄰結點；*記錄2個超點的鄰結點*

⑦uj=hvj的鄰結點；

⑧ FOR ?u∈ui∪uj

⑨ 建立超邊eu,hvnew；*建超點與鄰結點間超邊*

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

輸入：加權圖增量序列gW=〈GW0,GW1,…,GWT〉；

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

④ WHILEt!=0

⑦t=t-1；

⑧ END WHILE

定理2. 在匿名過程中，邊權重改變量越小，匿名圖就能更好地保留原圖的性質，可用性就越高.

HVKA算法借助超圖的思想在匿名過程中對權重的改變量較小，并且不需要添加大量虛擬結點.根據定理2可知，經HVKA匿名得到的匿名圖具有高可用性.

(2)

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

5性能分析與評價

本節對WLKA和HVKA隱私保護算法進行性能分析和評價，采用真實社會網絡數據集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進行實驗分析和測試，數據集的描述如表1和表2所示.

數據集Cond-Mat-2005為科研人員在凝聚態物理研究領域合作發表論文的加權網絡，分別獲取該網絡在1995-12-03,1998-03-03,2001-04-03,2005-05-18的圖數據，作為加權圖增量序列的時刻t=0,1,2,3的社會網絡圖.表1展示了每一時刻增加的結點和邊的數目，總共包含了40 421個結點和175 692條邊.每條邊的權重表示科研人員之間合作發表論文的數目[13]，Cond-Mat-2005的平均邊權重值為0.28.

Astro-Ph描述了天體物理學研究領域中科研人員之間的合作發表論文的加權網絡，表2所示的時刻t=0,1的社會網絡圖是該網絡在1998-11-06和1999-02-01的圖數據，總共包含了16 706個結點和121 251條邊.Astro-Ph的平均邊權重值為0.51.

Table 1　Cond-Mat-2005 Datasets Description

Table 2　Astro-Ph Datasets Description

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

5.1執行時間

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

Fig. 7　Running time for different k values.圖7　執行時間隨k值的變化

首先考慮匿名權重對圖數據可用性的影響，即發布的匿名加權圖增量序列中邊權重信息的保持程度.

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

本文利用單跳查詢來評估匿名加權圖增量序列的可用性.單跳查詢涉及同一周期中一對不同屬性的結點，形式化描述為：在一個時間周期具有某一屬性的結點和另一屬性結點間存在多少連接. 例如，

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

在一個測量周期，美國的用戶和日本的用戶間存在多少朋友關系.本文通過計算查詢結果的平均相對誤差來度量匿名方法的可用性.定義相對誤差為

其中，q是在原始圖上的查詢結果，q′是匿名圖上的查詢結果.由于匿名圖中結點標簽是不確定的，所以無法在匿名圖中執行查詢操作，對此同樣使用抽樣一致圖方法隨機抽取與匿名圖一致的圖，然后在此抽樣圖上進行查詢.

圖9展示了在不同的屬性優先隊列下，對WLKA算法在2個數據集上得到的匿名序列進行單跳查詢所得結果的相對誤差隨k值的變化情況.從圖9的4幅圖中均可看出，k越大，每一時刻單跳查詢的相對誤差就越大，這是由于隨著k的增加，結點的候選標簽數隨之增加，從而造成了查詢結果的相對誤差越來越大.圖9(a)為沒有考慮屬性優先隊列的情況，所有時間戳的平均相對誤差都超過3.2%.圖9(b)則為匿名前按屬性優先隊列listap=〈location,gender,age〉(LGA)對結點進行排序的情況，平均相對誤差降到0.4%以下，這是因為排序后同一分組中結點具有相似的屬性，從而導致單跳查詢的相對誤差變小.屬性優先隊列對數據集Astro-Ph的影響如圖9(c)(d)所示，再次驗證了屬性優先隊列對減小查詢結果相對誤差的重要性.

圖10為對2個數據集的HVKA匿名序列進行單跳查詢所得結果的相對誤差隨k值的變化情況.對比圖9(b)和圖10(a)、圖9(d)和圖10(b)可以看出，HVKA匿名序列單跳查詢的相對誤差要比WLKA匿名序列單跳查詢的相對誤差小.這是由于單跳查詢只考慮不同屬性結點間的關聯，HVKA算法的匿名過程中添加的虛擬結點不包含邊，所以添加虛擬結點并沒有改變匿名序列中邊的總數，因此對單跳查詢結果的影響并不大；而WLKA算法的匿名過程中為了實現權重鏈表統一化會添加虛擬邊，導致單跳查詢結果的相對誤差增大.

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

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

6結束語

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

參考文獻

[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)(陳可, 劉向宇, 王斌, 等. 防止路徑攻擊的加權社會網絡匿名化技術[J]. 計算機科學與探索, 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]. 計算機研究與發展, 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

基金項目：國家“九七三”重點基礎研究發展計劃基金項目(2012CB316201)；國家自然科學基金項目(61173031,61272178)；國家自然科學基金海外及港澳學者合作基金項目(61129002)；高等學校博士學科點專項科研基金項目(20110042110028)；中央高校基本科研業務費專項資金項目(N120504001)

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

中圖法分類號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).