重要節(jié)點(diǎn)發(fā)現(xiàn)算法在民航旅客社會(huì)網(wǎng)絡(luò)中的應(yīng)用研究

曹衛(wèi)東　白　亮　劉紅霞

1(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　天津 300300)

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

3(國(guó)網(wǎng)丹東供電公司　遼寧 丹東 118000)

?

重要節(jié)點(diǎn)發(fā)現(xiàn)算法在民航旅客社會(huì)網(wǎng)絡(luò)中的應(yīng)用研究

曹衛(wèi)東1,2白亮3劉紅霞1

1(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院天津 300300)

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

3(國(guó)網(wǎng)丹東供電公司遼寧 丹東 118000)

摘要當(dāng)前，民航旅客價(jià)值分析把每一個(gè)旅客當(dāng)作彼此不相關(guān)聯(lián)的實(shí)體，忽略了旅客間存在的關(guān)系。針對(duì)這種情況，提出從旅客間的相互影響角度出發(fā)，量化這種影響的強(qiáng)弱。基于PNR(Passenger Name Record)數(shù)據(jù)構(gòu)建民航旅客社會(huì)網(wǎng)絡(luò)，從系統(tǒng)科學(xué)、網(wǎng)絡(luò)關(guān)系和互聯(lián)網(wǎng)搜索這三個(gè)角度研究社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的評(píng)估算法，并把這三種算法應(yīng)用在民航旅客社會(huì)網(wǎng)絡(luò)中。最后，通過(guò)F-度量方法對(duì)這三種算法計(jì)算出的重要節(jié)點(diǎn)進(jìn)行相似性比較。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效地得到民航旅客社會(huì)網(wǎng)絡(luò)中的重要旅客。

關(guān)鍵詞民航旅客社會(huì)網(wǎng)絡(luò)PNR數(shù)據(jù)社會(huì)網(wǎng)絡(luò)重要節(jié)點(diǎn)發(fā)現(xiàn)算法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引言

隨著民航信息化程度的日益加深，民航的信息系統(tǒng)中積累了大量的旅客信息及其行為數(shù)據(jù)，運(yùn)用數(shù)據(jù)挖掘與分析領(lǐng)域的最新研究成果，從海量信息中發(fā)現(xiàn)高價(jià)值旅客，并對(duì)這些旅客提供更加具有針對(duì)性的機(jī)艙服務(wù)顯得尤為重要。而當(dāng)前關(guān)于民航數(shù)據(jù)挖掘方面的研究，大多是基于傳統(tǒng)的數(shù)據(jù)挖掘方法[1]，比如在旅客價(jià)值分析方面，主要是針對(duì)彼此不相關(guān)聯(lián)的、單個(gè)的旅客數(shù)據(jù)進(jìn)行分析，相對(duì)比較片面。

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

因此，可以把社會(huì)網(wǎng)絡(luò)相關(guān)技術(shù)應(yīng)用在民航領(lǐng)域中。旅客作為真實(shí)的社會(huì)個(gè)體，其行為模式受到其所處的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)影響，通過(guò)對(duì)民航旅客社會(huì)網(wǎng)絡(luò)的構(gòu)建與挖掘，可以獲得更有價(jià)值的旅客，從而為民航企業(yè)提高服務(wù)質(zhì)量提供有利依據(jù)，并為企業(yè)市場(chǎng)營(yíng)銷提供決策支持[4]。

1基于PNR數(shù)據(jù)構(gòu)建民航旅客社會(huì)網(wǎng)絡(luò)

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

1.1PNR數(shù)據(jù)分析

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

表1　PNR數(shù)據(jù)中包含的屬性

在PNR數(shù)據(jù)中，不同旅客間對(duì)應(yīng)的BOOK_ID是不同的，而同一旅客對(duì)應(yīng)的BOOK_ID是相同的，所以它唯一地標(biāo)識(shí)了每名旅客。當(dāng)系統(tǒng)一次為多名旅客預(yù)訂同一航班時(shí)，對(duì)應(yīng)PNR數(shù)據(jù)中BOOK_PNR_ID是相同的。當(dāng)兩名旅客的PNR數(shù)據(jù)中BOOK_FLT_CODE，BOOK_FLT_DATE，BOOK_FLT_DPT_TIME都相同時(shí)，就標(biāo)志著這兩名旅客乘坐的同一架班次。

