重要節點發現算法在民航旅客社會網絡中的應用研究

曹衛東　白　亮　劉紅霞

1(中國民航大學計算機科學與技術學院　天津 300300)

2(中國民航信息技術科研基地　天津 300300)

3(國網丹東供電公司　遼寧 丹東 118000)

?

重要節點發現算法在民航旅客社會網絡中的應用研究

曹衛東1,2白亮3劉紅霞1

1(中國民航大學計算機科學與技術學院天津 300300)

2(中國民航信息技術科研基地天津 300300)

3(國網丹東供電公司遼寧 丹東 118000)

摘要當前，民航旅客價值分析把每一個旅客當作彼此不相關聯的實體，忽略了旅客間存在的關系。針對這種情況，提出從旅客間的相互影響角度出發，量化這種影響的強弱。基于PNR(Passenger Name Record)數據構建民航旅客社會網絡，從系統科學、網絡關系和互聯網搜索這三個角度研究社會網絡中節點重要性的評估算法，并把這三種算法應用在民航旅客社會網絡中。最后，通過F-度量方法對這三種算法計算出的重要節點進行相似性比較。實驗結果表明，該方法能夠有效地得到民航旅客社會網絡中的重要旅客。

關鍵詞民航旅客社會網絡PNR數據社會網絡重要節點發現算法F-度量

ON APPLICATION OF IMPORTANT NODES DISCOVERY ALGORITHM IN SOCIAL NETWORK OF CIVIL AVIATION PASSENGERS

Cao Weidong1,2Bai Liang3Liu Hongxia1

1(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)2(Information Technology Research Base of CAAC,Tianjin 300300,China)3(State Grid Power Supply Company of Dandong,Dandong 118000,Liaoning,China)

AbstractAt present, the value analysis on civil aviation passengers deems every traveller as an entity with no association with each other, but overlooks the relationship between passengers. For this issue, proceeding from the perspective of mutual influence between passengers, we quantify the strength of such influence, and construct the social networks of civil aviation passengers based on PNR data, then research the evaluation algorithm of the node importance in social network from three perspectives of system science, networking and Internet searching, and apply these three algorithms in social networks of civil aviation passenger. Finally, we make the similarity comparison on the important nodes calculated by the above three algorithms through F-measure approach. Experimental result demonstrates that this method can effectively find out the important passengers in social networks of civil aviation.

KeywordsSocial network of civil aviation passengerPNR dataAlgorithm of discovering important nodes in social networkF-measure approach

0引言

隨著民航信息化程度的日益加深，民航的信息系統中積累了大量的旅客信息及其行為數據，運用數據挖掘與分析領域的最新研究成果，從海量信息中發現高價值旅客，并對這些旅客提供更加具有針對性的機艙服務顯得尤為重要。而當前關于民航數據挖掘方面的研究，大多是基于傳統的數據挖掘方法[1]，比如在旅客價值分析方面，主要是針對彼此不相關聯的、單個的旅客數據進行分析，相對比較片面。

民航旅客社會網絡是指由民航旅客及其相互關系組成的一種結構體系[2],而社區發現技術幫助人們了解網絡中不同結構的功能特性，分析整個網絡的層次結構，并預測網絡行為模式，具有非常重要的理論意義[3]。文獻[2]中，李勇等人對PNR數據特征進行分析，提出了民航旅客社會網絡的構建方法，文獻[3]中，陳卉敏等人提出一種結合奇異值分解(SVD)的對稱非負矩陣分解(SNMF)社區發現方法，用于發現復雜網絡社區。

因此，可以把社會網絡相關技術應用在民航領域中。旅客作為真實的社會個體，其行為模式受到其所處的社會網絡結構影響，通過對民航旅客社會網絡的構建與挖掘，可以獲得更有價值的旅客，從而為民航企業提高服務質量提供有利依據，并為企業市場營銷提供決策支持[4]。

1基于PNR數據構建民航旅客社會網絡

