基于旅客-航班異構(gòu)網(wǎng)絡(luò)的旅客同行子圖抽取

盧 敏 王彥威

1(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300300) 2(民航旅客服務(wù)智能化應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室 天津 300300) 3(中國(guó)民航大學(xué)信息技術(shù)科研基地 天津 300300)

0 引 言

民航旅客同行子圖抽取旨在從旅客-航班異構(gòu)網(wǎng)絡(luò)中抽取具有潛在同行關(guān)系的旅客子圖，其本質(zhì)是根據(jù)部分旅客出行具有相似性的特點(diǎn)對(duì)旅客進(jìn)行劃分，使得子圖內(nèi)部連接緊湊，子圖外部連接稀疏。旅客-航班異構(gòu)網(wǎng)絡(luò)是由描述旅客選擇航班關(guān)系的旅客-航班二部圖，以及描述航班相似性的航班同構(gòu)網(wǎng)絡(luò)構(gòu)成。民航旅客同行子圖具有廣泛的應(yīng)用，例如：發(fā)現(xiàn)潛在同行旅客，為具有潛在同行的旅客預(yù)留座位；發(fā)現(xiàn)旅客潛在出行意圖，為具有相同出行意圖的旅客進(jìn)行航班推薦；通過(guò)對(duì)危險(xiǎn)旅客及其同行旅客的監(jiān)控，為民航業(yè)提供安全保障等。

民航旅客同行子圖抽取目標(biāo)是抽取關(guān)系最緊密的旅客節(jié)點(diǎn)。由于旅客出行的高代價(jià)和低頻性，使得旅客出行記錄稀疏，現(xiàn)有子圖抽取[1-3]方法難以應(yīng)用在稀疏圖；并且僅從單一維度進(jìn)行旅客同行子圖抽取不能準(zhǔn)確地發(fā)現(xiàn)旅客間的潛在同行可能。

針對(duì)上述問(wèn)題，本文設(shè)計(jì)了基于“旅客-航班”異構(gòu)網(wǎng)絡(luò)的子圖抽取算法，旨在通過(guò)旅客乘坐的歷史航班記錄和航班與航班的相似關(guān)系找到潛在的旅客同行信息。在此基礎(chǔ)之上，對(duì)生成的旅客同行信息進(jìn)行分析，發(fā)現(xiàn)旅客可能存在多個(gè)潛在同行信息。因此，在進(jìn)行子圖抽取過(guò)程中，應(yīng)保證旅客可以屬于多個(gè)子圖。因此，本文提出標(biāo)簽傳播的方法進(jìn)行子圖抽取并使用后處理閾值來(lái)記錄每個(gè)旅客所在的子圖。在旅客訂票記錄真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明：相比于基準(zhǔn)算法，本文算法在子圖模塊度和精準(zhǔn)度指標(biāo)上具有良好效果。

本文主要貢獻(xiàn)如下：(1) 針對(duì)旅客同行記錄高度稀疏，提出了基于旅客-航班異構(gòu)網(wǎng)絡(luò)的旅客同行子圖抽取方法，能夠?qū)⑾∈璧穆每统鲂杏涗涋D(zhuǎn)換成稠密的旅客潛在同行記錄；(2) 提出了通過(guò)隨機(jī)游走進(jìn)行旅客間相似度計(jì)算方法；(3) 將本文算法應(yīng)用在國(guó)內(nèi)某旅客訂票記錄中，相比于LPA、COPRA、CPM等基準(zhǔn)算法，本文在子圖抽取模塊度和準(zhǔn)確率上具有更好效果。

1 相關(guān)工作

1.1 旅客同行研究現(xiàn)狀

旅客同行研究旨在通過(guò)對(duì)旅客的出行記錄發(fā)現(xiàn)具有潛在同行關(guān)系的旅客。葉紹貴等[4]通過(guò)對(duì)旅客同行網(wǎng)絡(luò)進(jìn)行層次劃分，然后根據(jù)共同鄰居的信息來(lái)構(gòu)造出節(jié)點(diǎn)的一系列層次屬性，使得網(wǎng)絡(luò)的特征更加豐富，并使用分類(lèi)算法發(fā)現(xiàn)潛在同行鏈接。張奧爽等[5]根據(jù)航空公司旅客信息系統(tǒng)中旅客歷史出行記錄提取旅客之間的社會(huì)關(guān)系并構(gòu)建旅客同行網(wǎng)絡(luò)，對(duì)潛在同行旅客進(jìn)行分類(lèi)。

