結(jié)合全局種子最優(yōu)局部擴展的跨網(wǎng)絡(luò)用戶識別*

李 想，申德榮，馮 朔，寇 月，聶鐵錚

東北大學(xué) 計算機科學(xué)與工程學(xué)院，沈陽110819

1 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，社交網(wǎng)絡(luò)極大地改變了人們的生活方式。例如，微博為網(wǎng)民提供短消息分享發(fā)布服務(wù)，抖音為網(wǎng)民提供短視頻分享服務(wù)，知乎為網(wǎng)民提供了問答知識服務(wù)，可見由于不同社交網(wǎng)絡(luò)側(cè)重于不同服務(wù)方式，用戶通常選擇活躍于多個社交網(wǎng)絡(luò)中。然而，為準(zhǔn)確高效地進(jìn)行商業(yè)產(chǎn)品推薦、社交好友推薦、網(wǎng)絡(luò)安全以及合并通訊錄等用戶服務(wù)，如何有效集成分散于不同社交網(wǎng)絡(luò)中的用戶數(shù)據(jù)，尤其是跨社交網(wǎng)絡(luò)用戶識別問題，是目前急需解決的關(guān)鍵問題。

針對跨社交網(wǎng)絡(luò)用戶識別問題，現(xiàn)有方法[1-7]主要基于已匹配用戶的信息，包括屬性信息、行為信息和結(jié)構(gòu)信息。本文主要利用用戶結(jié)構(gòu)信息進(jìn)行用戶識別。

傳統(tǒng)基于用戶結(jié)構(gòu)信息的方法通常迭代地對待匹配用戶進(jìn)行識別，在每次迭代過程中，僅識別部分相似度較高的待匹配用戶，其中相似度函數(shù)通常利用用戶共同鄰居數(shù)量進(jìn)行衡量，共同鄰居數(shù)量越多，其相似性越大，反之越少。若用戶相似性大于指定閾值，則可視為新匹配用戶，并作為下次迭代過程的輸入。

如何快速有效地選取用戶候選集是傳統(tǒng)方法中的關(guān)鍵性問題，主要有兩種用戶候選集選取方式[8]：

（1）枚舉方式[9-10]：該類方法從剩余的待匹配的用戶中選擇候選匹配用戶。枚舉的用戶候選集合選取方式在最壞情況的時間消耗是N×N（N為社交網(wǎng)絡(luò)中用戶的個數(shù)），雖然能處理大量待匹配用戶，但是具有較高的時間代價。

（2）局部擴展：現(xiàn)有局部擴展方法[4-5,11-12]是從已知匹配用戶的鄰居中選取候選匹配用戶。局部擴展的用戶候選集合選取方式時間代價小，但是僅僅通過鄰居進(jìn)行擴展不能處理大量的潛在的匹配用戶，準(zhǔn)確性較低。

目前大部分方法在候選匹配用戶集選取過程中，難以有效平衡時間代價與準(zhǔn)確率召回率之間的關(guān)系，無法在較低的時間內(nèi)精準(zhǔn)選取候選匹配用戶集合。

分析已有方法，具有如下幾點不足：

（1）存在冷啟動問題，當(dāng)已知匹配用戶數(shù)量過少時，難以區(qū)分匹配用戶，將嚴(yán)重降低匹配結(jié)果的準(zhǔn)確率與召回率。

（2）在候選匹配用戶集選取過程中，難以有效平衡時間代價與準(zhǔn)確率召回率之間的關(guān)系，無法在較低的時間內(nèi)精準(zhǔn)選取候選匹配用戶集合。

針對上述不足，本文的貢獻(xiàn)如下：

（1）針對已知匹配用戶數(shù)量過少的問題，提出了全局種子擴充模型。根據(jù)已有的少量種子節(jié)點對網(wǎng)絡(luò)中的其他節(jié)點進(jìn)行表示，對含有豐富信息的節(jié)點進(jìn)行匹配，豐富種子節(jié)點。

（2）針對無法在較低的時間內(nèi)精準(zhǔn)選取候選匹配用戶集合，提出了最優(yōu)局部擴展模型。給定種子節(jié)點，找到源網(wǎng)絡(luò)中種子節(jié)點的鄰居節(jié)點在目的網(wǎng)絡(luò)中的最優(yōu)匹配節(jié)點。

