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

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

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

1 引言

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

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

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

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

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

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

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

分析已有方法，具有如下幾點(diǎn)不足：

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

3 問題定義

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

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

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

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

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

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

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

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

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

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

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

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

5 全局種子擴(kuò)充模型

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

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

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

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

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

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

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

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

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

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

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

5.2 全局種子擴(kuò)充模型

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

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

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

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

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

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

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

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

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

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

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

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

下面給出全局種子節(jié)點(diǎn)擴(kuò)充算法。

算法2全局種子擴(kuò)充算法

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

輸出：種子集合A。

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

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

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

6.1 基于種子節(jié)點(diǎn)擴(kuò)展的搜索范圍

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

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

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

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

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

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

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

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

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

節(jié)點(diǎn)匹配過程：

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

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

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

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

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

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

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

7 實(shí)驗(yàn)與結(jié)果

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

7.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

真實(shí)數(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í)數(shù)據(jù)集

7.2 對(duì)比實(shí)驗(yàn)與評(píng)估

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

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

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

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

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

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

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

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

7.3 實(shí)驗(yàn)和結(jié)果

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

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

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

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

Fig.7 Effect of Info on the number of nodes圖7 Info 對(duì)節(jié)點(diǎn)個(gè)數(shù)的影響

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

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

（2）不同算法的種子擴(kuò)展率Rate對(duì)比

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

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

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

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

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

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

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

（4）不同算法的運(yùn)行時(shí)間對(duì)比

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

Fig.11 Running time of different algorithms圖11 不同算法的運(yùn)行時(shí)間

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

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

8 結(jié)束語

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