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' direct route service on the U.S. domestic market. 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 substantial topology transitions. We also propose a simple new 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 a number of implications for the way in which subgraphs can be used to analyze real-world networks. Although most of the literature on motifs focuses on natural networks, we have found one interesting study by Gergana Bounova ("Topological evolution of networks: Case studies in the US airlines and language Wikipedias", PhD thesis, Massachusetts Institute of Technology, 2009) that, like us, investigates topology transitions in U.S. airline route maps.