上述方法研究在旅客同行同質(zhì)網(wǎng)絡(luò)上的旅客關(guān)系鏈接預(yù)測(cè)，但并未考慮旅客與航班以及航班與航班的關(guān)系。在現(xiàn)實(shí)生活中，這種關(guān)系表現(xiàn)為乘坐相似航班的旅客有可能同行。

1.2 子圖抽取研究現(xiàn)狀

子圖抽取算法[6]最早在2004年被提出，旨在發(fā)現(xiàn)關(guān)系緊密的節(jié)點(diǎn)。近年來(lái)，為了發(fā)現(xiàn)子圖中的內(nèi)部規(guī)律，例如萬(wàn)維網(wǎng)中的子圖是討論相關(guān)主題的若干網(wǎng)站；電子電路網(wǎng)絡(luò)中的子圖可能是具有某一類(lèi)特定功能的單元等,一些學(xué)者展開(kāi)了深入研究，形成了大量的研究成果，其中代表性的方法可以分為基于模塊性?xún)?yōu)化的子圖抽取方法[7]；基于標(biāo)簽傳播的子圖抽取方法[8-9]；基于劃分的子圖抽取方法[10]等。例如Clauset等[11]提出局部模塊度的概念，并使用邊界節(jié)點(diǎn)和子圖內(nèi)節(jié)點(diǎn)連接的邊數(shù)與該節(jié)點(diǎn)的度的比值來(lái)進(jìn)行子圖抽取，其提出從起始節(jié)點(diǎn)出發(fā)，通過(guò)廣度優(yōu)先遍歷節(jié)點(diǎn)，找到使得模塊度增大的節(jié)點(diǎn)并放入子圖中，直到遍歷完所有節(jié)點(diǎn)。LPA算法[12]是一種基于標(biāo)簽傳播的算法，該方法將每個(gè)節(jié)點(diǎn)標(biāo)簽化，節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽作為自己的標(biāo)簽。

上述方法僅考慮節(jié)點(diǎn)屬于唯一子圖，而在現(xiàn)實(shí)生活中，一個(gè)節(jié)點(diǎn)可能隸屬于多個(gè)子圖，例如在旅客同行網(wǎng)絡(luò)中，處于子圖邊緣的乘客有可能與多個(gè)乘客存在同行關(guān)系；在學(xué)術(shù)合作網(wǎng)絡(luò)中，一個(gè)學(xué)者可能同時(shí)參與多個(gè)學(xué)術(shù)團(tuán)體；在蛋白質(zhì)互相作用網(wǎng)絡(luò)中，根據(jù)蛋白質(zhì)功能的不同，應(yīng)劃分為多個(gè)子圖。針對(duì)上述問(wèn)題，子圖抽取引入隸屬度的概念，用來(lái)發(fā)現(xiàn)可能重疊的子圖。例如BMLPA算法[13]在初始化階段設(shè)置平衡歸屬因子用來(lái)約束節(jié)點(diǎn)標(biāo)簽的更新，以便形成不重疊的子圖。陳杰等[14]提出一種從圖中抽取有意義的密集子圖方法，該方法利用矩陣分塊的思想，抽取節(jié)點(diǎn)度大于閾值的節(jié)點(diǎn)。上述子圖抽取算法需要保證圖中節(jié)點(diǎn)類(lèi)型一致，由于其抽取不同類(lèi)型的子圖并無(wú)實(shí)際意義，因此不適用于旅客-航班異構(gòu)網(wǎng)絡(luò)子圖抽取中。

2 算法設(shè)計(jì)

本文首先對(duì)旅客-航班異構(gòu)網(wǎng)絡(luò)進(jìn)行隨機(jī)游走以便發(fā)現(xiàn)旅客潛在同行信息。旅客-航班異構(gòu)網(wǎng)絡(luò)是由描述旅客選擇航班關(guān)系的旅客-航班二部圖，以及描述航班相似性的航班同構(gòu)網(wǎng)絡(luò)構(gòu)成。在此基礎(chǔ)之上，使用標(biāo)簽傳播的方法根據(jù)旅客潛在同行信息進(jìn)行旅客同行子圖抽取，首先得到圖中較大度的完全子圖，并為每個(gè)節(jié)點(diǎn)打上一個(gè)唯一的標(biāo)簽，然后根據(jù)標(biāo)簽傳播規(guī)則對(duì)節(jié)點(diǎn)標(biāo)簽進(jìn)行更新，最后處理可能具有多個(gè)標(biāo)簽的節(jié)點(diǎn)。

