基于時空簽到的移動社交網(wǎng)絡(luò)關(guān)系推斷

陶玉婷

（東華大學計算機科學與技術(shù)學院 上海市 201600）

1 概述

近些年，隨著基于位置的服務(wù)和在線社交網(wǎng)絡(luò)的流行，移動社交網(wǎng)絡(luò)開始逐漸興起，如Brightkite、Gowalla 等。在社交網(wǎng)絡(luò)中，朋友關(guān)系是一項非常重要和敏感的信息，并可以用來進一步推斷其他敏感信息。例如，通過用戶的8 個朋友關(guān)系就可以推斷其身份信息[1]。雖然已經(jīng)有越來越多的社交網(wǎng)絡(luò)用戶意識到這一點，并且選擇隱藏朋友關(guān)系信息（例如，F(xiàn)acebook 用戶隱藏好友列表的比例從2010年的17.2%上升到2011年的56.2%[2]），但朋友關(guān)系信息仍存在其他泄露途徑。

分享時空簽到（check-in）數(shù)據(jù)，是移動社交網(wǎng)絡(luò)中的關(guān)鍵用戶行為之一。一方面，移動用戶通過簽到來完成社交行為；另一方面，服務(wù)商通過收集并分析用戶簽到信息，來改進用戶服務(wù)、提升服務(wù)體驗。然而，現(xiàn)有研究發(fā)現(xiàn)，由于朋友間在現(xiàn)實中的社交行為可能導致其擁有時空中相近的簽到（例如，一同在餐廳用餐時，各自分享的簽到），因此，用戶的時空簽到數(shù)據(jù)可被用于推斷用戶間朋友關(guān)系[3]。

本文提出了一種基于移動時空簽到數(shù)據(jù)的朋友關(guān)系推斷攻擊方法。首先，通過分析移動軌跡中能夠揭示用戶朋友關(guān)系的個體移動模式和用戶間的交互行為特征，構(gòu)建用戶間的時空關(guān)系矩陣；然后，通過自編碼器實現(xiàn)時空關(guān)系矩陣的向量化；最后，依據(jù)編碼的時空關(guān)系向量實現(xiàn)朋友關(guān)系的推斷攻擊。

2 研究背景

基于移動數(shù)據(jù)的朋友關(guān)系推斷研究主要是從數(shù)據(jù)挖掘的角度，根據(jù)某些觀察抽取有效特征進行朋友關(guān)系推斷。因此，從用戶的移動數(shù)據(jù)中抽取與朋友關(guān)系具有強相關(guān)的移動特征是至關(guān)重要的。該特征能夠有效地區(qū)別朋友關(guān)系對和非朋友關(guān)系對，滿足若兩個用戶的時空交互越頻繁或移動軌跡相似，則他們具有朋友關(guān)系這一條件。

圖1：朋友與非朋友間共享位置數(shù)累計概率分布圖

圖2：朋友關(guān)系推斷攻擊模型結(jié)構(gòu)圖

文獻[3]從移動數(shù)據(jù)中抽取用戶的訪問路徑和停留地點集合，并用分層圖來表示這些地點，如果用戶在較低層共享更多的地點，則認為他們之間的相似程度更高，更有可能是朋友。該方法僅使用用戶個體的移動模式未考慮到用戶間的交互移動特征。文獻[4]發(fā)現(xiàn)兩個人的碰面事件是判斷他們是否是朋友的一個很有力的指示因子。另外，如果該事件發(fā)生在非工作時間或者是非工作地點，他們是朋友的概率更大。在文獻[4]的基礎(chǔ)上，文獻[5]發(fā)現(xiàn)碰面事件涉及到的地點數(shù)越多，他們是朋友的可能性越大。與之前工作不同，文獻[6]從簽到數(shù)據(jù)中提取眾多有效的特征，包括共同出現(xiàn)地點集的時間和空間范圍、地點的多樣性和特征性和社交關(guān)系網(wǎng)的結(jié)構(gòu)特征等，再將這些特征應(yīng)用到多種機器學習技術(shù)推斷用戶對之間是否具有朋友關(guān)系。和文獻[6]類似，文獻[7]運用邏輯回歸二元分類器預(yù)測用戶對之間是否存在朋友關(guān)系，與文獻[6]不同的是該工作僅僅考慮兩個個體碰面次數(shù)這一個特征。這些方法均基于用戶間共享位置或發(fā)生碰面這一假設(shè)，無法推斷那些從未共享過位置的用戶對關(guān)系推斷。