（3）提出了結(jié)合全局種子最優(yōu)局部擴展的跨網(wǎng)絡(luò)用戶識別框架，并在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上設(shè)計對比實驗，證明了本文方法具有一定的優(yōu)勢。

2 相關(guān)工作

現(xiàn)有研究主要基于已匹配用戶的信息，包括屬性信息、行為信息和結(jié)構(gòu)信息，建立二分類模型進(jìn)行用戶識別。

傳統(tǒng)基于用戶結(jié)構(gòu)信息的方法通常迭代地對待匹配用戶進(jìn)行識別，在每次迭代過程中，僅識別部分相似度較高的待匹配用戶，若用戶相似性大于指定閾值，則可視為新匹配用戶，并作為下次迭代過程的輸入。在傳統(tǒng)識別方法中，用戶候選集選取方法是關(guān)鍵環(huán)節(jié)，主要有兩種用戶候選集選取方式：（1）枚舉方式；（2）局部擴展。

有關(guān)枚舉方式候選集選取，文獻(xiàn)[9]基于網(wǎng)絡(luò)中的鄰居屬性，先只匹配兩個網(wǎng)絡(luò)中度高的用戶，讓度高的用戶成為候選匹配用戶，之后逐漸降低可成為候選匹配用戶的閾值條件，度較低的用戶也可進(jìn)行匹配；文獻(xiàn)[2]提出了一種半監(jiān)督多目標(biāo)框架，基于用戶屬性、用戶話題和用戶風(fēng)格的異構(gòu)網(wǎng)絡(luò)，建立多目標(biāo)的用戶匹配模型；文獻(xiàn)[10]提供了一個用于分析社交網(wǎng)絡(luò)中的隱私和匿名化的框架，并開發(fā)一種針對匿名社交網(wǎng)絡(luò)圖的去匿名識別算法。

基于枚舉方式候選集選取方法[9-10]建立的用戶匹配模型作用于兩個網(wǎng)絡(luò)中待匹配的用戶。這種方法在最壞情況的時間消耗是N×N（N為網(wǎng)絡(luò)中的用戶個數(shù)），當(dāng)社交網(wǎng)絡(luò)中的用戶量是百萬級甚至是千萬級別，枚舉方式候選集選取方法雖然保證了準(zhǔn)確性，但是具有較高的時間代價。

有關(guān)局部擴展候選集選取，文獻(xiàn)[4]從社交網(wǎng)絡(luò)的用戶關(guān)系、概要屬性和時空信息中抽取特征，基于穩(wěn)定婚姻匹配約束用戶的映射關(guān)系；文獻(xiàn)[11]提出一種基于規(guī)則的傳播算法，首先根據(jù)用戶的網(wǎng)絡(luò)拓?fù)鋵傩缘泥従訉傩陨蓛蓚€網(wǎng)絡(luò)中的候選匹配用戶，然后根據(jù)用戶的屬性信息識別匹配的用戶；文獻(xiàn)[12]提出了一種基于能量模型綜合考慮局部一致性和全局一致性的用戶識別模型；文獻(xiàn)[13]提出了基于朋友關(guān)系的用戶識別框架，基于用戶網(wǎng)絡(luò)屬性中的鄰居建立半監(jiān)督傳播算法。

文獻(xiàn)[5]在選取候選匹配用戶時候，從已經(jīng)匹配用戶的兩層內(nèi)的鄰居選取候選匹配用戶，準(zhǔn)確性有一定的提高，但是沒有考慮如何給出適合的擴展范圍。

上述局部擴展候選集選取方法大多選取已知匹配用戶的鄰居作為候選匹配用戶，但是存在一個問題：在尋找源網(wǎng)絡(luò)中已匹配用戶的鄰居對應(yīng)于目的網(wǎng)絡(luò)中的匹配用戶時，未知的匹配用戶不一定在目的網(wǎng)絡(luò)中已匹配用戶的一層鄰居上，可能存在于已匹配用戶的一層、兩層、三層甚至多層鄰居。因此該方法雖然節(jié)省時間，但是準(zhǔn)確性有待提高。