民航旅客信息系統中積累了大量的旅客信息及行為數據，充分利用這些海量數據，挖掘出高價值旅客，并服務于航空公司的管理、經營，具有重要的實際意義[5]。旅客訂座記錄PNR作為民航旅客系統中的重要數據，不僅包含了旅客的基本個人信息，而且包含了旅客的行為數據，如訂座時間、出發機場、目的機場、艙位代碼等，這為民航旅客社會網絡的構建提供了一定的基礎。因此，這里介紹一種基于PNR數據的民航旅客社會網絡構建方法。

1.1PNR數據分析

PN反映旅客的航程、旅客信息及航班座位占用情況。PNR數據主要屬性如表1所示。

表1　PNR數據中包含的屬性

在PNR數據中，不同旅客間對應的BOOK_ID是不同的，而同一旅客對應的BOOK_ID是相同的，所以它唯一地標識了每名旅客。當系統一次為多名旅客預訂同一航班時，對應PNR數據中BOOK_PNR_ID是相同的。當兩名旅客的PNR數據中BOOK_FLT_CODE，BOOK_FLT_DATE，BOOK_FLT_DPT_TIME都相同時，就標志著這兩名旅客乘坐的同一架班次。

1.2民航旅客社會網絡的構建

以社會個體為節點，兩個社會個體之間的關系為邊的網絡稱為社會網絡。社會網絡具有復雜的連接關系，且具有無標度分布特性以及小世界性等性質[6-8]。社會網絡分析的意義在于,它為各種關系提供了精確的量化分析，從而為構建理論模型和檢驗實證命題提供模擬[9], 所以為了更準確地分析出民航旅客中的高價值客戶，構建了以旅客為網絡節點，旅客間關系為網絡中邊，關系的強弱為權重的民航旅客社會網絡。

點的確定：由于在PNR記錄中BOOK_ID可以唯一標識每名旅客，所以就以每個不同的BOOK_ID來代表網絡中的節點。

邊的確定：在民航旅客社會網絡中，邊的實質就是旅客間的關系，主要是分為以下兩種情況：

一是多名旅客一起訂票乘機：一般來說，如果兩個人或多個人一起訂票乘機，那么他們存在某種親密關系的概率是較大的，這時他們的PNR數據中BOOK_PNR_ID是相同的，因此可以把PNR數據中BOOK_PNR_ID相同作為旅客之間存在關系的一種依據。

二是一同乘坐同一航班多次：因為陌生人一同乘機多次的可能性很小，只有相互熟悉的人才有可能多次一同乘機，而PNR數據中BOOK_FLT_CODE，BOOK_FLT_DATE，BOOK_FLT_DPT_TIME這三個屬性值可以唯一標識旅客乘坐的航班，因此可以通過這三個屬性值統計出每名旅客所乘坐的航班，然后計算出每兩名旅客所乘坐航班的交集，如果交集中兩名旅客多次一同乘坐這一航班，就可以認為這兩名旅客之間存在關系。

權重的確定：在民航旅客社會網絡中的，權重實質就是指旅客間關系強弱的量化值，在量化的過程中主要遵循以下規則：

一是當多名旅客一同訂票乘機的時候，旅客人數越多關系就越疏遠。如果超過10名以上的旅客一同訂票，他們有可能是某個團體一同組織出行，也有可能是陌生的游客一同組團出行，例如導游帶領10人以上的觀光團乘機，那么這些旅客彼此之間并不熟悉，所以他們之間的關系是隨著人數的增加而不斷減弱的。因此，基于上述分析，在此引入旅客間關系權重來表示旅客之間關系的親密程度，如表2所示。

表2　旅客間關系權重

當兩名旅客同時與多個團體一同訂票時，選擇團體中權重最大值作為兩旅客的權重，例如旅客A與旅客B一同訂過票，且他們還和一個十人團體一同訂過票，這時旅客A與旅客B之間的關系權重就選為4。

二是當兩名旅客一同乘坐同一航班多次時，同乘次數越多關系就越緊密。這時關系權重的量化就遵循以下規則：若兩名旅客曾一起訂過票，則關系權重為上述一中的關系權重加上同乘次數再減去1，若兩旅客沒有一起訂過票，則關系權重為同乘次數。

