基于旅客-航班異構網絡的旅客同行子圖抽取

盧 敏 王彥威

1(中國民航大學計算機科學與技術學院 天津 300300) 2(民航旅客服務智能化應用技術重點實驗室 天津 300300) 3(中國民航大學信息技術科研基地 天津 300300)

0 引 言

民航旅客同行子圖抽取旨在從旅客-航班異構網絡中抽取具有潛在同行關系的旅客子圖，其本質是根據部分旅客出行具有相似性的特點對旅客進行劃分，使得子圖內部連接緊湊，子圖外部連接稀疏。旅客-航班異構網絡是由描述旅客選擇航班關系的旅客-航班二部圖，以及描述航班相似性的航班同構網絡構成。民航旅客同行子圖具有廣泛的應用，例如：發現潛在同行旅客，為具有潛在同行的旅客預留座位；發現旅客潛在出行意圖，為具有相同出行意圖的旅客進行航班推薦；通過對危險旅客及其同行旅客的監控，為民航業提供安全保障等。

民航旅客同行子圖抽取目標是抽取關系最緊密的旅客節點。由于旅客出行的高代價和低頻性，使得旅客出行記錄稀疏，現有子圖抽取[1-3]方法難以應用在稀疏圖；并且僅從單一維度進行旅客同行子圖抽取不能準確地發現旅客間的潛在同行可能。

針對上述問題，本文設計了基于“旅客-航班”異構網絡的子圖抽取算法，旨在通過旅客乘坐的歷史航班記錄和航班與航班的相似關系找到潛在的旅客同行信息。在此基礎之上，對生成的旅客同行信息進行分析，發現旅客可能存在多個潛在同行信息。因此，在進行子圖抽取過程中，應保證旅客可以屬于多個子圖。因此，本文提出標簽傳播的方法進行子圖抽取并使用后處理閾值來記錄每個旅客所在的子圖。在旅客訂票記錄真實數據集上的實驗表明：相比于基準算法，本文算法在子圖模塊度和精準度指標上具有良好效果。

本文主要貢獻如下：(1) 針對旅客同行記錄高度稀疏，提出了基于旅客-航班異構網絡的旅客同行子圖抽取方法，能夠將稀疏的旅客出行記錄轉換成稠密的旅客潛在同行記錄；(2) 提出了通過隨機游走進行旅客間相似度計算方法；(3) 將本文算法應用在國內某旅客訂票記錄中，相比于LPA、COPRA、CPM等基準算法，本文在子圖抽取模塊度和準確率上具有更好效果。

1 相關工作

1.1 旅客同行研究現狀

旅客同行研究旨在通過對旅客的出行記錄發現具有潛在同行關系的旅客。葉紹貴等[4]通過對旅客同行網絡進行層次劃分，然后根據共同鄰居的信息來構造出節點的一系列層次屬性，使得網絡的特征更加豐富，并使用分類算法發現潛在同行鏈接。張奧爽等[5]根據航空公司旅客信息系統中旅客歷史出行記錄提取旅客之間的社會關系并構建旅客同行網絡，對潛在同行旅客進行分類。

上述方法研究在旅客同行同質網絡上的旅客關系鏈接預測，但并未考慮旅客與航班以及航班與航班的關系。在現實生活中，這種關系表現為乘坐相似航班的旅客有可能同行。

1.2 子圖抽取研究現狀

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

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

2 算法設計

本文首先對旅客-航班異構網絡進行隨機游走以便發現旅客潛在同行信息。旅客-航班異構網絡是由描述旅客選擇航班關系的旅客-航班二部圖，以及描述航班相似性的航班同構網絡構成。在此基礎之上，使用標簽傳播的方法根據旅客潛在同行信息進行旅客同行子圖抽取，首先得到圖中較大度的完全子圖，并為每個節點打上一個唯一的標簽，然后根據標簽傳播規則對節點標簽進行更新，最后處理可能具有多個標簽的節點。

2.1 基于“旅客-航班”異構網絡的旅客同行網絡構建

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

(1)

式中：Wxx表示“旅客-旅客”模塊；Wxy表示“旅客-航班”模塊；Wyx表示“航班-旅客”模塊；Wyy表示“航班-航班”模塊。“旅客-航班”模塊定義將旅客乘坐過相同的航班號填入到“旅客-航班”矩陣的對應位置，“旅客-航班”模塊與“航班-旅客”模塊一致。與此同時，本文構建“航班-航班”矩陣，該矩陣描述航班與航班間的相似性。航班的相似度根據航班起始地和目的地的經緯度，使用余弦相似度計算。其計算方法如下：

(2)

式中：F1以向量的形式表示航班1的經緯度；F2以向量的形式表示航班2的經緯度；構建旅客同行網絡的目的是為了得到旅客潛在同行關系。

2.2 隨機游走重構網絡

對“旅客-航班”模塊，“航班-旅客”模塊和“旅客-航班”模塊初始化后，通過隨機游走的方式對上述模塊進行更新。在本節中，根據上節構建的“航班-旅客”和“旅客-航班”關系網絡，進行旅客和旅客的相似度計算。

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