有關(guān)基于迭代的用戶匹配方法存在著冷啟動問題，主要解決思想是優(yōu)先匹配能傳播更多信息的用戶來加快迭代過程。文獻(xiàn)[14]將用戶的度作為用戶含有信息量的評判標(biāo)準(zhǔn)，在識別兩個網(wǎng)絡(luò)中的用戶時，優(yōu)先識別一些度較高的用戶；文獻(xiàn)[15]挖掘了用戶社區(qū)信息，先將兩個網(wǎng)絡(luò)中劃分好的社區(qū)進(jìn)行社區(qū)級別的匹配，然后在兩個網(wǎng)絡(luò)間匹配好的社區(qū)進(jìn)行用戶級別的匹配，最后去除社區(qū)概念將兩個網(wǎng)絡(luò)之間的用戶進(jìn)行全局匹配。

綜上，目前大部分方法在候選匹配用戶集選取過程中，難以有效平衡時間代價與準(zhǔn)確率召回率之間的關(guān)系，無法在較低的時間內(nèi)精準(zhǔn)選取候選匹配用戶集合。同時由于已匹配節(jié)點和用戶信息稀疏，導(dǎo)致冷啟動問題嚴(yán)重和識別準(zhǔn)確性低。

本文提出結(jié)合全局種子最優(yōu)局部擴展的跨網(wǎng)絡(luò)用戶識別方法，能夠有效改善冷啟動問題，并且在顯著提高用戶識別的召回率和準(zhǔn)確率同時具有較低的時間開銷。

3 問題定義

給出兩個網(wǎng)絡(luò)和已知的匹配用戶集合（下面描述中用種子集合描述），目標(biāo)是找到兩個網(wǎng)絡(luò)之間的匹配用戶集合（下面的描述中用節(jié)點替代用戶）。本章主要介紹跨社交網(wǎng)絡(luò)的用戶識別的定義和問題描述。

定義1（社交網(wǎng)絡(luò)）給定G(V,E) 來表示社交網(wǎng)絡(luò)，其中v節(jié)點表示用戶，V代表節(jié)點的集合，E代表用戶節(jié)點間的關(guān)系（邊）的集合。Gs表示源網(wǎng)絡(luò)，Gt表示目的網(wǎng)絡(luò)。

定義2（跨網(wǎng)絡(luò)用戶識別）給定兩個網(wǎng)絡(luò)：源網(wǎng)絡(luò)Gs和目的網(wǎng)絡(luò)Gt，跨網(wǎng)絡(luò)用戶識別的任務(wù)是預(yù)測分別屬于兩個網(wǎng)絡(luò)的用戶是不是現(xiàn)實一個人。

當(dāng)是一個人時，函數(shù)值為1，否則為0。

定義3（種子節(jié)點）在源網(wǎng)絡(luò)和目的網(wǎng)絡(luò)兩個網(wǎng)絡(luò)之間已經(jīng)匹配出來的節(jié)點，例如源網(wǎng)絡(luò)中的節(jié)點和目的網(wǎng)絡(luò)中的節(jié)點是已匹配節(jié)點，則是一對種子節(jié)點，A表示種子集合。

4 跨社交網(wǎng)絡(luò)用戶匹配模型

本文從兩方面來提高用戶識別的準(zhǔn)確性。首先，將節(jié)點根據(jù)到少量種子的距離進(jìn)行向量表示，將向量中含有豐富信息的節(jié)點作為候選節(jié)點進(jìn)行匹配，將稀疏的種子節(jié)點進(jìn)行擴充來解決冷啟動問題。然后，在保證較低時間復(fù)雜性的情況下，基于已匹配的節(jié)點進(jìn)行最優(yōu)局部擴展，來匹配大量潛在的候選匹配節(jié)點。

此模型包括全局種子擴充和最優(yōu)局部擴展兩個階段，如圖1 所示。

在第一階段，基于節(jié)點到種子節(jié)點的距離進(jìn)行向量化表示，對兩個網(wǎng)絡(luò)中含有豐富信息的節(jié)點進(jìn)行相互匹配，以此來擴充種子節(jié)點對的數(shù)量。

