Urn Modeling of Random Graphs Across Granularity Scales: A Framework for Origin-Destination Human Mobility Networks

Fabio Vanni, David Lambert · 2025

Read Urn Modeling of Random Graphs Across Granularity Scales: A Framework for Origin-Destination Human Mobility Networks by Fabio Vanni, David Lambert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18544.txt.

Introduction

Fabio Vanni and David Lambert model city trips as balls tossed into bins, in a study from 2025. Each trip is a ball; each place is a bin. From that plain game, the pair build origin-destination networks, the maps of who goes from where to where that planners live by.

Their frame spans three scales, from exact counts to smooth graph forms. A core proof shows the three meet in one mixed law when the net is vast and sparse. Neat forms then give the odds a place is hit, left blank, or over-full, plus the time to cover a set of sites. Sims with pull-like draw rules, fit to real trip data, matched the math. Planners gain a kit for fake nets and crush checks.

Catalog record

CREATORFabio Vanni, David Lambert
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18544

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Urn Modeling of Random Graphs Across Granularity Scales: A Framework for Origin-Destination Human Mobility Networks Fabio Vanni, David Lambert Abstract We model human mobility as a combinatorial allocation process, treating trips as distinguishable balls assigned to location-bins and generating origin–destination (OD) networks. From this analogy, we construct a unified three-scale framework, enumerative, probabilistic, and continuum graphon ensembles, and prove a renormalization theorem showing that, in the large sparse regime, these representations converge to a universal mixed-Poisson law. The framework yields compact formulas for key mobility observables, including destination occupancy, vacancy of unvisited sites, coverage (a stopping-time extension of the coupon collector problem), and overflow beyond finite capacities. Simulations with gravity-like kernels, calibrated on empirical OD data, closely match the asymptotic predictions. By connecting exact combinatorial models with continuum analysis, the results offer a principled toolkit for synthetic network generation, congestion assessment, and the design of sustainable urban mobility policies. PACS 89.75.-k , 05.40.-a , 89.65.Lm 2020 MSC 05C80 , 60C05 , 90B20 , 91D10 1 Introduction Human mobility, the movement of people and goods across space, shapes urban form, economic activity, and social interaction. Origin-destination (OD) models are a core tool for analyzing these flows, linking origins (e.g., homes, firms) to destinations (e.g., workplaces, markets) through directed connections that represent commuting, migration, trade, and related interactions [ 1 , 2 , 3 ] . Rooted in geography, economics, statistical physics, and applied mathematics, OD systems are naturally represented as directed graphs, where nodes are administrative units and edges quantify flow intensities [ 4 , 5 , 6 ] , integrating spatial interaction and location theory [ 7 , 8 ] . We model OD networks via a formal analogy with combinatorial allocation problems, specifically balls-into-bins, in the spirit of [ 9 , 10 ] . In this view, the OD mobility network is characterized by directed flows of individuals between locations [ 11 , 12 ] , represented as nodes. The flows (balls) have origins (types or colors of balls) and destinations (bins), creating a complex, directed network of mobility patterns. By leveraging this analogy, we can derive insights into the distribution of flows, congestion effects, and optimization strategies. In particular, we introduce a three-level granularity framework for random graphs, based on a systematic coarsening process that combines statistical relaxation [ 13 , 14 , 15 ] and structural aggregation [ 16 , 17 ] . Statistical relaxation replaces exact link allocations (fine-grained representation) with probabilistic ones (coarse-grain representation), moving from enumerative graph configurations to random ensembles that match expected link patterns. Structural aggregation groups nodes according to latent characteristics (namely attractiveness such as location or socio-economic attributes), reducing the network’s dimensionality while preserving key structural heterogeneity by using the inhomogeneous random graph configurations which is a class of random graphs with latent variables, reformulated using urn modeling methods and stochastic occupancy equations in a continuous setting (continuum-grained representation). This procedure defines three renormalized ensembles, each representing the system at a different resolution. As granularity decreases, these ensembles preserve the key large-scale statistics of the original network while filtering microscopic variability, revealing persistent topological structure across scales. At the fine-grained level, the system is described by a fully specified link allocation, where the randomness reflects combinatorial uncertainty over admissible configurations under exact structural constraints. At the fine-grained level, we solve occupancy and load problems using exact combinatorial enumeration, refined with asymptotic approximations. In contrast, the coarse-grained representation relaxes these constraints and models the network probabilistically, interpreting connection tendencies as the result of partial information or latent structural preferences. At the coarse-grained level, we reformulate the problem in terms of cumulants and apply the saddle-point approximation to the moment-generating function. While the two approaches differ in their treatment of uncertainty, they become statistically consistent under appropriate large-scale and sparse conditions via a mean-field argument (self-averaging limit). Both frameworks yield a discrete representation of the system, making them well-suited for generating synthetic networks and producing numerical Monte Carlo results. On the other side, at the continuum-grained level, the system is described through a class of random graphs with latent variables, where the discrete set of nodes is replaced by a continuous domain endowed with a probability density. Each node is characterized by a latent variable, and the connection or allocation process is governed by a kernel function acting on these latent traits. We evaluate macroscopic observables with integral transforms and the Laplace method. Here, the large-deviation principle for the graphon (adjacency-matrix density) provides the variational rate functional that makes the continuum approach fully consistent with the discrete ones. The principal motivation for introducing this continuum formulation is to provide a general framework in which analytical expressions for typical urn problems, such as occupancy and other load-allocation problems, can be rigorously derived. In this setting, key probabilistic quantities admit tractable integral representations in the large-system limit, enabling closed-form approximations that complement and extend the discrete Monte Carlo simulations produced by the fine- and coarse-grained ensembles. Section 2 develops the mathematical foundations of these three urn-based ensembles. We formalize the fine-, coarse-, and continuum-grained representations of random pseudo-graphs and prove their asymptotic equivalence in the large, sparse regime (Theorems 1 and 2 ). Under these conditions, the coarse-grained conditioned product of binomials ensemble, the fine-grained multivariate hypergeometric ensemble, and the exponential graphon (under fixed mass) describe the same limiting distribution. In Section 3 , we derive analytical expressions for the occupancy problem at all three scales. In mobility terms, this is the allocation of visits across locations; in graph terms, it is the OD network degree distribution. Specifically, it describes the expected number of location-bins containing a given number of visit-balls. We will show that, across all three granularity scales, this problem is asymptotically equivalent to a pure multinomial balls-into-bins setting. Furthermore, under suitable mean-field assumptions, the degree (visit) distribution converges to a mixed Poisson law, extending classical Poissonization results [ 18 , 19 ] . Section 4 addresses allocation-load phenomena, i.e. vacancy, coverage, and overflow, consistently across the three scales. Vacancy counts locations left unvisited after a given number of trips, indicating underutilization and access inequities. Coverage adopts a stopping-time perspective, the number of trips required until exactly a target number of locations remain unvisited, generalizing the coupon collector problem. Last, overflow quantifies allocations exceeding finite capacities, providing an indicator of congestion and stress at destinations (e.g., stations, hospitals, roads). These metrics offer a compact, tractable basis for diagnosing crowding, queuing, and systemic strain, and for evaluating policies such as demand redistribution or capacity expansion. Finally, in Section 5 , we validate our results using parameterization and functional forms from the data-driven case study [ 12 ] . This gravity-like specification aligns with standard gravity models [ 20 , 21 , 22 ] and with recent AI-driven approaches [ 23 , 24 ] that identify gravity-type OD laws as interpretable, parsimonious fits to mobility data. We then generate fine- and coarse-grained networks via Monte Carlo simulation (using purpose-built code) and compare their estimates and plots with continuum-grained asymptotic analytical predictions; the excellent agreement across scales, therefore, corroborates our findings on occupancy and load-allocation (vacancy, coverage, overflow). The paper closes with a discussion of potential applications and outlines how the framework could be extended

Read the complete text