針對上述問題，本文綜合個體移動模式和用戶間的交互行為來構(gòu)建時空關(guān)系矩陣。一方面，該時空關(guān)系矩陣能夠有效推斷用戶間是否存在朋友關(guān)系；另一方面，利用時空關(guān)系矩陣中的個體移動特征可以推斷不存在時空交互的用戶是否存在朋友關(guān)系，有效地解決了現(xiàn)有推斷方法適用性不普遍的問題。

表1：符號定義

表2：數(shù)據(jù)集統(tǒng)計信息

3 基本定義與問題描述

3.1 符號說明

用戶的移動數(shù)據(jù)是若干條簽到記錄的集合，其中每條簽到信息可以定義為一個三元組(u,p,t)∈U×P×T，該三元組表示在t 時刻用戶u 位于位置p。簽到數(shù)據(jù)集合中涉及到的所有用戶用集合U={u1,u2,...,un}來表示，其中n 表示該移動數(shù)據(jù)中包含的用戶個數(shù)。此外，本文使用集合T={t1,t2,...,tn}來表示移動數(shù)據(jù)中所有簽到的時刻集合。因此，用戶u 的移動軌跡T 可以用一系列簽到表示為Tu=〈(u,p1,t1),(u,p2,t2),...,(u,pn,tm)〉,其中tj≤tj+1(1 ≤j ≤n)。上述符號的定義如表1所示。

3.2 共享位置與共享位置數(shù)

定義（共享位置）給定兩個用戶u1∈U 和u2∈U 的移動軌跡 和當且僅當存在使得pm=p 且pn=p，則稱p 為用戶u1和u2的共享位置。

用戶u1和u2移動數(shù)據(jù)的共享位置數(shù)其中表示用戶u1移動數(shù)據(jù)中的所有為位置集合，表示用戶u2移動數(shù)據(jù)中的所有位置集合。

3.3 朋友關(guān)系推斷攻擊

定義（朋友關(guān)系推斷攻擊）給定一組用戶U 以及他們在一段時間內(nèi)的移動軌跡TU，對于U 中的每一對用戶(ua,ub)的移動軌跡均可以通過攻擊模型f 推斷他們之間是否存在朋友關(guān)系。其中攻擊模型f 滿足：

4 實驗數(shù)據(jù)集分析

為了有效地表征用戶對的交互行為，本節(jié)基于實驗數(shù)據(jù)集對用戶間的共享位置數(shù)與朋友關(guān)系的相關(guān)性進行了探究。

4.1 數(shù)據(jù)集概述

本文使用公開的基于位置服務(wù)社交網(wǎng)絡(luò)平臺收集到的Gowalla數(shù)據(jù)集和Brightkite 數(shù)據(jù)集，且每個數(shù)據(jù)集均包含簽到數(shù)據(jù)集和社交網(wǎng)絡(luò)圖兩個部分的數(shù)據(jù)。其中每條簽到記錄的格式為：

＜userID，time，placeID，longitude，latitude＞

對數(shù)據(jù)集中兩個數(shù)據(jù)集的具體信息如表2所示。

4.2 共享位置數(shù)與朋友關(guān)系相關(guān)性分析

針對上述數(shù)據(jù)集進行朋友關(guān)系與共享位置數(shù)之間關(guān)系的探究。將用戶集合U 中的所有用戶兩兩配對，形成若干組無序的用戶對(ui,uj),其中ui∈U 且uj∈U。所有的用戶對根據(jù)社交網(wǎng)絡(luò)圖分成朋友關(guān)系和非朋友關(guān)系兩類分別統(tǒng)計每類用戶對的共享位置數(shù)，并繪制其累計概率分布圖。如圖1所示，Gowalla 數(shù)據(jù)集中的非朋友關(guān)系對中有近98%用戶間從未共享過位置，而朋友關(guān)系中僅有約60%；Brightkite 數(shù)據(jù)集中，非朋友關(guān)系中有近97%的關(guān)系對從未共享過位置，而朋友關(guān)系中僅有35%左右未共享過位置。由此可見，非朋友關(guān)系大概率不存在共享位置，而朋友關(guān)系則更傾向于具有共享的位置。因此，用戶對是否共享過位置以及共享位置的數(shù)目可以成為本文推斷用戶對之間是否存在朋友關(guān)系的一個重要特征。