Fig.1 Cross-network user matching model圖1 跨網(wǎng)絡(luò)用戶匹配模型

在第二階段，基于種子節(jié)點進(jìn)行最優(yōu)局部擴展來提高局部擴展的范圍的同時降低時間開銷。尋找源網(wǎng)絡(luò)中的已匹配用戶的鄰居中的待匹配用戶是從目的網(wǎng)絡(luò)的已匹配用戶的n層鄰居中尋找，其中提出全局最優(yōu)節(jié)點和局部最優(yōu)節(jié)點的概念降低n層鄰居的層數(shù)和分支達(dá)到分支限定的作用。

在第一次匹配完成后，更新種子節(jié)點的集合，再次進(jìn)行第二階段的最優(yōu)擴展，實現(xiàn)節(jié)點匹配的迭代過程。

5 全局種子擴充模型

根據(jù)已知的少量種子節(jié)點，對網(wǎng)絡(luò)中的其他節(jié)點進(jìn)行向量表示。將向量中含有豐富信息的節(jié)點作為候選節(jié)點進(jìn)行匹配，將大于閾值的節(jié)點添加到種子集合中，完成全局種子節(jié)點擴充。

5.1 基于種子節(jié)點的節(jié)點向量化表示

將網(wǎng)絡(luò)中的節(jié)點到種子節(jié)點的距離進(jìn)行向量化表示。

初始給定有少量種子節(jié)點aij（源網(wǎng)絡(luò)中節(jié)點和目的網(wǎng)絡(luò)中的節(jié)點是已匹配的用戶），將這些種子節(jié)點作為參照點，將網(wǎng)絡(luò)中的待匹配節(jié)點到種子節(jié)點的距離進(jìn)行向量化表示。如式（1）所示，將用戶v到已匹配用戶ai的距離進(jìn)行向量化表示，表示為vec(v)，其中d(v,a)代表用戶到已知匹配用戶的距離。

從種子節(jié)點逐層擴展，在擴展的過程中豐富節(jié)點的向量信息，如圖2 所示。

Fig.2 Node representation process based on seed nodes圖2 基于種子節(jié)點的節(jié)點表示過程

橙色節(jié)點代表網(wǎng)絡(luò)中的種子節(jié)點，從橙色的種子節(jié)點逐層擴展（最多擴展6 層）。例如，灰色節(jié)點和藍(lán)色節(jié)點分別為距離種子節(jié)點為1 和2 的節(jié)點。在擴展的過程中，將對應(yīng)的距離信息記錄在遍歷到的節(jié)點的向量中。節(jié)點表示的算法如下：

算法1基于種子節(jié)點的節(jié)點向量生成算法

輸入：社交網(wǎng)絡(luò)G種子集合A，閾值k。

輸出：社交網(wǎng)絡(luò)G。

在第2 行、第3 行，讀取已知種子節(jié)點中的一個，并將這個已知的種子節(jié)點初始化；第8 行、第9 行計算其他節(jié)點到已知的種子節(jié)點的距離；第10 行～第12行記錄節(jié)點信息的豐富程度（Info），Info值高的節(jié)點被認(rèn)為是節(jié)點的向量信息豐富的節(jié)點，第5.2 節(jié)對Info指標(biāo)進(jìn)行說明。

5.2 全局種子擴充模型

在兩個網(wǎng)絡(luò)中，選取含有豐富信息的節(jié)點作為候選匹配節(jié)點，進(jìn)行相互匹配，將大于閾值的節(jié)點添加到種子節(jié)點集合。

評價節(jié)點的信息的豐富度有三個指標(biāo)：節(jié)點向量所具有的有效維度dim、節(jié)點連通的種子節(jié)點的個數(shù)link_nodes和節(jié)點連通種子節(jié)點的方向個數(shù)dir。下面分別定義并且介紹這三個指標(biāo)。

節(jié)點向量所具有的有效維度dim見式（2）：

