Co-travel Subgraph Extraction Based On Passenger-flight Heterogeneous Network

The task of extracting co-travel subgraphs from passenger-flight heterogeneous network is to group passengers with high relationships into the same subgraph.The intra-connections among passengers in the subgraph are compact and vice versa.On one hand,passengers co-travel subgraph would help airlines provide personalized services.On the other hand,that subgraph would be utilized to improve the airport safety by monitor dangerous passengers and their counterparts.Since individuals have few travel records but the total records are in large scale,the connection among passengers are highly sparse.Nevertheless,the existing subgraph extraction algorithms usually handle networks with tight relationships so that they would perform poorly on passenger-flight heterogeneous network with sparse connections.To address this issue,the manuscript proposed two methods to extracting co-travel subgraphs.The main work of the paper is as follows:To overcome the passenger-flight heterogeneous network with few connections,an approach extracting co-travel subgraphs based on random walks is proposed.That approach firstly constructs a passenger-flight heterogeneous network from huge volume of passenger name records,one of which is a flight ticket information.After that,the random walk method is employed to update similarities among network nodes.Finally,a label propagation algorithm based on complete subgraphs is designed to extract co-travel subgraphs.Experimental results on the passenger name records demonstrate that the proposed method outperforms the baselines in terms of modularity,normalized mutual information and precision.That baselines are label propagation algorithm,overlapping communication discovery algorithm based on label propagation and cluster percolation method.As the random walks could not handle the dependence among nodes with multi-hops,an algorithm extracting co-travel subgraphs based on network representation learning is designed.That method employs Node2 vec to embed nodes into dense vectors.Consequently,node similarity is reconstructed by computing the cosine distance on their embedding.After that,label propagation algorithm would be still used to mine co-travel subgraphs.Experimental results that performance improvements of the proposed method over the baselines are respectively 43.2% and 3.84% in terms of modularity and accuracy.