Modularity maximization and tree clustering: Novel ways to determine effective geographic borders

Daniel Grady, Rafael Brune, Christian Thiemann, Fabian J. Theis, Dirk BrockmannarXiv 2011 · OpenReview

TL;DR

This paper introduces novel methods for identifying "effective" geographic borders by analyzing human mobility patterns, specifically using the circulation of US dollar bills as a proxy. By applying community detection algorithms to a network of inter-county bill movements, they uncover border structures that are more reflective of actual human interaction than arbitrary administrative lines, demonstrating that these mobility-driven borders are robust and meaningful.

What Problem Does This Paper Address?

Existing administrative and political borders are often historical artifacts, determined by past circumstances rather than current societal dynamics. As human mobility and communication have become increasingly complex and long-distance, these traditional borders may no longer accurately represent the functional divisions of society. The authors aim to address this by using human mobility data to discover "effective" geographic borders that reflect how people actually interact and move across space, rather than relying on arbitrary or outdated divisions. This is crucial for understanding phenomena like the spread of information, trade, and even disease.

Methods

The paper employs two primary methods for identifying community structures and, by extension, geographic borders:

  1. Modularity Maximization: This is a standard network analysis technique used to find partitions of a network into communities. The authors use a stochastic simulated annealing algorithm to search for partitions that maximize a "modularity" score, which indicates how well-connected nodes are within their communities compared to connections between communities. They generate an ensemble of high-modularity partitions to overcome issues like degeneracy and the resolution limit.
  2. Shortest-Path Tree (SPT) Clustering: This is a novel approach developed by the authors. It involves computing shortest-path trees for each node in the network, then measuring the dissimilarity between these trees. Hierarchical clustering is applied to these dissimilarity scores to identify community structures and borders. This method is highlighted for its uniqueness and its ability to identify a network backbone that strongly correlates with observed borders.

Datasets

The primary dataset used is the "Where's George?" (WG) bank note circulation data. This dataset tracks the movement of individual US dollar bills across counties in the continental United States. The authors use a subset of over 11 million bills that were reported at least twice, creating a network where nodes are counties and edge weights represent the number of bills exchanged between them.

Key Insights and Ideas

  • Human mobility reveals functional borders: The core idea is that the flow of money (or people) between locations creates a network that implicitly defines meaningful geographic divisions, which can be more relevant than administrative borders.
  • Modularity maximization can be sensitive: While powerful, modularity maximization can suffer from degeneracy (multiple partitions with the same optimal score) and resolution limits (difficulty detecting small communities). The authors address this by using an ensemble of partitions.
  • SPT clustering offers a unique perspective: This method provides a topologically unique set of borders and a network backbone, offering a complementary approach to modularity.
  • Effective borders are spatially coherent: Despite the long-range nature of some mobility, the detected communities and their borders tend to be spatially compact, often centered around major metropolitan areas.
  • Existing borders are not always optimal: The study shows that a significant portion of administrative borders do not align with these mobility-driven effective borders, suggesting that current divisions are not always the most logical.

Key Results

  • The authors successfully identified a set of "effective" geographic borders from the bank note circulation data using both modularity maximization and SPT clustering.
  • These mobility-induced borders are robust to data removal (even with 95% of flux removed, the structure remains largely intact).
  • The effective borders are often spatially coherent and centered around large metropolitan hubs.
  • A significant portion (64%) of the identified effective borders do not coincide with existing state borders, while 44% of state borders do align with these new divisions.
  • The gravity model, a common null model for spatial interactions, fails to reproduce the sharp definition and spatial coherence of the borders found in the real mobility data.

Limitations and Future Work

  • Data limitations: The "Where's George?" data is a proxy for human mobility and may not capture all aspects of movement. The authors acknowledge potential biases from initial bill entries and the fact that the data is based on voluntary reporting.
  • Degeneracy and resolution limit: While addressed by using an ensemble of partitions, these are inherent challenges in community detection that can still influence results.
  • Future work: The authors suggest further investigation into the structural stability of observed patterns and the development of more efficient computational techniques. They also aim to compare their findings with other types of mobility data and explore the implications of these effective borders for various social and economic phenomena.

Summary updated

Abstract

Territorial subdivisions and geographic borders are essential for understanding phenomena in sociology, political science, history, and economics. They influence the interregional flow of information and cross-border trade and affect the diffusion of innovation and technology. However, most existing administrative borders were determined by a variety of historic and political circumstances along with some degree of arbitrariness. Societies have changed drastically, and it is doubtful that currently existing borders reflect the most logical divisions. Fortunately, at this point in history we are in a position to actually measure some aspects of the geographic structure of society through human mobility. Large-scale transportation systems such as trains and airlines provide data about the number of people traveling between geographic locations, and many promising human mobility proxies are being discovered, such as cell phones, bank notes, and various online social networks. In this chapter we apply two optimization techniques to a human mobility proxy (bank note circulation) to investigate the effective geographic borders that emerge from a direct analysis of human mobility.
BibTeX
@misc{grady2011modularity,
  author = {Daniel Grady and Rafael Brune and Christian Thiemann and Fabian J. Theis and Dirk Brockmann},
  title = {{Modularity maximization and tree clustering: Novel ways to determine effective geographic borders}},
  year = {2011},
  eprint = {1104.1200},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.1200},
}
Figure