其中，passed(k)為節(jié)點k被種子節(jié)點遍歷時，被遍歷節(jié)點k記錄下來的所有經(jīng)過k節(jié)點的種子節(jié)點集合。節(jié)點向量所具有的有效維度dim為passed(k)的個數(shù)。

節(jié)點連通的種子節(jié)點的個數(shù)link_nodes見式（3）：

其中，path(i,j)為種子節(jié)點i到種子節(jié)點j路徑上的節(jié)點的集合；link_node(k)為種子節(jié)點之間被節(jié)點k連接的次數(shù)。

節(jié)點連通種子節(jié)點的方向個數(shù)dir見式（4）：

如果節(jié)點在兩個種子節(jié)點連接的路徑上沒有其他種子節(jié)點的出現(xiàn)，節(jié)點連通種子節(jié)點的方向個數(shù)dir就是節(jié)點連通的種子節(jié)點的個數(shù)link_nodes，一旦在兩個種子節(jié)點連接的路徑上出現(xiàn)其他種子節(jié)點，相應(yīng)的方向數(shù)就減1。例如圖3 所示。

Fig.3 dir calculation example diagram of node圖3 節(jié)點的dir 計算示例圖

左側(cè)圖中的節(jié)點3 出現(xiàn)在種子節(jié)點2 到6，2 到7,2 到8，6 到7，6 到8 和7到8的連接路徑共6次，link_nodes(3)和dir(3)都是6。而右側(cè)圖中的節(jié)點3 出現(xiàn)在種子節(jié)點2 到6，2 到8，6 到7，6 到8 和7 到8 的連接路徑共5 次。link_nodes(3)的值為5，因為種子節(jié)點2 在6 到7 和6 到8 之間出現(xiàn)，所以dir(3)的值是3。

節(jié)點的信息豐富度用變量Info表示，見式（5）：

在全局種子豐富的過程中選取Info達(dá)到閾值k的節(jié)點進(jìn)行匹配。參數(shù)α（α為關(guān)于種子節(jié)點個數(shù)的可變參數(shù)）、β、γ和閾值k的選取在實驗部分第7 章進(jìn)行討論。

下面給出全局種子節(jié)點擴充算法。

算法2全局種子擴充算法

輸入：社交網(wǎng)絡(luò)Gs和Gt，分?jǐn)?shù)閾值scr,Info閾值k，種子集合A。

輸出：種子集合A。

在第1 行～第5 行，選取源網(wǎng)絡(luò)中向量信息豐富的節(jié)點，即節(jié)點的Info值大于閾值k的節(jié)點；在第6行～第10 行，選取目的網(wǎng)絡(luò)中向量信息豐富的節(jié)點，即節(jié)點的Info值大于閾值k的節(jié)點；在第11 行～第15行，將兩個網(wǎng)絡(luò)中信息豐富的節(jié)點進(jìn)行匹配，將匹配結(jié)果大于閾值的節(jié)點加入到種子集合中，相似度分?jǐn)?shù)由式（6）給出。

6 基于種子節(jié)點的最優(yōu)局部擴展模型

給定種子節(jié)點，找到源網(wǎng)絡(luò)中種子節(jié)點的鄰居節(jié)點在目的網(wǎng)絡(luò)中的最優(yōu)匹配節(jié)點。

6.1 基于種子節(jié)點擴展的搜索范圍

Fig.4 Search range based on seed node extension圖4 基于種子節(jié)點擴展的搜索范圍

6.2 最優(yōu)局部擴展模型

基于種子的最優(yōu)局部擴展模型找出在目的網(wǎng)絡(luò)中以種子節(jié)點為根的樹的最優(yōu)搜索范圍，并且在范圍內(nèi)找到最優(yōu)的匹配節(jié)點。

在現(xiàn)有基于種子擴展的算法中都是基于直接鄰居進(jìn)行擴展的，但是這樣存在一個問題。如圖5，圖中＜A，a＞是一對種子節(jié)點，從Gs中A的鄰居E向Gt中a的鄰居識別。由于只能在a的鄰居中識別，因此可能錯誤匹配到其他節(jié)點或者是匹配不到。因為在真實世界中，存在A中第一跳鄰居E和a的第二跳鄰居e對應(yīng)的事實。