在構建民航旅客社會網絡時，主要是根據網絡中的節點關系來進一步查找網絡中的重要節點，所以孤立點在構建過程中是沒有價值的。因此，在構建民航旅客社會網絡之前，首先要把PNR數據集中的孤立點去掉，再按照點、邊、權重的生成規則構建民航旅客社會網絡。

2基于社會網絡的重要節點發現算法研究

通過PNR數據構建出的民航旅客社會網絡，實質就是一個加權的社會網絡，基于社會網絡的重要節點發現算法有很多，但本質上都是從系統科學、網絡關系和互聯網搜索這三個領域來研究的，因此選取這三個領域比較具有代表性的三個算法做了相關研究。在系統科學領域選取了基于節點刪除思想的節點綜合測度算法；在網絡關系領域選取了基于度、點權、鄰近節點、距離等多指標的等效點權值算法；在互聯網搜索領域選取了基于相似度貢獻的節點重要性評估算法，同時，為了比較在民航旅客社會網絡中尋找到的重要節點，利用相似性比較函數F(r)對不同排序結果間的相似度進行度量，從而找出民航旅客社會網絡中的重要節點。

2.1邊權值的意義

一個邊賦權值的圖或網絡，邊權的意義在于節點間彼此作用的強度[10]，在物理網絡中，有客觀的權重，例如家用寬帶的帶寬；也有主觀的權重，例如社會生活中人與人之間的親近程度。在遇到上述情況時，一般采取的措施是遵循相異性原則或相似性原則，處理相異性網絡時，如果節點對間的權值越大，那么節點對間的距離也越大，節點間也越疏遠；處理相似性網絡時，如果節點對間的權值越大，那么節點對間的距離就越小，節點間的關系就越近，設節點i與節點j間通過二個權重為wki和wkj的邊連接，則關于節點對間的距離dij，有如下公式：

相異性網絡：dij=wik+wkj

(1)

(2)

由相異性和相似性網絡中兩節點間的距離公式，可以看出兩節點間最短路徑的意義是不變的，即上述距離公式表示兩節點間的最優連通路徑，這為利用Floyd算法計算節點間最短路徑奠定了基礎。顯然，民航旅客社會網絡應該是屬于相似性網絡，所以在求節點間最短路徑時，不作特殊說明的都是使用式(2)為基礎計算的。

2.2節點綜合測度算法

節點綜合測度算法，主要基于節點刪除思想，這種算法在節點刪除后會對連通分支產生較大影響，主要分為兩種損失，即直接損失和間接損失[11]。

直接損失(DLOS)：被刪除節點無法連接其它節點所造成的路徑損失，計算公式如下：

(3)

間接損失(ILOS)：節點刪除造成其它節點不能相互連通所導致的路徑損失，計算公式如下：

(4)

節點損失(TLOS)：基于 DLOS 和 ILOS ，節點損失的計算公式如式(5)，如果節點損失越大，那么節點就越重要：

TLOS(vi)=DLOS(vi)+ILOS(vi)

(5)

利用TLOS的計算公式，可以對網絡中的所有節點進行重要度排序。

2.3等效點權值算法

等效點權值算法主要考慮度，點權，接近度，鄰近節點，距離等復雜網絡的評價指標對節點重要性的影響[12-14]，這種影響分為點權影響和附加點權影響。

點權：在社會網絡中，點權具有非常重要的意義，它是與節點相關聯的所有邊的權值和：

(6)

其中ηi為節點i鄰域內邊的集合。

附加點權：考慮度，鄰近節點，距離因素等指標：

(7)

由此給出節點i的等效點權：

(8)

綜上所述，節點本身點權以及網絡中所有其他點權對等效點權的影響較大，距離中心節點越近，對中心節點的等效點權貢獻值就越大。在評價節點重要性時，節點等效點權越大，節點就越重要。

2.4基于相似度貢獻的節點重要性算法

該算法是在Pagerank算法的基礎上進行了優化。Pagerank算法以網頁為信息處理單元,把每一個網頁抽象為Web結構圖上的一個節點,對每一個網頁節點計算其對應的Pagerank值,然后根據其值的大小排序，并找到重要的網頁節點[15]。Pagerank的計算公式如下：

(9)

