Title: Topological Evolution of Networks: Case Studies in the US Airlines and Language Wikipedias Speaker: Gergana Bounova, Massachusetts Institute of Technology Date/Time: Wednesday, February 11, 2009 – 9:00 AM Location: CSRI Building, Room 90 (Sandia NM) to 915/S101 Brief Abstract: Our research examines the topology of engineering systems and how the topology changes over time. Topology refers to the relative arrangements and connectedness of the elements of a system. We review network theory relevant to topological evolution and use graph-theoretical methods to analyze real systems. We combine existing canonical topology generative models and develop tools for comparing real networks to a canonical profile. The developed metrics are used to track topology changes over the history of real systems. This theoretical work is applied to two case studies. The first discusses the US airline industry from a route networks point of view. We study various airlines and segments of the industry statistically and find commonly occurring patterns. We show that there are topology transitions in the history of airlines in the period 1990-2007. Most airline networks have similar topology and historical patterns, with the exception of Southwest Airlines. We show mathematically that Southwest’s topology is different. We propose two heuristic growth models, one featuring hub-seeding derived from the underlying patterns of evolution of JetBlue Airways and one featuring local interconnectedness, derived from the patterns of growth of Southwest. We show that the two models match the topologies of these airlines better than canonical models over time. Results suggest that Southwest is becoming more centralized, closer to the hub-spoke topologies of other airlines. Our second case study discusses the growth of language Wikipedia networks, where nodes are the articles and hyperlinks are the connections between them. These knowledge networks are subject to different constraints than air transportation systems. We find that the topology of these networks and their principles of growth are completely different. Most Wikipedias studied grow by coalescence, with multiple disconnected thematic clusters of pages growing separately and over time, converging to a giant connected component via weak links. These topologies start out as simple trees, and coalesce into fairly sparse hierarchical structures with random interlinking. One striking exception is the history of the Chinese Wikipedia which grows fully connected from its inception. We discuss these patterns of growth comparatively across Wikipedias, and overall, with insights into the distinct principles of growth compared with airline networks. Our work suggests that complex engineering system topologies are hybrids of pure canonical forms and that they undergo distinct phase transitions during their evolution. We find some commonality among systems and uncover important differences by learning from the exceptions.CSRI POC: Scott Collis, (505) 284-1123 |