1.2民航旅客社會(huì)網(wǎng)絡(luò)的構(gòu)建

以社會(huì)個(gè)體為節(jié)點(diǎn)，兩個(gè)社會(huì)個(gè)體之間的關(guān)系為邊的網(wǎng)絡(luò)稱為社會(huì)網(wǎng)絡(luò)。社會(huì)網(wǎng)絡(luò)具有復(fù)雜的連接關(guān)系，且具有無(wú)標(biāo)度分布特性以及小世界性等性質(zhì)[6-8]。社會(huì)網(wǎng)絡(luò)分析的意義在于,它為各種關(guān)系提供了精確的量化分析，從而為構(gòu)建理論模型和檢驗(yàn)實(shí)證命題提供模擬[9], 所以為了更準(zhǔn)確地分析出民航旅客中的高價(jià)值客戶，構(gòu)建了以旅客為網(wǎng)絡(luò)節(jié)點(diǎn)，旅客間關(guān)系為網(wǎng)絡(luò)中邊，關(guān)系的強(qiáng)弱為權(quán)重的民航旅客社會(huì)網(wǎng)絡(luò)。

點(diǎn)的確定：由于在PNR記錄中BOOK_ID可以唯一標(biāo)識(shí)每名旅客，所以就以每個(gè)不同的BOOK_ID來(lái)代表網(wǎng)絡(luò)中的節(jié)點(diǎn)。

邊的確定：在民航旅客社會(huì)網(wǎng)絡(luò)中，邊的實(shí)質(zhì)就是旅客間的關(guān)系，主要是分為以下兩種情況：

一是多名旅客一起訂票乘機(jī)：一般來(lái)說(shuō)，如果兩個(gè)人或多個(gè)人一起訂票乘機(jī)，那么他們存在某種親密關(guān)系的概率是較大的，這時(shí)他們的PNR數(shù)據(jù)中BOOK_PNR_ID是相同的，因此可以把PNR數(shù)據(jù)中BOOK_PNR_ID相同作為旅客之間存在關(guān)系的一種依據(jù)。

二是一同乘坐同一航班多次：因?yàn)槟吧艘煌藱C(jī)多次的可能性很小，只有相互熟悉的人才有可能多次一同乘機(jī)，而PNR數(shù)據(jù)中BOOK_FLT_CODE，BOOK_FLT_DATE，BOOK_FLT_DPT_TIME這三個(gè)屬性值可以唯一標(biāo)識(shí)旅客乘坐的航班，因此可以通過(guò)這三個(gè)屬性值統(tǒng)計(jì)出每名旅客所乘坐的航班，然后計(jì)算出每?jī)擅每退俗桨嗟慕患?，如果交集中兩名旅客多次一同乘坐這一航班，就可以認(rèn)為這兩名旅客之間存在關(guān)系。

權(quán)重的確定：在民航旅客社會(huì)網(wǎng)絡(luò)中的，權(quán)重實(shí)質(zhì)就是指旅客間關(guān)系強(qiáng)弱的量化值，在量化的過(guò)程中主要遵循以下規(guī)則：

一是當(dāng)多名旅客一同訂票乘機(jī)的時(shí)候，旅客人數(shù)越多關(guān)系就越疏遠(yuǎn)。如果超過(guò)10名以上的旅客一同訂票，他們有可能是某個(gè)團(tuán)體一同組織出行，也有可能是陌生的游客一同組團(tuán)出行，例如導(dǎo)游帶領(lǐng)10人以上的觀光團(tuán)乘機(jī)，那么這些旅客彼此之間并不熟悉，所以他們之間的關(guān)系是隨著人數(shù)的增加而不斷減弱的。因此，基于上述分析，在此引入旅客間關(guān)系權(quán)重來(lái)表示旅客之間關(guān)系的親密程度，如表2所示。