Pagerank算法的缺點是對于一個節點的所有鄰接節點，這個節點給予了相同的轉移概率，相應的優化方法是根據節點間的相似度大小來確定節點之間的轉移概率。所以提出了基于相似度貢獻的節點重要性算法，算法的核心思想是利用節點的NodeRank值來衡量節點的重要性[16]，算法過程如圖1所示。

圖1　基于相似度貢獻的節點重要性算法流程

以下是算法的幾個關鍵步驟。

(1) 構造節點相似性矩陣

Leieh E A等[17]通過嚴格的數學推理給出了計算節點間相似度值的算法,其核心思想是：如果節點v的鄰接節點是i和j，那么節點i與節點j相似，如果每個節點與自身完全相似，那么節點i與節點j的相似度值Sij如式(10)(其中φ和φ都是調節系數)，因此，該度量方法的迭代的。

(10)

矩陣表示為：

S=φAS+φE

(11)

可變為：

S=φ-1[E-φA]-1

(12)

(2) 構造概率轉移矩陣

將節點相似度矩陣S歸一化，可以求得初始的概率轉移矩陣Mtran如下：

(13)

(3) 計算節點的中心度值

首先，把圖的鄰接矩陣A轉化成距離矩陣D，即把Aij=0的轉化成Dij=∞。再根據Floyd算法得到任意兩點間的最短路徑Bij。最后，進行歸一化并計算得到節點i的中心度值ti：

(14)

2.5利用F-度量確定重要節點

由于以上三個算法是從三個不同角度來衡量節點的重要性的，所以所求的結果會有一定的差異性，為了更形象地比較由三個算法分別得到的重要節點的可靠性，采用結果相似性比較函數F(r)來度量兩個不同排序結果間的相似度[18]，取相似度較高的一組作為網絡中的重要節點。

F(r) 的定義如下：

(15)

其中L(r)以及L′(r)分別為所比較的兩個排序算法的前r個節點的集合。

3實驗分析

3.1實驗數據及可視化分析

實驗分析所采用的實驗數據是某航空公司多條航線上2010年1月的真實PNR數據，共計13 582 388條記錄，生成7 703 972個旅客節點，3 856 602條邊，從這個網絡中獲取它的最大連通子網(153個節點，1814條邊)作為研究對象。為了更加直觀地觀察節點間的關系，采用Cytoscape軟件對網絡進行了可視化，由于Cytoscape軟件只能對無權圖進行可視化，所以圖2中不包括權重。但是，在算法進行計算時，每條邊的權重是存在的。

圖2　民航旅客社會網絡的構建圖

對于上述的網絡進行分析，由圖3中的平均路徑長度分布，以及圖4中的平均聚類系數分布，計算得出，其網絡的基本屬性值如表3所示。

表3　民航旅客社會網絡的有關參數值

圖3　平均路徑長度分布

圖4　平均聚類系數分布

從表3中可以看出網絡中的平均聚類系數為0.716，平均路徑長度為3.213，說明民航旅客社會網絡符合社會網絡聚類系數高，平均路徑長度短的小世界性。

3.2實驗結果

把上述三種計算重要節點的算法應用到3.1節中得到的民航旅客社會網絡中，可以得到這156個節點的重要性排序結果，如表4所示(取每種算法排序結果的前10名)。

表4　三種算法的排序結果

為了更加形象地比較出上述三個算法的排序結果，采用F-度量方法，計算出結果的相似度，如表5所示。

表5　基于F-度量方法的結果相似度對比圖

其中1代表等效點權值算法，2代表節點綜合測度算法，3代表基于相似度貢獻的節點重要性評估算法。

可以看出：各個算法得到結果的相似度都很高，基本上都在80%以上，其中算法1和算法3的評價結果是最相似的，它們分別是從節點刪除后造成的損失和節點相似性兩個完全不同的方面來研究的，但是評價出的結果卻基本一致。所以基于F-度量方法的結果，最后選取算法1和算法3共同的排序結果，其中前五名如表6所示。

表6　民航旅客社會網絡的前五名重要節點

3.3結果分析

實驗分別從節點度、點權、二重度、二重點權以及實際數據庫中節點1月份出行情況兩個方面，對排序結果進行了可靠性分析，排序結果見表7所示。