2.1 基于“旅客-航班”異構(gòu)網(wǎng)絡(luò)的旅客同行網(wǎng)絡(luò)構(gòu)建

“旅客-航班”異構(gòu)網(wǎng)絡(luò)是指在旅客訂票記錄(PNR)中構(gòu)建旅客-航班矩陣，此矩陣分為4個(gè)模塊，如式(1)所示：

(1)

式中：Wxx表示“旅客-旅客”模塊；Wxy表示“旅客-航班”模塊；Wyx表示“航班-旅客”模塊；Wyy表示“航班-航班”模塊?！奥每?航班”模塊定義將旅客乘坐過(guò)相同的航班號(hào)填入到“旅客-航班”矩陣的對(duì)應(yīng)位置，“旅客-航班”模塊與“航班-旅客”模塊一致。與此同時(shí)，本文構(gòu)建“航班-航班”矩陣，該矩陣描述航班與航班間的相似性。航班的相似度根據(jù)航班起始地和目的地的經(jīng)緯度，使用余弦相似度計(jì)算。其計(jì)算方法如下：

(2)

式中：F1以向量的形式表示航班1的經(jīng)緯度；F2以向量的形式表示航班2的經(jīng)緯度；構(gòu)建旅客同行網(wǎng)絡(luò)的目的是為了得到旅客潛在同行關(guān)系。

2.2 隨機(jī)游走重構(gòu)網(wǎng)絡(luò)

對(duì)“旅客-航班”模塊，“航班-旅客”模塊和“旅客-航班”模塊初始化后，通過(guò)隨機(jī)游走的方式對(duì)上述模塊進(jìn)行更新。在本節(jié)中，根據(jù)上節(jié)構(gòu)建的“航班-旅客”和“旅客-航班”關(guān)系網(wǎng)絡(luò)，進(jìn)行旅客和旅客的相似度計(jì)算。

旅客間的相似度物理含義是有可能同行的旅客，本文對(duì)“旅客-旅客”矩陣進(jìn)行處理，將其初始化為對(duì)角矩陣。“旅客-旅客”矩陣的相似度通過(guò)“旅客-航班”矩陣，“航班-旅客”矩陣和“航班-航班”矩陣來(lái)表示，其計(jì)算方法如下：

(3)

式中：Wij表示旅客i和旅客j之間的相似度；aik表示“旅客-航班”矩陣中旅客i與航班k歸一化后的權(quán)值；bkl表示“航班-航班”矩陣中航班k與航班l(xiāng)歸一化后的權(quán)值；clj表示“航班-旅客”中航班l(xiāng)與旅客j歸一化后的權(quán)值?！奥每?旅客”矩陣中的值表示的含義是旅客間潛在的同行概率，本文通過(guò)隨機(jī)游走來(lái)更新旅客間的潛在同行概率。

隨機(jī)游走可以理解為節(jié)點(diǎn)通過(guò)對(duì)鄰居節(jié)點(diǎn)的訪問(wèn)，以達(dá)到對(duì)網(wǎng)絡(luò)進(jìn)行隨機(jī)遍歷的行為。節(jié)點(diǎn)訪問(wèn)其鄰居節(jié)點(diǎn)的概率被稱(chēng)作轉(zhuǎn)移概率，節(jié)點(diǎn)轉(zhuǎn)移概率pij計(jì)算方法如下：

(4)

式中：Z表示節(jié)點(diǎn)歸一化因子；Wij表示旅客節(jié)點(diǎn)i選擇旅客節(jié)點(diǎn)j的概率。得到節(jié)點(diǎn)轉(zhuǎn)移概率后，“旅客-旅客”模塊更新方式如下：

(5)

式中：θ為隨機(jī)游走次數(shù)。

2.3 標(biāo)簽傳播算法

標(biāo)簽傳播算法首先為圖中任意旅客節(jié)點(diǎn)初始化標(biāo)簽；然后在標(biāo)簽傳播的過(guò)程中，每個(gè)節(jié)點(diǎn)在接收其鄰居節(jié)點(diǎn)標(biāo)簽的同時(shí)，也向鄰居節(jié)點(diǎn)發(fā)出標(biāo)簽；在每個(gè)節(jié)點(diǎn)的存儲(chǔ)空間中，可以保存之前迭代所接到的標(biāo)簽，為避免出現(xiàn)每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)子圖標(biāo)簽過(guò)多的情況，標(biāo)簽傳播算法使用相同標(biāo)簽所占比例大于給定參數(shù)的方式來(lái)確定哪些標(biāo)簽將保存下來(lái)，最終完成子圖抽取。