表2　旅客間關(guān)系權(quán)重

當(dāng)兩名旅客同時(shí)與多個(gè)團(tuán)體一同訂票時(shí)，選擇團(tuán)體中權(quán)重最大值作為兩旅客的權(quán)重，例如旅客A與旅客B一同訂過(guò)票，且他們還和一個(gè)十人團(tuán)體一同訂過(guò)票，這時(shí)旅客A與旅客B之間的關(guān)系權(quán)重就選為4。

二是當(dāng)兩名旅客一同乘坐同一航班多次時(shí)，同乘次數(shù)越多關(guān)系就越緊密。這時(shí)關(guān)系權(quán)重的量化就遵循以下規(guī)則：若兩名旅客曾一起訂過(guò)票，則關(guān)系權(quán)重為上述一中的關(guān)系權(quán)重加上同乘次數(shù)再減去1，若兩旅客沒(méi)有一起訂過(guò)票，則關(guān)系權(quán)重為同乘次數(shù)。

在構(gòu)建民航旅客社會(huì)網(wǎng)絡(luò)時(shí)，主要是根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)關(guān)系來(lái)進(jìn)一步查找網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，所以孤立點(diǎn)在構(gòu)建過(guò)程中是沒(méi)有價(jià)值的。因此，在構(gòu)建民航旅客社會(huì)網(wǎng)絡(luò)之前，首先要把PNR數(shù)據(jù)集中的孤立點(diǎn)去掉，再按照點(diǎn)、邊、權(quán)重的生成規(guī)則構(gòu)建民航旅客社會(huì)網(wǎng)絡(luò)。

2基于社會(huì)網(wǎng)絡(luò)的重要節(jié)點(diǎn)發(fā)現(xiàn)算法研究

通過(guò)PNR數(shù)據(jù)構(gòu)建出的民航旅客社會(huì)網(wǎng)絡(luò)，實(shí)質(zhì)就是一個(gè)加權(quán)的社會(huì)網(wǎng)絡(luò)，基于社會(huì)網(wǎng)絡(luò)的重要節(jié)點(diǎn)發(fā)現(xiàn)算法有很多，但本質(zhì)上都是從系統(tǒng)科學(xué)、網(wǎng)絡(luò)關(guān)系和互聯(lián)網(wǎng)搜索這三個(gè)領(lǐng)域來(lái)研究的，因此選取這三個(gè)領(lǐng)域比較具有代表性的三個(gè)算法做了相關(guān)研究。在系統(tǒng)科學(xué)領(lǐng)域選取了基于節(jié)點(diǎn)刪除思想的節(jié)點(diǎn)綜合測(cè)度算法；在網(wǎng)絡(luò)關(guān)系領(lǐng)域選取了基于度、點(diǎn)權(quán)、鄰近節(jié)點(diǎn)、距離等多指標(biāo)的等效點(diǎn)權(quán)值算法；在互聯(lián)網(wǎng)搜索領(lǐng)域選取了基于相似度貢獻(xiàn)的節(jié)點(diǎn)重要性評(píng)估算法，同時(shí)，為了比較在民航旅客社會(huì)網(wǎng)絡(luò)中尋找到的重要節(jié)點(diǎn)，利用相似性比較函數(shù)F(r)對(duì)不同排序結(jié)果間的相似度進(jìn)行度量，從而找出民航旅客社會(huì)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。

2.1邊權(quán)值的意義

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

相異性網(wǎng)絡(luò)：dij=wik+wkj

(1)

(2)

由相異性和相似性網(wǎng)絡(luò)中兩節(jié)點(diǎn)間的距離公式，可以看出兩節(jié)點(diǎn)間最短路徑的意義是不變的，即上述距離公式表示兩節(jié)點(diǎn)間的最優(yōu)連通路徑，這為利用Floyd算法計(jì)算節(jié)點(diǎn)間最短路徑奠定了基礎(chǔ)。顯然，民航旅客社會(huì)網(wǎng)絡(luò)應(yīng)該是屬于相似性網(wǎng)絡(luò)，所以在求節(jié)點(diǎn)間最短路徑時(shí)，不作特殊說(shuō)明的都是使用式(2)為基礎(chǔ)計(jì)算的。