Fig.5 Process of expansion of the first layer圖5 第一層擴展匹配過程

為解決上述存在的問題，在匹配過程中，需要將目標(biāo)網(wǎng)絡(luò)的種子節(jié)點的搜索范圍進(jìn)行擴大。但是考慮到簡單擴大帶來的時間損失和擴展如何收斂的問題，下面提出了最優(yōu)局部擴展策略。本文不同于已有算法，采用局部歷史最優(yōu)和全局最優(yōu)的思想來進(jìn)行剪枝的決策，進(jìn)行節(jié)點的匹配。其中，局部最優(yōu)節(jié)點是在每個分支路徑中分?jǐn)?shù)最高的節(jié)點；全局最優(yōu)節(jié)點是在上一次擴展中分?jǐn)?shù)最高的節(jié)點。

下面通過例子說明，如圖6 所示。

Fig.6 Process of expansion of the second layer圖6 第二層擴展匹配過程

假設(shè)給定源網(wǎng)絡(luò)Gs、目標(biāo)網(wǎng)絡(luò)Gt和種子集合，目的是找Gs中A的鄰居E在Gt中的對應(yīng)節(jié)點。

節(jié)點匹配過程：

第一次擴展：令a的鄰居f、j、g、b四個節(jié)點分別計算和E的相似性，j的分?jǐn)?shù)最高為全局最優(yōu)，下一次擴展時，所有節(jié)點向它靠近。

第二次擴展：擴展全局最優(yōu)節(jié)點j的所有鄰居，擴展非全局最優(yōu)節(jié)點f、g、b中距離上一次全局最優(yōu)節(jié)點j距離最近的節(jié)點h、c、l。此時，在分支擴展中從g到c出現(xiàn)分?jǐn)?shù)降低，g為這個分支上的局部歷史最優(yōu)，從c回退到g。

不斷擴展，最后當(dāng)全局最優(yōu)節(jié)點不變時，算法結(jié)束。

算法3最優(yōu)局部擴展算法

輸入：社交網(wǎng)絡(luò)Gs和Gt，種子節(jié)點，種子節(jié)點集合A。

輸出：更新后的種子節(jié)點集合A。

第1 行，找到源網(wǎng)絡(luò)中種子節(jié)點的全部鄰居和目的網(wǎng)絡(luò)中對應(yīng)的節(jié)點；第2 行、第3 行，初始化，將種子節(jié)點入棧作為全局最優(yōu)節(jié)點；第4 行～第15 行，基于種子節(jié)點找到源網(wǎng)絡(luò)中種子節(jié)點的鄰居在目的網(wǎng)絡(luò)中對應(yīng)的節(jié)點；第4 行，如果全局最優(yōu)節(jié)點不變時，算法收斂，匹配結(jié)束；第8 行、第9 行，如果是全局最優(yōu)節(jié)點，則擴展全局最優(yōu)節(jié)點的所有鄰居，入棧；第11 行～第13 行，如果是局部最優(yōu)節(jié)點，則只擴展一個分支；在第14 行更新全局最優(yōu)節(jié)點是根據(jù)匹配函數(shù)得到的分?jǐn)?shù)進(jìn)行評價的，相似度分?jǐn)?shù)根據(jù)共同鄰居確定，相似度分?jǐn)?shù)由式（7）給出。

7 實驗與結(jié)果

本章分別在模擬數(shù)據(jù)集（S_DS：simulated data set）和真實數(shù)據(jù)集（R_DS：real data set）上對提出的方法進(jìn)行實驗評估。

7.1 實驗數(shù)據(jù)集

實驗采用的數(shù)據(jù)集分為兩種：S_DS 和R_DS。

由于一組R_DS 具有特征性不具有普遍性，因此通過GNP（generate a graph withNnodes and edges with probabilityp）算法生成S_DS 來模擬真實網(wǎng)絡(luò)，保證提出的方法得到更具備普遍性的實驗結(jié)果。

GNP 算法以概率p將N個節(jié)點進(jìn)行連接，生成一個無向圖G，在無向圖G的基礎(chǔ)上，以概率v1刪除G上的節(jié)點并且以概率e1刪除G上的邊生成圖G1。同時，以概率v2刪除G上的節(jié)點并且以概率e2刪除G上的邊生成圖G2，表1 為S_DS 的基本信息。