(3)

式中：Wij表示旅客i和旅客j之間的相似度；aik表示“旅客-航班”矩陣中旅客i與航班k歸一化后的權值；bkl表示“航班-航班”矩陣中航班k與航班l歸一化后的權值；clj表示“航班-旅客”中航班l與旅客j歸一化后的權值。“旅客-旅客”矩陣中的值表示的含義是旅客間潛在的同行概率，本文通過隨機游走來更新旅客間的潛在同行概率。

隨機游走可以理解為節點通過對鄰居節點的訪問，以達到對網絡進行隨機遍歷的行為。節點訪問其鄰居節點的概率被稱作轉移概率，節點轉移概率pij計算方法如下：

(4)

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

(5)

式中：θ為隨機游走次數。

2.3 標簽傳播算法

標簽傳播算法首先為圖中任意旅客節點初始化標簽；然后在標簽傳播的過程中，每個節點在接收其鄰居節點標簽的同時，也向鄰居節點發出標簽；在每個節點的存儲空間中，可以保存之前迭代所接到的標簽，為避免出現每個節點所對應子圖標簽過多的情況，標簽傳播算法使用相同標簽所占比例大于給定參數的方式來確定哪些標簽將保存下來，最終完成子圖抽取。

2.3.1標簽傳播算法初始化

由上述“旅客-航班”“航班-旅客”和“航班-航班”矩陣得到“旅客-旅客”矩陣后，本節對“旅客-旅客”矩陣進行子圖抽取。由于在初始階段，每個節點隨機接收鄰居節點的標簽，造成節點標簽收斂慢。因此，在初始化階段，本文首先發現圖中完全子圖，然后使得完全子圖持有相同的標簽，提高算法收斂速度的同時減少算法的隨機性。

定義1完全子圖。若圖G1是圖G的子圖且G1中每個節點對之間都有一條邊相連，則G1是G的完全子圖。

以完全子圖進行標簽傳播，往往能取得較好的效果[15]。其原因是完全子圖內部連接緊密，因此其標簽一致，在標簽傳播過程中可以看作一個節點，進而加快標簽傳播過程。其算法描述如算法1所示。

算法1以較高節點度為中心的完全子圖

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

輸出：完全子圖集合G。

BEGIN

(1) 初始化節點標簽：為“旅客-旅客”矩陣N中的每個節點按照從1到n的順序編號；

(2) 從編號1的節點開始搜索；

(3) If節點i未被搜索；

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

(5) 搜索節點i的鄰居節點中度大于等于i的節點集合，從中選擇度最大的節點p，若度最大節點不唯一時，則隨機選取一個節點，并將其標記為已被搜索；

(6)Gp=Gp∪p；

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

(7) 搜索節點p的鄰居節點，從中選擇度最大的節點，若度最大節點不唯一，則隨機選擇一個節點q；

(8) 如果q的鄰居節點k與Gp中的節點均有邊時，將其加入到Gp，并將節點標記為已被搜索；

(9) 更新Gp節點中的標簽為相同標簽。

算法首先為每個節點進行標簽化，接著在未搜索的區域找到節點度較大的節點，并將其作為完全子圖的中心節點。完全子圖的搜索過程是指選擇與中心節點相連的度最大的節點，將其加入完全子圖集合；接著選擇與完全子圖集合中所有元素都相連的最大度的節點將其加入完全子圖集合，并將同一個完全子圖集合中的元素統一貼上相同標簽。反復執行以上操作，圖中會得到多個完全子圖。完全子圖的元素作為標簽傳播的初始點。

2.3.2標簽傳播過程

初始化階段，每個節點的標簽已被標記，首先對完全子圖中的元素進行傳播，然后對完全子圖外的節點按照節點編號更新。該傳播策略減輕網絡中較重要節點在更新標簽的過程中受到圖中邊緣節點標簽的影響。

在選定當前需要更新標簽的節點后，與其直接相連的節點標簽作為當前節點更改標簽的因素。其更改標簽需要遵循如下原則：節點按鄰居節點出現頻次最高的標簽進行修改，若存在多個相同頻次的標簽，則根據“旅客-旅客”矩陣中旅客的相似度，選擇相似度高的節點的標簽，將其修改為自身標簽。節點標簽傳播規則使用同步更新方法，其表示如下：

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

(6)

式中：Ci(m)表示節點i的第m次的標簽；Ci1(m-1)和Cit(m-1)表示節點i第1個至t個鄰居節點在m-1次出現的標簽。相比于異步更新，同步更新在更新節點標簽時，僅依賴前一次更新的標簽集，減少了因為節點更新順序不同而產生的隨機性。因此本文使用同步更新策略來更新節點的標簽傳播。

2.3.3重疊子圖發現

標簽傳播算法記錄了每個節點的每個標簽，在迭代結束后，計算每個節點互異標簽出現的概率，以便發現可能屬于多個子圖的節點。每個不同標簽的概率表示如下：

(7)