2.3.1標(biāo)簽傳播算法初始化

由上述“旅客-航班”“航班-旅客”和“航班-航班”矩陣得到“旅客-旅客”矩陣后，本節(jié)對(duì)“旅客-旅客”矩陣進(jìn)行子圖抽取。由于在初始階段，每個(gè)節(jié)點(diǎn)隨機(jī)接收鄰居節(jié)點(diǎn)的標(biāo)簽，造成節(jié)點(diǎn)標(biāo)簽收斂慢。因此，在初始化階段，本文首先發(fā)現(xiàn)圖中完全子圖，然后使得完全子圖持有相同的標(biāo)簽，提高算法收斂速度的同時(shí)減少算法的隨機(jī)性。

定義1完全子圖。若圖G1是圖G的子圖且G1中每個(gè)節(jié)點(diǎn)對(duì)之間都有一條邊相連，則G1是G的完全子圖。

以完全子圖進(jìn)行標(biāo)簽傳播，往往能取得較好的效果[15]。其原因是完全子圖內(nèi)部連接緊密，因此其標(biāo)簽一致，在標(biāo)簽傳播過(guò)程中可以看作一個(gè)節(jié)點(diǎn)，進(jìn)而加快標(biāo)簽傳播過(guò)程。其算法描述如算法1所示。

算法1以較高節(jié)點(diǎn)度為中心的完全子圖

輸入：“旅客-旅客”矩陣N。

輸出：完全子圖集合G。

BEGIN

(1) 初始化節(jié)點(diǎn)標(biāo)簽：為“旅客-旅客”矩陣N中的每個(gè)節(jié)點(diǎn)按照從1到n的順序編號(hào)；

(2) 從編號(hào)1的節(jié)點(diǎn)開(kāi)始搜索；

(3) If節(jié)點(diǎn)i未被搜索；

(4)i標(biāo)記為已被搜索；

(5) 搜索節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中度大于等于i的節(jié)點(diǎn)集合，從中選擇度最大的節(jié)點(diǎn)p，若度最大節(jié)點(diǎn)不唯一時(shí)，則隨機(jī)選取一個(gè)節(jié)點(diǎn)，并將其標(biāo)記為已被搜索；

(6)Gp=Gp∪p；

//Gp是以p為中心的完全子圖集合；

(7) 搜索節(jié)點(diǎn)p的鄰居節(jié)點(diǎn)，從中選擇度最大的節(jié)點(diǎn)，若度最大節(jié)點(diǎn)不唯一，則隨機(jī)選擇一個(gè)節(jié)點(diǎn)q；

(8) 如果q的鄰居節(jié)點(diǎn)k與Gp中的節(jié)點(diǎn)均有邊時(shí)，將其加入到Gp，并將節(jié)點(diǎn)標(biāo)記為已被搜索；

(9) 更新Gp節(jié)點(diǎn)中的標(biāo)簽為相同標(biāo)簽。

算法首先為每個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)簽化，接著在未搜索的區(qū)域找到節(jié)點(diǎn)度較大的節(jié)點(diǎn)，并將其作為完全子圖的中心節(jié)點(diǎn)。完全子圖的搜索過(guò)程是指選擇與中心節(jié)點(diǎn)相連的度最大的節(jié)點(diǎn)，將其加入完全子圖集合；接著選擇與完全子圖集合中所有元素都相連的最大度的節(jié)點(diǎn)將其加入完全子圖集合，并將同一個(gè)完全子圖集合中的元素統(tǒng)一貼上相同標(biāo)簽。反復(fù)執(zhí)行以上操作，圖中會(huì)得到多個(gè)完全子圖。完全子圖的元素作為標(biāo)簽傳播的初始點(diǎn)。

2.3.2標(biāo)簽傳播過(guò)程

初始化階段，每個(gè)節(jié)點(diǎn)的標(biāo)簽已被標(biāo)記，首先對(duì)完全子圖中的元素進(jìn)行傳播，然后對(duì)完全子圖外的節(jié)點(diǎn)按照節(jié)點(diǎn)編號(hào)更新。該傳播策略減輕網(wǎng)絡(luò)中較重要節(jié)點(diǎn)在更新標(biāo)簽的過(guò)程中受到圖中邊緣節(jié)點(diǎn)標(biāo)簽的影響。