表7　節點度，點權，二重度，二重點權的排序結果

其中，度是指與該節點相鄰的所有節點的個數；點權是指與該節點相鄰的所有節點的權重之和；二重度是指與節點相鄰的所有節點的度之和；二重點權是指與節點相鄰的所有節點的點權之和。

從表7可以看出：分別按節點度、點權、二重度、二重點權排序的結果的前五名也正好是3.2節中所求的五個重要節點。因此，進一步地說明了最后所求出的重要節點是準確的。

4結語

本文主要從民航旅客社會網絡的構建以及重要節點發現算法在民航旅客社會網絡的應用方面展開研究，通過挖掘PNR數據間的內在關系，進一步推測出民航旅客間的關系以及這種關系的強弱，從而構建出民航旅客社會網絡。在此基礎上分析了多種社會網絡重要節點發現算法，并進一步地把這些算法應用在了民航旅客社會網絡中，最后通過F-度量方法對結果進行了相似性比較，確定出重要的民航旅客。實驗結果證明，本次研究為民航旅客社會網絡分析與挖掘提供了社會網絡類型的數據支持，并更加全面準確地分析了民航旅客，為提高航空公司效益，改善民航旅客服務提供了有力依據。

參考文獻

[1] 王紅,李曉輝.基于數據挖掘的航空公司客戶信息分析[J].計算機工程,2005,31(S1):189-191.

[2] 馮霞,李勇,陳卉敏.民航旅客社會網絡構建方法研究[J].計算機仿真,2013,30(6):51-54.

[3] 馮霞,陳卉敏,李勇.一種結合SVD的SNMF復雜網絡社區發現方法[J].信息與控制,2013,42(3):387-391.

[4] 潘玲玲.基于旅客行為的航空旅客細分模型研究及其實現[D].南京:南京航空航天大學,2012.

[5] 羅利,彭際華.競爭環境下的民航客運收益管理動態定價模型[J].系統工程理論與實踐,2007(11):15-24.

[6] Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[7] Watts D J,Strogatz S H.Collective dynamics of small world networks[J].Nature,1998,393(4):440-442.

[8] Barabasi A L,Bonabeau E.Scale-Free networks[J].Scientific American,2003,288(5):60-69.

[9] 楊育彬,李寧,張瑤.基于社會網絡可視化分析的數據挖掘[J].軟件學報,2008,19(8):1980-1994.

[10] Tang J T,Wang T,Wang J.Shortest Path Approximate Algorithm for Complex Network Analysis[J].Journal of software,2011,22(10):2279-2290.

[11] 喬少杰,唐常杰,彭京,等.基于個性特征仿真郵件分析系統挖掘犯罪網絡核心[J].計算機學報,2008,31(10):1795-1803.

[12] 王昊翔,曾珊,劉揮揚.虛擬社交網絡中節點重要度分析[J].上海交通大學學報,2013,47(7):1055-1059.

[13] 王喆.基于復雜網絡的社區發現算法研究[D].吉林:吉林大學,2013.

[14] 司曉靜.復雜網絡中節點重要性排序的研究[D].西安:西安電子科技大學,2012.

[15] Opsahl T,Agneessens F,Skvoretz J.Node centrality in weighted networks:Generalizing degree and shortest paths[J].Social Networks,2010,32:245-251.

[16] Wagner C,Roessner J,Bobb K,et al.Approaches to understanding and measuring interdisciplinary scientific research(IDR):A review of the literature[J].Journal of Informatics,2011,5(1):14-26.

[17] Okamoto K,Chen W,Li X.Ranking of closeness centrality for large-scale social networks[J].Lecture Notes in Computer Science,2008,5059:186-195.

[18] Kim H,Tang J,Aderson R,et al.Centrality prediction in dynamic human contact networks[J].Computer Networks,2012,56(3):983-996.

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.055

收稿日期：2014-07-22。國家自然科學基金項目(60879015)；中國民航局科研基金項目(MHRD201130)。曹衛東，副教授，主研領域：數據庫與數據挖掘。白亮，碩士生。劉紅霞，碩士生。