曹卫东　白　亮　刘红霞

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)。曹卫东，副教授，主研领域：数据库与数据挖掘。白亮，硕士生。刘红霞，硕士生。