5 朋友關(guān)系推斷攻擊

由上節(jié)分析可知，共享位置數(shù)是表征一對用戶間是否存在朋友關(guān)系的一個重要指標，但僅使用該指標無法推斷不存在共享位置的用戶對。針對該問題，本文首先綜合用戶個體的移動模式和用戶間的交互特征構(gòu)建用戶對的時空關(guān)系矩陣，然后使用自編碼器將時空關(guān)系矩陣壓縮，使得到的時空關(guān)系特征向量盡可能包含了原矩陣中的信息，最后通過分類器（例如，支持向量機）進行朋友關(guān)系推測。具體的攻擊模型結(jié)構(gòu)如圖2所示。

5.1 時空關(guān)系矩陣的構(gòu)建

首先，基于經(jīng)緯度將位置集合P 映射到I×J 個方格中，時間集合T 分為M 個時長均為τ 的時間片段，將用戶的移動軌跡重構(gòu)成I×J×M 的時空立方體，使得每一個簽到記錄均可投放到該立方體中的某個小立方體中，記作表示時空立方體中第m 個時間片段的第i 個緯度部分和第j 個經(jīng)度部分。

定義（時空關(guān)系矩陣）給定兩個用戶ua和ub的移動軌跡和將軌跡中的簽到投射到I×J×M 的時空立方體中，則用戶對(ua,ub)的時空關(guān)系矩陣

其中na為中用戶ua的簽到數(shù)，nb為中用戶ub的簽到數(shù)，

na,b為中用戶ua和ub的共享位置數(shù)。

空間位置的劃分方法是在二維位置平面通過多次四等份切割保證每個方格中的興趣點個數(shù)不超過一定的閾值σ。由此可見，時空關(guān)系矩陣的稀疏程度是由劃分時空立方體的參數(shù)σ 和τ 決定的。通常，參數(shù)σ 和τ 越小，構(gòu)建的時空關(guān)系矩陣會稀疏，抽取到的移動特征就會越模糊，因此合理的選擇參數(shù)σ 和τ 也是本文實驗過程的一個重要部分。

5.2 時空關(guān)系矩陣的編碼

由于構(gòu)建的用戶對時空關(guān)系矩陣O(a,b)是一個高維度的矩陣，其中包含很多無關(guān)的特征，為了更加準確地抽取到用戶的移動特征，本文利用自編碼器模型[8]對O(a,b)進行向量化的表示。

給定一個時空關(guān)系矩陣O(a,b)，首先送入有R 個隱藏層的編碼器中，然后將編碼器的輸出作為解碼器（與編碼器具有相同的結(jié)構(gòu)）的輸入，解碼器盡可能得到一個與編碼器輸入O(a,b)一致的結(jié)果該過程就是自編碼器（記作A）的整個工作過程，該網(wǎng)絡(luò)中的第r 層輸出結(jié)果可以表示為：

圖3：不同σ 值對攻擊結(jié)果的影響

圖4：不同τ 值對攻擊結(jié)果的影響

圖5：朋友關(guān)系推斷攻擊結(jié)果對比圖

由編碼器和解碼器共同組成的自編碼器通過最小化重構(gòu)誤差L學習網(wǎng)絡(luò)中的參數(shù)和其中損失函數(shù)L 的定義如下[10]：

5.3 朋友關(guān)系推斷攻擊

6 實驗結(jié)果與分析

6.1 實驗方案

6.1.1 實驗參數(shù)設(shè)置

實驗中，編碼器網(wǎng)絡(luò)的每一個隱含層神經(jīng)元的個數(shù)均為前一個隱含層神經(jīng)元個數(shù)的一半，最后一個輸出層神經(jīng)元的個數(shù)為固定的個數(shù)d為128。分類器為SVM模型，其中核函數(shù)為徑向基函數(shù)(Radial Basis Function,RBF)。實驗選擇70%的用戶對數(shù)據(jù)進行訓練，30%的用戶對數(shù)據(jù)進行測試。

