Social networks provide a new perspective for enterprises to better understand their customers and have attracted substantial attention in industry. However, inferring high quality customer social networks is a great challenge while there are no explicit customer relations in many traditional OLTP environments. In this paper, we study this issue in the field of passenger transport and introduce a new member to the family of social networks, which is named Co-Travel Networks, consisting of passengers connected by their co-travel behaviors. We propose a novel method to infer high quality co-travel networks of civil aviation passengers from their co-booking behaviors derived from the PNRs (Passenger Naming Records). In our method, to accurately evaluate the strength of ties, we present a measure of Co-Journey Times to count the co-travel times of complete journeys between passengers. We infer a high quality co-travel network based on a large encrypted PNR dataset and conduct a series of network analyses on it. The experimental results show the effectiveness of our inferring method, as well as some special characteristics of co-travel networks, such as the sparsity and high aggregation, compared with other kinds of social networks. It can be expected that such co-travel networks will greatly help the industry to better understand their passengers so as to improve their services. More importantly, we contribute a special kind of social networks with high strength of ties generated from very close and high cost travel behaviors, for further scientific researches on human travel behaviors, group travel patterns, high-end travel market evolution, etc., from the perspective of social networks.