在選定當(dāng)前需要更新標(biāo)簽的節(jié)點(diǎn)后，與其直接相連的節(jié)點(diǎn)標(biāo)簽作為當(dāng)前節(jié)點(diǎn)更改標(biāo)簽的因素。其更改標(biāo)簽需要遵循如下原則：節(jié)點(diǎn)按鄰居節(jié)點(diǎn)出現(xiàn)頻次最高的標(biāo)簽進(jìn)行修改，若存在多個(gè)相同頻次的標(biāo)簽，則根據(jù)“旅客-旅客”矩陣中旅客的相似度，選擇相似度高的節(jié)點(diǎn)的標(biāo)簽，將其修改為自身標(biāo)簽。節(jié)點(diǎn)標(biāo)簽傳播規(guī)則使用同步更新方法，其表示如下：

Ci(m)=f(Ci1(m-1),Ci2(m-1),…,Cit(m-1))

(6)

式中：Ci(m)表示節(jié)點(diǎn)i的第m次的標(biāo)簽；Ci1(m-1)和Cit(m-1)表示節(jié)點(diǎn)i第1個(gè)至t個(gè)鄰居節(jié)點(diǎn)在m-1次出現(xiàn)的標(biāo)簽。相比于異步更新，同步更新在更新節(jié)點(diǎn)標(biāo)簽時(shí)，僅依賴(lài)前一次更新的標(biāo)簽集，減少了因?yàn)楣?jié)點(diǎn)更新順序不同而產(chǎn)生的隨機(jī)性。因此本文使用同步更新策略來(lái)更新節(jié)點(diǎn)的標(biāo)簽傳播。

2.3.3重疊子圖發(fā)現(xiàn)

標(biāo)簽傳播算法記錄了每個(gè)節(jié)點(diǎn)的每個(gè)標(biāo)簽，在迭代結(jié)束后，計(jì)算每個(gè)節(jié)點(diǎn)互異標(biāo)簽出現(xiàn)的概率，以便發(fā)現(xiàn)可能屬于多個(gè)子圖的節(jié)點(diǎn)。每個(gè)不同標(biāo)簽的概率表示如下：

(7)

式中：T為迭代的次數(shù)；count(labeli)表示在迭代過(guò)程中；labeli出現(xiàn)的次數(shù)。若節(jié)點(diǎn)中出現(xiàn)兩個(gè)最高的相同概率的標(biāo)簽，則保留這兩個(gè)標(biāo)簽，節(jié)點(diǎn)擁有多個(gè)標(biāo)簽表明節(jié)點(diǎn)可能屬于多個(gè)子圖。在節(jié)點(diǎn)標(biāo)簽達(dá)到迭代次數(shù)或趨于穩(wěn)定后，對(duì)每個(gè)節(jié)點(diǎn)的標(biāo)簽矩陣進(jìn)行分析，其目的是保留大于閾值的標(biāo)簽，并將其作為節(jié)點(diǎn)的最終標(biāo)簽，刪除剩余標(biāo)簽。標(biāo)簽傳播算法如算法2所示。

算法2以標(biāo)簽傳播方法進(jìn)行子圖抽取

輸入：初始化后的旅客同行網(wǎng)絡(luò)M，迭代次數(shù)T,后處理閾值r。

輸出：節(jié)點(diǎn)標(biāo)簽列表listi。

BEGIN

(1) 采用同步更新方式，根據(jù)鄰居節(jié)點(diǎn)標(biāo)簽信息對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行更新；

(2) 如果目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)出現(xiàn)最多的標(biāo)簽唯一，修改目標(biāo)節(jié)點(diǎn)的標(biāo)簽；否則根據(jù)旅客同行網(wǎng)絡(luò)中旅客-旅客的權(quán)值，選擇權(quán)值最高的旅客節(jié)點(diǎn)的標(biāo)簽作為目標(biāo)節(jié)點(diǎn)的標(biāo)簽；

(3) 重復(fù)上述步驟(1)-步驟(2),直到達(dá)到迭代次數(shù)T或標(biāo)簽趨于穩(wěn)定；

(4) 記錄每次目標(biāo)節(jié)點(diǎn)的標(biāo)簽，在迭代結(jié)束后，計(jì)算互異標(biāo)簽出現(xiàn)的概率；

(5) 根據(jù)節(jié)點(diǎn)互異標(biāo)簽的概率和后處理閾值r，選擇最終作為目標(biāo)節(jié)點(diǎn)的標(biāo)簽，并刪除其余標(biāo)簽。

3 算法復(fù)雜性分析