2.2節(jié)點(diǎn)綜合測(cè)度算法

節(jié)點(diǎn)綜合測(cè)度算法，主要基于節(jié)點(diǎn)刪除思想，這種算法在節(jié)點(diǎn)刪除后會(huì)對(duì)連通分支產(chǎn)生較大影響，主要分為兩種損失，即直接損失和間接損失[11]。

直接損失(DLOS)：被刪除節(jié)點(diǎn)無(wú)法連接其它節(jié)點(diǎn)所造成的路徑損失，計(jì)算公式如下：

(3)

間接損失(ILOS)：節(jié)點(diǎn)刪除造成其它節(jié)點(diǎn)不能相互連通所導(dǎo)致的路徑損失，計(jì)算公式如下：

(4)

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

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

(5)

利用TLOS的計(jì)算公式，可以對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行重要度排序。

2.3等效點(diǎn)權(quán)值算法

等效點(diǎn)權(quán)值算法主要考慮度，點(diǎn)權(quán)，接近度，鄰近節(jié)點(diǎn)，距離等復(fù)雜網(wǎng)絡(luò)的評(píng)價(jià)指標(biāo)對(duì)節(jié)點(diǎn)重要性的影響[12-14]，這種影響分為點(diǎn)權(quán)影響和附加點(diǎn)權(quán)影響。

點(diǎn)權(quán)：在社會(huì)網(wǎng)絡(luò)中，點(diǎn)權(quán)具有非常重要的意義，它是與節(jié)點(diǎn)相關(guān)聯(lián)的所有邊的權(quán)值和：

(6)

其中ηi為節(jié)點(diǎn)i鄰域內(nèi)邊的集合。

附加點(diǎn)權(quán)：考慮度，鄰近節(jié)點(diǎn)，距離因素等指標(biāo)：

(7)

由此給出節(jié)點(diǎn)i的等效點(diǎn)權(quán)：

(8)

綜上所述，節(jié)點(diǎn)本身點(diǎn)權(quán)以及網(wǎng)絡(luò)中所有其他點(diǎn)權(quán)對(duì)等效點(diǎn)權(quán)的影響較大，距離中心節(jié)點(diǎn)越近，對(duì)中心節(jié)點(diǎn)的等效點(diǎn)權(quán)貢獻(xiàn)值就越大。在評(píng)價(jià)節(jié)點(diǎn)重要性時(shí)，節(jié)點(diǎn)等效點(diǎn)權(quán)越大，節(jié)點(diǎn)就越重要。

2.4基于相似度貢獻(xiàn)的節(jié)點(diǎn)重要性算法

該算法是在Pagerank算法的基礎(chǔ)上進(jìn)行了優(yōu)化。Pagerank算法以網(wǎng)頁(yè)為信息處理單元,把每一個(gè)網(wǎng)頁(yè)抽象為Web結(jié)構(gòu)圖上的一個(gè)節(jié)點(diǎn),對(duì)每一個(gè)網(wǎng)頁(yè)節(jié)點(diǎn)計(jì)算其對(duì)應(yīng)的Pagerank值,然后根據(jù)其值的大小排序，并找到重要的網(wǎng)頁(yè)節(jié)點(diǎn)[15]。Pagerank的計(jì)算公式如下：

(9)

Pagerank算法的缺點(diǎn)是對(duì)于一個(gè)節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)給予了相同的轉(zhuǎn)移概率，相應(yīng)的優(yōu)化方法是根據(jù)節(jié)點(diǎn)間的相似度大小來(lái)確定節(jié)點(diǎn)之間的轉(zhuǎn)移概率。所以提出了基于相似度貢獻(xiàn)的節(jié)點(diǎn)重要性算法，算法的核心思想是利用節(jié)點(diǎn)的NodeRank值來(lái)衡量節(jié)點(diǎn)的重要性[16]，算法過(guò)程如圖1所示。