Table 1 Simulated data set表1 模擬數(shù)據(jù)集

真實數(shù)據(jù)（R_DS）來自于社交網(wǎng)絡(luò)facebook。其中，facebook_links 是facebook 上的好友關(guān)系的數(shù)據(jù)集，facebook_wall是facebook 照片墻功能模塊的數(shù)據(jù)集。表2 為R_DS 的基本信息（https://pan.baidu.com/s/1OHxljahQWOh6JRjUGX4Bkw，提取密碼15lv）。

Table 2 Real data set表2 真實數(shù)據(jù)集

7.2 對比實驗與評估

本文提出的方法GLE（global seed extension and optimal local extension）與MNA（multi-network anchoring）[4]、ALLEN-MLP（ALLEN based on multilayer perceptron）[5]算法進(jìn)行對比實驗。

MNA：從社交網(wǎng)絡(luò)的用戶關(guān)系、概要屬性和時空信息中抽取特征，基于穩(wěn)定婚姻匹配約束用戶的映射關(guān)系。

ALLEN-MLP：結(jié)合用戶的家鄉(xiāng)的位置信息，基于種子節(jié)點的二層鄰居進(jìn)行局部擴展。

GLE：基于少量種子將種子節(jié)點豐富，然后進(jìn)行最優(yōu)局部擴展。

本文提出的第一階段的應(yīng)對冷啟動的GSE（global seed expansion）方法與ECRN（emergence of scaling in random networks）[14]、CED（community-enhanced de-anonymization）[15]算法進(jìn)行對比實驗。

ECRN：將用戶的度作為用戶含有信息量的評判標(biāo)準(zhǔn)，在識別兩個網(wǎng)絡(luò)中的用戶時，優(yōu)先識別一些度較高的用戶。

CED：挖掘了用戶社區(qū)信息，先將兩個網(wǎng)絡(luò)中劃分好的社區(qū)進(jìn)行社區(qū)級別的匹配，然后在兩個網(wǎng)絡(luò)間匹配好的社區(qū)進(jìn)行用戶級別的匹配，最后去除社區(qū)概念將兩個網(wǎng)絡(luò)之間的用戶進(jìn)行全局匹配。

評估指標(biāo)有種子擴展率Rate、準(zhǔn)確率Accuracy和召回率Recall。其中種子擴展率Rate（擴充的種子節(jié)點的個數(shù)除以所有種子節(jié)點的個數(shù)）作為第一階段種子擴充效果的評價指標(biāo)，準(zhǔn)確率和召回率作為第一階段和第二階段總體效果的評價指標(biāo)。

7.3 實驗和結(jié)果

本節(jié)設(shè)置多個實驗來驗證本文方法的有效性和正確性。

（1）閾值參數(shù)k的選擇

在基于種子進(jìn)行擴展的過程中，節(jié)點形成向量同時節(jié)點保存Info信息。然后選取含有豐富信息的節(jié)點作為候選匹配節(jié)點，即Info值大于閾值參數(shù)k的節(jié)點。下面通過實驗觀測選取不同閾值對結(jié)果的影響。實驗結(jié)果如圖7、圖8所示。

在S_DS和R_DS上分別選取占節(jié)點總數(shù)的0.1%、1%、5%和10%的種子節(jié)點。統(tǒng)計節(jié)點關(guān)于Info值的分布信息如圖7 所示，圖7（a）是在S_DS 上的結(jié)果，圖7（b）是在R_DS 上的結(jié)果。從圖7 可看出，節(jié)點的個數(shù)隨著Info值的增加而減少。Info值小的節(jié)點雖然多，但是可以被識別為種子節(jié)點的卻很少。圖8 所示為能夠被識別出來的候選匹配節(jié)點比例隨著不同的Info閾值k的變化曲線。圖8（a）是在S_DS 上的結(jié)果，圖8（b）是在R_DS 上的結(jié)果。

Fig.7 Effect of Info on the number of nodes圖7 Info 對節(jié)點個數(shù)的影響