假設(shè)旅客節(jié)點(diǎn)數(shù)為m，航班節(jié)點(diǎn)數(shù)為n，隨機(jī)游走的迭代次數(shù)為l，旅客節(jié)點(diǎn)的平均度為k，完全子圖的數(shù)量為f，標(biāo)簽傳播過(guò)程迭代次數(shù)為t，在迭代完成后具有多個(gè)標(biāo)簽的節(jié)點(diǎn)數(shù)量為n。本節(jié)主要從時(shí)間復(fù)雜度方面對(duì)子圖抽取方法進(jìn)行分析。

隨機(jī)游走階段，計(jì)算航班相似度的時(shí)間復(fù)雜度為O(n2)，計(jì)算“旅客-航班”轉(zhuǎn)移概率矩陣的時(shí)間復(fù)雜度為O(ml)，生成“旅客-旅客”矩陣的時(shí)間復(fù)雜度為O(m2·n)。因此，隨機(jī)游走階段所需要的時(shí)間復(fù)雜度為O(n2+2ml+m2·n)。

標(biāo)簽傳播方法分為初始化階段和標(biāo)簽傳播階段。在初始化階段中，需要給每個(gè)節(jié)點(diǎn)編碼，其時(shí)間復(fù)雜度為O(m)，在算法1中，搜索完全子圖的時(shí)間復(fù)雜度不超過(guò)O(mkf)。在標(biāo)簽傳播階段，更新標(biāo)簽所需要的時(shí)間復(fù)雜度為O(mkt)，發(fā)現(xiàn)重疊子圖所需要的時(shí)間復(fù)雜度為O(tm)，因此標(biāo)簽傳播方法的時(shí)間復(fù)雜度為O(m+mkf+mkt+tm)。

4 實(shí) 驗(yàn)

將上述算法應(yīng)用到國(guó)內(nèi)某航空公司旅客訂票記錄(PNR)真實(shí)數(shù)據(jù)集中，并檢驗(yàn)其準(zhǔn)確度、模塊度和算法收斂速度。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集來(lái)自201X—201Y年國(guó)內(nèi)某大型航空公司旅客訂票記錄。實(shí)驗(yàn)數(shù)據(jù)集是由中國(guó)民航信息網(wǎng)絡(luò)股份有限公司訂座系統(tǒng)提供，每一條記錄為旅客真實(shí)訂票記錄，具體字段包括旅客身份證號(hào)、出生年月、旅客乘坐航班記錄、旅客乘坐航班的起飛機(jī)場(chǎng)和降落機(jī)場(chǎng)(使用機(jī)場(chǎng)三字碼表示)及旅客訂單號(hào)等。機(jī)場(chǎng)的經(jīng)緯度來(lái)源于谷歌地圖上機(jī)場(chǎng)真實(shí)位置的經(jīng)緯度。本文已對(duì)旅客信息進(jìn)行加密處理。實(shí)驗(yàn)數(shù)據(jù)集反映了旅客真實(shí)訂票習(xí)慣與旅客潛在同行關(guān)系，為此可開(kāi)展旅客同行子圖抽取的實(shí)驗(yàn)。旅客訂票記錄使用見(jiàn)表1，航班信息示例見(jiàn)表2。

表1 旅客訂票記錄示例

表2 航班信息示例

4.1.1數(shù)據(jù)預(yù)處理

本實(shí)驗(yàn)原始數(shù)據(jù)集為201X—201Y年旅客真實(shí)訂票記錄，大小為48.6 GB。對(duì)原始數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)其中部分旅客在201X年和201Y年中并無(wú)同行記錄且出行次數(shù)較少，這類(lèi)數(shù)據(jù)不在本文考慮范圍內(nèi)。因此本文首先對(duì)原始數(shù)據(jù)進(jìn)行處理，抽取在201X—201Y年都活躍的旅客，即抽取兩年內(nèi)都有乘機(jī)記錄，且乘機(jī)次數(shù)大于等于5次的旅客，旅客數(shù)據(jù)共有113 MB。旅客訂票記錄共有204 825條。本文根據(jù)201X年的旅客訂票記錄，生成旅客潛在同行網(wǎng)絡(luò)。為了驗(yàn)證子圖抽取的準(zhǔn)確性，將由本文生成的旅客同行子圖與測(cè)試集上的旅客同行子圖進(jìn)行對(duì)比。在對(duì)比之前，需額外增加一維標(biāo)簽信息。本文通過(guò)抽取201Y年相同的訂單號(hào)的旅客，以及訂單號(hào)不同但同時(shí)乘坐相同航班3次以上的旅客，將他們標(biāo)注相同標(biāo)簽。標(biāo)注后的旅客訂票信息如表3所示。