式中：T為迭代的次數；count(labeli)表示在迭代過程中；labeli出現的次數。若節點中出現兩個最高的相同概率的標簽，則保留這兩個標簽，節點擁有多個標簽表明節點可能屬于多個子圖。在節點標簽達到迭代次數或趨于穩定后，對每個節點的標簽矩陣進行分析，其目的是保留大于閾值的標簽，并將其作為節點的最終標簽，刪除剩余標簽。標簽傳播算法如算法2所示。

算法2以標簽傳播方法進行子圖抽取

輸入：初始化后的旅客同行網絡M，迭代次數T,后處理閾值r。

輸出：節點標簽列表listi。

BEGIN

(1) 采用同步更新方式，根據鄰居節點標簽信息對目標節點進行更新；

(2) 如果目標節點的鄰居節點出現最多的標簽唯一，修改目標節點的標簽；否則根據旅客同行網絡中旅客-旅客的權值，選擇權值最高的旅客節點的標簽作為目標節點的標簽；

(3) 重復上述步驟(1)-步驟(2),直到達到迭代次數T或標簽趨于穩定；

(4) 記錄每次目標節點的標簽，在迭代結束后，計算互異標簽出現的概率；

(5) 根據節點互異標簽的概率和后處理閾值r，選擇最終作為目標節點的標簽，并刪除其余標簽。

3 算法復雜性分析

假設旅客節點數為m，航班節點數為n，隨機游走的迭代次數為l，旅客節點的平均度為k，完全子圖的數量為f，標簽傳播過程迭代次數為t，在迭代完成后具有多個標簽的節點數量為n。本節主要從時間復雜度方面對子圖抽取方法進行分析。

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

標簽傳播方法分為初始化階段和標簽傳播階段。在初始化階段中，需要給每個節點編碼，其時間復雜度為O(m)，在算法1中，搜索完全子圖的時間復雜度不超過O(mkf)。在標簽傳播階段，更新標簽所需要的時間復雜度為O(mkt)，發現重疊子圖所需要的時間復雜度為O(tm)，因此標簽傳播方法的時間復雜度為O(m+mkf+mkt+tm)。

4 實 驗

將上述算法應用到國內某航空公司旅客訂票記錄(PNR)真實數據集中，并檢驗其準確度、模塊度和算法收斂速度。

4.1 實驗設置

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

表1 旅客訂票記錄示例

表2 航班信息示例

4.1.1數據預處理

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

表3 帶標簽的201Y年旅客訂票記錄

4.1.2基準算法

通過參考大量國內外文獻，未曾有人在旅客訂票記錄數據集中進行子圖抽取算法比較。因此，本文基準算法選取在公共數據集中表現較好的子圖抽取算法，并將本文算法與之比較。

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

4.1.3評價指標

性能指標為用來衡量重疊子圖質量的模塊度及衡量子圖抽取準確度的標準化互信息。模塊度EQ計算公式如下：

(8)

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

標準化互信息NMI計算公式如下：

(9)

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

4.1.4算法參數設置

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

4.2 實驗結果

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

表4 子圖抽取性能比較

4.3 實驗分析

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

圖1 不同θ下的NMI對比

相比于CPM算法，本文算法通過發現高節點度的完全子圖進行傳播，保障算法找到合適的起點，進而加快節點收斂速度。相比于SLPA和COPRA算法，本文在模塊度和標準化互信息方面均有提高。SLPA和COPRA算法在識別子圖過程中隨機性較強，具有很強的振蕩現象。而本文算法在標簽傳播過程中，考慮到節點的相似性，在選擇標簽的時候會優先選擇相似度大的節點的標簽，進而減少因隨機選取而產生的不確定性，并且因為本文在標簽傳播初始化階段通過完全子圖進行傳播，將具有緊密關系的節點在開始階段標記相同標簽，相比于SLPA和COPRA算法，減少因隨機標注標簽而導致的精確度下降問題。算法迭代過程如圖2所示，可以看到，在剛開始迭代時隨機性較大，隨著迭代次數的增多，迭代到16次時算法收斂性趨于平穩。產生該現象的原因是在開始階段節點選擇標簽隨機性較大，導致在初始階段節點被分為多個子圖。在每次迭代過程中，節點的標簽都會被儲存下來。多次迭代后節點的標簽也趨于固定。

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

5 結 語

針對旅客同行網絡稀疏問題，本文提出了基于“旅客-航班”異構網絡的旅客同行子圖抽取算法。算法首先構建旅客-航班異構網絡矩陣，其次對其進行隨機游走以計算旅客潛在同行概率。在此基礎之上，設計了一種基于標簽傳播的子圖抽取算法，節點根據鄰居節點標簽以更改自身標簽，并且可發現屬于多個子圖的節點。為了加快迭代速度，進一步設計了基于完全子圖的節點標簽初始化方法。算法理論分析進一步表明算法求解過程是線性的。并在國內某旅客訂票數據集上驗證了算法性能的優越性。后期可圍繞異構網絡和動態子圖的抽取進行研究。