Comparing Multilevel Clustering Methods on Weighted Graphs: The Case of Worldwide Air Passenger Traffic 2000–2004 - Methods for Multilevel Analysis and Visualisation of Geographical Networks - page 135

Chapter 9
Comparing Multilevel Clustering Methods
on Weighted Graphs: The Case of Worldwide
Air Passenger Traffic 2000-2004

Céline Rozenblat, Guy Melançon, Romain Bourqui, and David Auber

9.1 Introduction

Worldwide deregulation of air transport began in 1978 and came to fruition in
2008, and the re-organization of flows and companies since 1978 is one of the
main subjects of air transport network studies. Hubs and spokes are re-shaping the
entire network in national and multinational contexts and shrinking international
and national links. Thus, each city with specific activities, such as business, research
or tourism, develops its own strategies to maximize accessibility from the relative
position with the goal of strengthening its economic base. Diagnostics for cities
increase the need to study the properties and dynamics of cities, which can be
considered nodes in the entire network of flows.
The study of air traffic networks involves large flow matrices. A useful approach
to understanding the structure of networks and the evolution of this structure is
to search for the highest subgroup densities in a graph, assuming that the graph
is neither random nor homogeneous (Barabasi & Albers, 1998; Watts & Strogatz ,
1998 ). Then, clusters of the most connected city airports encapsulate the entire
network structure underlying highly inter-connected groups of cities. Different
approaches from this perspective were recently developed by physicists ( Brandes ,
2001 ; Newman , 2004 ; Newman & Girvan , 2004 ). In air transportation in particular,
air traffic networks have been used by different network clustering methodologies
as a case study ( Guimerà, Mossa, Turtschi, & Amaral , 2005 ; Sales-Pardo et al. ,