表3 帶標(biāo)簽的201Y年旅客訂票記錄

4.1.2基準(zhǔn)算法

通過(guò)參考大量國(guó)內(nèi)外文獻(xiàn)，未曾有人在旅客訂票記錄數(shù)據(jù)集中進(jìn)行子圖抽取算法比較。因此，本文基準(zhǔn)算法選取在公共數(shù)據(jù)集中表現(xiàn)較好的子圖抽取算法，并將本文算法與之比較。

為了驗(yàn)證算法的有效性，將其與SLPA[16]算法、COPRA[17]算法及CPM[18]算法進(jìn)行比較。

4.1.3評(píng)價(jià)指標(biāo)

性能指標(biāo)為用來(lái)衡量重疊子圖質(zhì)量的模塊度及衡量子圖抽取準(zhǔn)確度的標(biāo)準(zhǔn)化互信息。模塊度EQ計(jì)算公式如下：

(8)

式中：C表示子圖；ni和nj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j所屬的子圖數(shù)；Aij的取值為0或1，0表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒(méi)有邊相連，1表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有邊相連；di和dj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度；σic和σjc取值為0或1，0表示節(jié)點(diǎn)i或節(jié)點(diǎn)j不屬于子圖c，1表示節(jié)點(diǎn)i或節(jié)點(diǎn)j屬于子圖。

標(biāo)準(zhǔn)化互信息NMI計(jì)算公式如下：

(9)

式中：CA表示真實(shí)的子圖數(shù)目；CB表示本算法劃分后的子圖數(shù)目；N表示矩陣，矩陣的行表示矩陣所屬的真實(shí)子圖，矩陣的列表示該節(jié)點(diǎn)由本文算法得到的子圖；nij表示真實(shí)子圖i與本文得到子圖j的重合節(jié)點(diǎn)個(gè)數(shù)；ni·表示第i行元素之和；n·j表示第j列元素之和。NMI的取值在0到1之間，其值越大，證明算法識(shí)別子圖結(jié)構(gòu)準(zhǔn)確度越高。

4.1.4算法參數(shù)設(shè)置

算法中存在三個(gè)參數(shù)需要預(yù)先進(jìn)行人工設(shè)置，分別為隨機(jī)游走次數(shù)θ、迭代次數(shù)T和后處理閾值r。通過(guò)對(duì)旅客潛在同行關(guān)系進(jìn)行分析，發(fā)現(xiàn)其中旅客節(jié)點(diǎn)數(shù)為460 998，在得到的連通子圖中，旅客節(jié)點(diǎn)的平均路徑長(zhǎng)度為2.96，節(jié)點(diǎn)的平均聚集系數(shù)為0.679 6，因此，本文所提出的旅客潛在同行網(wǎng)絡(luò)具有高聚集系數(shù)和低節(jié)點(diǎn)平均度的特性，該網(wǎng)絡(luò)符合小世界網(wǎng)絡(luò)的特征。根據(jù)小世界理論，將隨機(jī)游走次數(shù)θ設(shè)置為1～6；迭代次數(shù)T設(shè)置為20；后處理閾值r設(shè)置為0.1～0.3。

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

算法運(yùn)行的硬件環(huán)境是Intel(R) Core(TM) i7-6800K，3.4 GHz主頻，內(nèi)存為64 GB的計(jì)算機(jī)。由于本文標(biāo)簽傳播算法在標(biāo)簽傳播過(guò)程具有一定的隨機(jī)性，為此采用一次運(yùn)行結(jié)果進(jìn)行性能比較具有較強(qiáng)的不確定性。為了減少隨機(jī)影響，算法在相同參數(shù)下運(yùn)行多次，取多次性能的平均值。與基準(zhǔn)算法對(duì)比的實(shí)驗(yàn)結(jié)果如表4所示。本文在模塊度和標(biāo)準(zhǔn)化互信息方面均有提升。

表4 子圖抽取性能比較

4.3 實(shí)驗(yàn)分析