圖1　基于相似度貢獻(xiàn)的節(jié)點(diǎn)重要性算法流程

以下是算法的幾個(gè)關(guān)鍵步驟。

(1) 構(gòu)造節(jié)點(diǎn)相似性矩陣

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

(10)

矩陣表示為：

S=φAS+φE

(11)

可變?yōu)椋?/p>

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

(12)

(2) 構(gòu)造概率轉(zhuǎn)移矩陣

將節(jié)點(diǎn)相似度矩陣S歸一化，可以求得初始的概率轉(zhuǎn)移矩陣Mtran如下：

(13)

(3) 計(jì)算節(jié)點(diǎn)的中心度值

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

(14)

2.5利用F-度量確定重要節(jié)點(diǎn)

由于以上三個(gè)算法是從三個(gè)不同角度來(lái)衡量節(jié)點(diǎn)的重要性的，所以所求的結(jié)果會(huì)有一定的差異性，為了更形象地比較由三個(gè)算法分別得到的重要節(jié)點(diǎn)的可靠性，采用結(jié)果相似性比較函數(shù)F(r)來(lái)度量?jī)蓚€(gè)不同排序結(jié)果間的相似度[18]，取相似度較高的一組作為網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。

F(r) 的定義如下：

(15)

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

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

3.1實(shí)驗(yàn)數(shù)據(jù)及可視化分析

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

圖2　民航旅客社會(huì)網(wǎng)絡(luò)的構(gòu)建圖

對(duì)于上述的網(wǎng)絡(luò)進(jìn)行分析，由圖3中的平均路徑長(zhǎng)度分布，以及圖4中的平均聚類系數(shù)分布，計(jì)算得出，其網(wǎng)絡(luò)的基本屬性值如表3所示。

表3　民航旅客社會(huì)網(wǎng)絡(luò)的有關(guān)參數(shù)值

圖3　平均路徑長(zhǎng)度分布

圖4　平均聚類系數(shù)分布

從表3中可以看出網(wǎng)絡(luò)中的平均聚類系數(shù)為0.716，平均路徑長(zhǎng)度為3.213，說(shuō)明民航旅客社會(huì)網(wǎng)絡(luò)符合社會(huì)網(wǎng)絡(luò)聚類系數(shù)高，平均路徑長(zhǎng)度短的小世界性。

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

把上述三種計(jì)算重要節(jié)點(diǎn)的算法應(yīng)用到3.1節(jié)中得到的民航旅客社會(huì)網(wǎng)絡(luò)中，可以得到這156個(gè)節(jié)點(diǎn)的重要性排序結(jié)果，如表4所示(取每種算法排序結(jié)果的前10名)。

表4　三種算法的排序結(jié)果

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

表5　基于F-度量方法的結(jié)果相似度對(duì)比圖

其中1代表等效點(diǎn)權(quán)值算法，2代表節(jié)點(diǎn)綜合測(cè)度算法，3代表基于相似度貢獻(xiàn)的節(jié)點(diǎn)重要性評(píng)估算法。

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

表6　民航旅客社會(huì)網(wǎng)絡(luò)的前五名重要節(jié)點(diǎn)

3.3結(jié)果分析

實(shí)驗(yàn)分別從節(jié)點(diǎn)度、點(diǎn)權(quán)、二重度、二重點(diǎn)權(quán)以及實(shí)際數(shù)據(jù)庫(kù)中節(jié)點(diǎn)1月份出行情況兩個(gè)方面，對(duì)排序結(jié)果進(jìn)行了可靠性分析，排序結(jié)果見(jiàn)表7所示。

表7　節(jié)點(diǎn)度，點(diǎn)權(quán)，二重度，二重點(diǎn)權(quán)的排序結(jié)果

其中，度是指與該節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)的個(gè)數(shù)；點(diǎn)權(quán)是指與該節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)的權(quán)重之和；二重度是指與節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)的度之和；二重點(diǎn)權(quán)是指與節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)的點(diǎn)權(quán)之和。

