Title: Subgraphs and motifs in a dynamic airline network,
Abstract: How does the small-scale topological structure of an airline network behave
as the network evolves? To address this question, we study the dynamic and
spatial properties of small undirected subgraphs using 15 years of data on
Southwest Airlines' domestic route service. We find that this real-world
network has much in common with random graphs, and describe a possible
power-law scaling between subgraph counts and the number of edges in the
network, that appears to be quite robust to changes in network density and
size. We use analytic formulae to identify statistically over- and
under-represented subgraphs, known as motifs and anti-motifs, and discover the
existence of substantial topology transitions. We propose a simple
subgraph-based node ranking measure, that is not always highly correlated with
standard node centrality, and can identify important nodes relative to specific
topologies, and investigate the spatial "distribution" of the triangle subgraph
using graphical tools. Our results have implications for the way in which
subgraphs can be used to analyze real-world networks.