由表4可以看出，本文算法在模塊度和標(biāo)準(zhǔn)化互信息兩個(gè)指標(biāo)上具有良好效果。隨機(jī)游走次數(shù)θ控制旅客節(jié)點(diǎn)之間的相似度，在θ值增大的情況下，會(huì)導(dǎo)致節(jié)點(diǎn)間的相似度增大，旅客節(jié)點(diǎn)之間具有潛在關(guān)聯(lián)的邊也會(huì)增多，因此實(shí)驗(yàn)需要探究隨機(jī)游走次數(shù)θ的值如何反應(yīng)節(jié)點(diǎn)間的相似度。在隨機(jī)游走次數(shù)θ=1時(shí)，由于旅客節(jié)點(diǎn)間的聯(lián)系較為稀疏，因此NMI的值較低，隨著隨機(jī)游走次數(shù)的增多，旅客節(jié)點(diǎn)間潛在的關(guān)系也被挖掘出來(lái)，在θ增大時(shí)，子圖抽取算法的NMI增加。而在θ≥4時(shí)，出現(xiàn)了過(guò)擬合現(xiàn)象，導(dǎo)致子圖抽取算法準(zhǔn)確度下降。如圖1所示，其中橫坐標(biāo)為隨機(jī)游走迭代次數(shù)，縱坐標(biāo)為子圖抽取的標(biāo)準(zhǔn)化互信息(NMI)。

圖1 不同θ下的NMI對(duì)比

相比于CPM算法，本文算法通過(guò)發(fā)現(xiàn)高節(jié)點(diǎn)度的完全子圖進(jìn)行傳播，保障算法找到合適的起點(diǎn)，進(jìn)而加快節(jié)點(diǎn)收斂速度。相比于SLPA和COPRA算法，本文在模塊度和標(biāo)準(zhǔn)化互信息方面均有提高。SLPA和COPRA算法在識(shí)別子圖過(guò)程中隨機(jī)性較強(qiáng)，具有很強(qiáng)的振蕩現(xiàn)象。而本文算法在標(biāo)簽傳播過(guò)程中，考慮到節(jié)點(diǎn)的相似性，在選擇標(biāo)簽的時(shí)候會(huì)優(yōu)先選擇相似度大的節(jié)點(diǎn)的標(biāo)簽，進(jìn)而減少因隨機(jī)選取而產(chǎn)生的不確定性，并且因?yàn)楸疚脑跇?biāo)簽傳播初始化階段通過(guò)完全子圖進(jìn)行傳播，將具有緊密關(guān)系的節(jié)點(diǎn)在開(kāi)始階段標(biāo)記相同標(biāo)簽，相比于SLPA和COPRA算法，減少因隨機(jī)標(biāo)注標(biāo)簽而導(dǎo)致的精確度下降問(wèn)題。算法迭代過(guò)程如圖2所示，可以看到，在剛開(kāi)始迭代時(shí)隨機(jī)性較大，隨著迭代次數(shù)的增多，迭代到16次時(shí)算法收斂性趨于平穩(wěn)。產(chǎn)生該現(xiàn)象的原因是在開(kāi)始階段節(jié)點(diǎn)選擇標(biāo)簽隨機(jī)性較大，導(dǎo)致在初始階段節(jié)點(diǎn)被分為多個(gè)子圖。在每次迭代過(guò)程中，節(jié)點(diǎn)的標(biāo)簽都會(huì)被儲(chǔ)存下來(lái)。多次迭代后節(jié)點(diǎn)的標(biāo)簽也趨于固定。

圖2 子圖抽取算法收斂性分析

5 結(jié) 語(yǔ)

針對(duì)旅客同行網(wǎng)絡(luò)稀疏問(wèn)題，本文提出了基于“旅客-航班”異構(gòu)網(wǎng)絡(luò)的旅客同行子圖抽取算法。算法首先構(gòu)建旅客-航班異構(gòu)網(wǎng)絡(luò)矩陣，其次對(duì)其進(jìn)行隨機(jī)游走以計(jì)算旅客潛在同行概率。在此基礎(chǔ)之上，設(shè)計(jì)了一種基于標(biāo)簽傳播的子圖抽取算法，節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)標(biāo)簽以更改自身標(biāo)簽，并且可發(fā)現(xiàn)屬于多個(gè)子圖的節(jié)點(diǎn)。為了加快迭代速度，進(jìn)一步設(shè)計(jì)了基于完全子圖的節(jié)點(diǎn)標(biāo)簽初始化方法。算法理論分析進(jìn)一步表明算法求解過(guò)程是線性的。并在國(guó)內(nèi)某旅客訂票數(shù)據(jù)集上驗(yàn)證了算法性能的優(yōu)越性。后期可圍繞異構(gòu)網(wǎng)絡(luò)和動(dòng)態(tài)子圖的抽取進(jìn)行研究。