從表7可以看出：分別按節(jié)點(diǎn)度、點(diǎn)權(quán)、二重度、二重點(diǎn)權(quán)排序的結(jié)果的前五名也正好是3.2節(jié)中所求的五個(gè)重要節(jié)點(diǎn)。因此，進(jìn)一步地說(shuō)明了最后所求出的重要節(jié)點(diǎn)是準(zhǔn)確的。

4結(jié)語(yǔ)

本文主要從民航旅客社會(huì)網(wǎng)絡(luò)的構(gòu)建以及重要節(jié)點(diǎn)發(fā)現(xiàn)算法在民航旅客社會(huì)網(wǎng)絡(luò)的應(yīng)用方面展開(kāi)研究，通過(guò)挖掘PNR數(shù)據(jù)間的內(nèi)在關(guān)系，進(jìn)一步推測(cè)出民航旅客間的關(guān)系以及這種關(guān)系的強(qiáng)弱，從而構(gòu)建出民航旅客社會(huì)網(wǎng)絡(luò)。在此基礎(chǔ)上分析了多種社會(huì)網(wǎng)絡(luò)重要節(jié)點(diǎn)發(fā)現(xiàn)算法，并進(jìn)一步地把這些算法應(yīng)用在了民航旅客社會(huì)網(wǎng)絡(luò)中，最后通過(guò)F-度量方法對(duì)結(jié)果進(jìn)行了相似性比較，確定出重要的民航旅客。實(shí)驗(yàn)結(jié)果證明，本次研究為民航旅客社會(huì)網(wǎng)絡(luò)分析與挖掘提供了社會(huì)網(wǎng)絡(luò)類型的數(shù)據(jù)支持，并更加全面準(zhǔn)確地分析了民航旅客，為提高航空公司效益，改善民航旅客服務(wù)提供了有力依據(jù)。

參考文獻(xiàn)

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

[2] 馮霞,李勇,陳卉敏.民航旅客社會(huì)網(wǎng)絡(luò)構(gòu)建方法研究[J].計(jì)算機(jī)仿真,2013,30(6):51-54.

[3] 馮霞,陳卉敏,李勇.一種結(jié)合SVD的SNMF復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].信息與控制,2013,42(3):387-391.

[4] 潘玲玲.基于旅客行為的航空旅客細(xì)分模型研究及其實(shí)現(xiàn)[D].南京:南京航空航天大學(xué),2012.

[5] 羅利,彭際華.競(jìng)爭(zhēng)環(huán)境下的民航客運(yùn)收益管理動(dòng)態(tài)定價(jià)模型[J].系統(tǒng)工程理論與實(shí)踐,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] 楊育彬,李寧,張瑤.基于社會(huì)網(wǎng)絡(luò)可視化分析的數(shù)據(jù)挖掘[J].軟件學(xué)報(bào),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] 喬少杰,唐常杰,彭京,等.基于個(gè)性特征仿真郵件分析系統(tǒng)挖掘犯罪網(wǎng)絡(luò)核心[J].計(jì)算機(jī)學(xué)報(bào),2008,31(10):1795-1803.

[12] 王昊翔,曾珊,劉揮揚(yáng).虛擬社交網(wǎng)絡(luò)中節(jié)點(diǎn)重要度分析[J].上海交通大學(xué)學(xué)報(bào),2013,47(7):1055-1059.

[13] 王喆.基于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究[D].吉林:吉林大學(xué),2013.

[14] 司曉靜.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究[D].西安:西安電子科技大學(xué),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.

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

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

收稿日期：2014-07-22。國(guó)家自然科學(xué)基金項(xiàng)目(60879015)；中國(guó)民航局科研基金項(xiàng)目(MHRD201130)。曹衛(wèi)東，副教授，主研領(lǐng)域：數(shù)據(jù)庫(kù)與數(shù)據(jù)挖掘。白亮，碩士生。劉紅霞，碩士生。