Fig.8 Proportion of identifiable nodes at different thresholds圖8 不同閾值的節(jié)點的可識別比例

實驗表明節(jié)點Info的值越小，這個節(jié)點所帶有的信息越少，越不容易識別。綜上，在選取Info的閾值時，選取Info閾值為8，即只有Info值大于等于8 的節(jié)點，才能作為候選節(jié)點進(jìn)行跨網(wǎng)匹配，來豐富種子節(jié)點。

（2）不同算法的種子擴展率Rate對比

在S_DS和R_DS上分別選取占節(jié)點總數(shù)的0.1%、1%、5%和10%的種子節(jié)點。統(tǒng)計不同算法擴展種子節(jié)點的比例Rate 如表3 所示，從表3 中可以看出在種子節(jié)點稀疏的時候，GSE 模型明顯好于其他模型。

（3）不同匹配算法的準(zhǔn)確性和召回率的對比

在S_DS 和R_DS 上，選取0.1%、1%、5%、10%的種子節(jié)點進(jìn)行實驗，評估結(jié)果的準(zhǔn)確性如圖9 所示，圖9（a）是在S_DS 上的結(jié)果，圖9（b）是在R_DS 上的結(jié)果。評估結(jié)果的召回率如圖10 所示，圖10（a）是在S_DS 上的結(jié)果，圖10（b）是在R_DS 上的結(jié)果。

Table 3 Rate of seed expansion of different algorithms表3 不同算法的種子擴展比例Rate

實驗結(jié)果顯示，在種子節(jié)點稀疏的時候，GLE 效果明顯比MNA 和ALLEN-MLP 要好，主要是GLE 種子擴充發(fā)揮了作用。隨著種子節(jié)點的增多，GLE 的效果比MNA 和ALLEN-MLP 要好，是因為最優(yōu)局部擴展比MNA 的一層局部擴展和ALLEN-MLP 兩層局部擴展具有優(yōu)勢。而那些沒有被識別出來的節(jié)點主要是因為這些節(jié)點相對孤立，和其他節(jié)點之間的連接過少，無法進(jìn)行兩階段的擴展模型。

Fig.9 Accuracy of different algorithms圖9 不同算法的準(zhǔn)確率

Fig.10 Recall of different algorithms圖10 不同算法的召回率

（4）不同算法的運行時間對比

不同算法隨著種子個數(shù)增加的運行時間如圖11所示，圖11（a）是在S_DS 上的結(jié)果，圖11（b）是在R_DS 上的結(jié)果。

Fig.11 Running time of different algorithms圖11 不同算法的運行時間

從圖11 中可以看出在種子節(jié)點個數(shù)稀少的時候，GLE 的運行時間低于MNA 和ALLEN-MLP 的運行時間，說明第一階段的種子擴充起到了降低時間的作用。隨著種子節(jié)點的增多，GLE 的運行時間也沒有超過局部擴展方法MNA 和ALLEN-MLP。

GLE 的第二階段局部最優(yōu)擴展模型是基于MNA和ALLEN-MLP 的準(zhǔn)確性方面做出的改進(jìn)。除此之外，GLE 有較低的時間復(fù)雜性，窮舉方法的一次擴展的時間復(fù)雜性是N×N，明顯高于GLE，ALLEN-MLP方法的單次擴展的時間復(fù)雜性是n×n（n為節(jié)點的平均度數(shù)），GLE 算法的單次擴展的時間復(fù)雜度為n×n+4n。

8 結(jié)束語

本文提出了結(jié)合全局種子最優(yōu)局部擴展的跨網(wǎng)絡(luò)用戶匹配模型，通過全局種子擴充來增加種子數(shù)量，解決冷啟動問題；根據(jù)最優(yōu)局部擴展模型，有效地處理大量的潛在的候選匹配節(jié)點。同已有方法比較，本模型具有較高的準(zhǔn)確性和召回率，且具有較低的時間開銷。下一步，將結(jié)合全局種子最優(yōu)局部擴展的跨網(wǎng)絡(luò)用戶匹配模型應(yīng)用到多個社交網(wǎng)絡(luò)，使其應(yīng)用更加廣泛。