6.1.2 對比方法

本文選擇了兩種現(xiàn)有朋友關(guān)系推斷模型進行攻擊性能的對比：

共享位置數(shù)法[9]：該方法通過計算每對用戶之間共享的位置數(shù)作為衡量他們是否具有朋友關(guān)系的知識因子。然后通過SVM 對該特證進行學習，從而實現(xiàn)利用共享位置數(shù)推斷朋友關(guān)系的功能。

活動中心距離法[10]：該方法將用戶簽到數(shù)據(jù)中位置集合的幾何中心作為用戶活動的中心，然后計算每個用戶對活動中心之間的歐式距離，將該距離作為訓練SVM 分類器的特征。

6.1.3 評價指標

本文選擇F1 值作為衡量指標，定義如下：

6.2 參數(shù)σ對攻擊結(jié)果的影響

本節(jié)研究構(gòu)建時空關(guān)系矩陣過程中空間粒度σ 對推斷結(jié)果的影響。實驗評估了500、750、1000、1250 和1500 五種情況下的推斷結(jié)果。實驗結(jié)果如圖3所示，在Gowalla 中，當σ=750 時F1-score達到最大值56%；而在Brighkite 中，σ=1000 時F1-score 達到最大值62%。這是數(shù)據(jù)集中位置分布特征決定，當位置越分散時，參數(shù)σ 取較小值才能較為準確地表達用戶的移動特征。

另一方面，實驗結(jié)果表明σ 的過小或過大均不利于朋友關(guān)系的推測，這是因為σ 過小導致時空關(guān)系矩陣稀疏，難以表達用戶的移動特征；而σ 越大導致時空關(guān)系矩陣種包含過多的噪聲，即偶然事件。

6.3 參數(shù)τ對攻擊結(jié)果的影響

本節(jié)研究構(gòu)建時空關(guān)系矩陣過程中時間粒度τ 對推斷結(jié)果的影響。實驗評估了1 天、1 周、2 周、1 個月和兩個月五種情況下的推斷結(jié)果。實驗結(jié)果如圖4所示，當τ 為一周時兩個數(shù)據(jù)集均達到了最優(yōu)攻擊結(jié)果，這是由于人們的日常生活規(guī)律一般是以周為活動周期的。

與參數(shù)σ 具有相似的規(guī)律，即推斷攻擊結(jié)果的準確性隨著時間粒度τ 的增大先增加再減小。這是由于粗粒度時間片段包含較多的噪音，而細粒度時間片段不易捕獲用戶之間有效的移動特征。

6.4 朋友關(guān)系推斷攻擊結(jié)果

基于上述實驗結(jié)果，本文選擇最佳的參數(shù)即τ=7，σ= 750（Gowalla）或1000（Brightkite）進行實驗，并與兩種基本模型進行對比。實驗結(jié)果如圖5所示，在兩個數(shù)據(jù)集上，本文提出的方法均優(yōu)于共享位置數(shù)方法和活動中心距離方法，其中Brigthkite 數(shù)據(jù)集中本文方法的F1-score 分別提高了37%和30%；Gowalla 數(shù)據(jù)集中分別提高了12%和32%。

7 結(jié)束語

本文就基于移動軌跡推斷朋友關(guān)系這一問題，提出一種新的朋友關(guān)系推斷攻擊方法，該方法通過綜合用戶間的交互特征和用戶個體的移動模式推斷用戶間是否存在朋友關(guān)系。本文提出的攻擊方法具有較高的推斷準確性，適用于未共享位置用戶間的朋友關(guān)系推斷。使用Gowalla 和Brighkite 兩個基于位置社交網(wǎng)絡(luò)的數(shù)據(jù)集驗證了所提出朋友關(guān)系推斷攻擊模型的有效性。實驗結(jié)果表明，兩個數(shù)據(jù)集推斷結(jié)果的F1-score 分別達到了56%和62%。未來工作將針對這類攻擊方法提出合理有效的防御機制。