Partitioning of urban networks for MFD applications
S. F. A. Batistaa,∗ , D.M. Bramicha , J. Balsa-Barreiroa and Mónica Menéndezaa Division of Engineering, New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

sergio.batista@nyu.edu∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 18, 2022
Keywords: Network partitioning; Gaussian Mixture models; Nested sampling; Urban networks;
Aggregated traffic models.

1INTRODUCTION

Traffic modeling is a useful tool for developing policies aimed at mitigating congestion problems
that many cities face worldwide. Aggregated traffic models based on the Macroscopic Fundamental Diagram (MFD) (Geroliminis & Daganzo, 2008) present promising prospects in this direction.
The application of these models requires the partitioning of urban networks, represented as asequence of directed links, into a set of connected regions where all vehicles travel at similar
average speeds. The MFD encapsulates the relationship between the average travel speed andthe accumulation of vehicles in each region during a given time interval. MFD-based models
mimic the dynamics as exchange flows between adjacent regions.
An important question is how to best partition urban networks into regional networks. On
one hand, the partitioned regions should have reasonable sizes (i.e. it is undesirable to havea region with 10 intersections next to one with 1000 intersections), and be topologically fully
connected, compact and well separated (i.e. non overlapping regions). On the other hand,traffic conditions within each region should be approximately homogeneous (i.e. congestionshould be approximately homogeneous over the region). Several authors have discussed different
methodologies for partitioning urban networks for MFD applications. Ji & Geroliminis (2012)were the first to implement a Normalized Cut algorithm to partition urban networks for MFD
models. Saeedmanesh & Geroliminis (2016) proposed a model based on the “snake’s similarity”.
The model starts with a single road, and then iteratively adds roads with close similarity values
to the “snake”. Then, Symmetric Non-negative Matrix Factorization is used for partitioning theurban network. This method ensures fully connected regions, but not necessarily regions thatare compact and well separated. Lopez et al. (2017) showed that the K-means algorithm resultsin lower within-cluster variances than the Normalized Cut and DBSCAN methods to partition
urban networks, therefore offering better performance in comparison with the two previouslyintroduced methods. Casadei et al. (2018) proposed a spatiotemporal algorithm that ensuresthe consistency of travel times between the urban and regional networks. Ambühl et al. (2019)used real traffic data. They did the partition using random walks along the urban network
selecting the one that minimizes the scatter on estimating the regions’ MFDs. While some ofthese approaches ensure fully connected regions, they fail in most cases to deliver regions ofreasonable sizes, compact and not overlapping.
TRISTAN XI Symposium

Original abstract submittal

Batista et al.

2

Recently, Batista et al. (2021) utilized Gaussian Mixture Models (GMMs) to partition urban
networks by clustering a data set consisting of the Cartesian coordinates of the nodes. GMMs
assume that the underlying density distribution of the data can be modeled as a (convex) linear
combination of K Gaussian components. In this application of GMMs, each Gaussian component represents a network region. As part of the clustering problem, the optimal number ofcomponents K (i.e. regions) needs to be determined. The authors applied the GMMs in twosteps to partition the whole metropolitan area of Munich (Germany). First, the authors fit theirdata with multiple different GMMs covering all possible values of K between 1 and 200. Theauthors then computed the Akaike information criterion (AIC) and the Bayesian information
criterion (BIC) for each fit, and selected the value of K so as to minimize either the AIC orBIC. The final partitioning was determined by the GMM fit for the selected value of K. Thispartitioning approach enables the extraction of regions that respect the appropriate topologicalfeatures (i.e. in terms of size, compactness, connectivity, and separability) for the MFD applications. However, we have since found that this methodology for selecting the optimal K is
confounded by the many symmetries in the likelihood function because of the unidentifiabilityof the model components (e.g. the “label switching problem” is one type of unidentifiability).
Specifically, the regularity conditions that validate the AIC and BIC approximations do not holdfor GMMs as they require the model components/parameters to be identifiable (see Chapter 7 in
Frühwirth-Schnatter et al. (2018)), which explains why Batista et al. (2021) found that neither
the AIC or BIC achieve a global minimum for a reasonable range of K. This paper proposes analternative methodology that performs model selection by computing the Bayesian evidence foreach value of K, and selects the K that yields the greatest evidence. This naturally penalises
models with more components (and parameters). We also present some preliminary results fromapplying the proposed methodology to partition the network of Innsbruck (Austria).

2METHODOLOGICAL FRAMEWORK

GMMs fall into the class of unsupervised machine learning models, that can also be used forclustering data. Let us denote our data set of N pairs of Cartesian coordinates, with one pair foreach node in the urban network, as D ≡ {(xj , yj )}j=N
j=1 . Next, for a GMM MK with K components, let fk (x, y) represent the (density of the) k-th Gaussian component with parameter vector
θk . Then the probability density function (PDF) of a bivariate random variable G distributed
as MK can be written as:
fG (x, y) =KX

ϕk fk (x, y)

(1)

k=1

where ϕk is the weight for the kth component. The weights must satisfy ϕk ≥ 0 for all
Pk, and K
k=1 ϕk = 1. We gather the full set of parameters for MK into the single vector
ΘK = (ϕ1 , ..., ϕK , θ1 , ..., θK ).
Assuming that the data D are all independently drawn from the PDF of G, then the likelihood
function L (ΘK ) can be written as:
P (D | ΘK , MK ) = L (ΘK ) =N X
KY

ϕk fk (xj , yj )(2)

j=1 k=1

Via Bayes Theorem, the posterior distribution of ΘK may be computed from:
P (ΘK | D, MK ) =P (D | ΘK , MK ) P (ΘK | MK )L (ΘK ) Π (ΘK )=P (D | MK )ZK

(3)

where Π (ΘK ) and ZK are the prior parameter distribution and the Bayesian evidence, respectively. The Bayesian evidence is computed as:
ZK = P (D | MK ) =TRISTAN XI Symposium

ZL (ΘK ) Π (ΘK ) dΘK(4)

Original abstract submittal

Batista et al.

3

Finally, again using Bayes theorem, the posterior probability of model MK from a set of models{M1 , M2 , ..., MQ }, where 1 ≤ K ≤ Q, is given by:
P (MK | D) =P (D | MK ) P (MK )ZK ΨK= PQ
P (D)i=1 Zi Ψi(5)where Ψi = P (Mi ) is the prior probability of the ith model. The optimal value of K thencorresponds to the model that maximises P (MK | D).
The integral in Equation 4 can only be performed numerically, and even then it is very
difficult. Nested Sampling (Speagle, 2020), unlike other Monte Carlo Markov Chain sampling
methods, is able to perform these integrations and compute the ZK .
For this, we need to specify the model fully and adopt appropriate priors on the modelparameters. We model each component of the GMM as a radially symmetric Gaussian profile
with free parameters θk = (xc,k , yc,k , σk ). Since we are not using any prior information to guidethe network partitioning, we adopt non-informative priors on all parameters. For the “location”
parameters xc,k and yc,k , we adopt independent Uniform priors, and for the “scale” parameters
σk , we adopt independent Uniform priors on ln σk . With a similar motivation, we use a flat
Dirichlet prior for the ϕk parameters. We are currently investigating the use of sorted priors forthe ϕk to help remove multi-modality from the posterior (Buscicchio et al., 2019). Finally, weassume a Uniform prior on the Ψi (while we are also investigating an exponential prior on theΨi to further promote sparseness in the selected model).

3PRELIMINARY RESULTS AND DISCUSSION

This section discusses some preliminary results. In particular, we discuss a preliminary validationof the full Bayesian treatment from Section 2 against the GMM fitting method described inBatista et al. (2021). For a low number of components, both approaches should provide consistentestimates of the parameters of the Gaussian components (i.e. weights, locations, and sigmas). For
this purpose, we set K = 5 components and determine the static partition of the urban network
representing the city of Innsbruck (Austria). This network was retrieved from OpenStreetMaps(OpenStreetMap contributors, 2020), and consists of 1992 nodes and 4448 links. Table 1 lists
estimates of the weights, locations, and sigmas of each of the five Gaussian components, for theGMM fitting method described in Batista et al. (2021) and for our proposed Bayesian approach.
Figure 1 shows the Innsbruck network partitioned into the 5 components/regions.
As expected, from Table 1, we can observe that both approaches provide similar estimatesof the region locations (xc,k , yc,k ), showing their consistency. This happens because for a low
number of components of K = 5, we have a multi-modality of 5! = 1201 . This means that westill have a (relatively) low level of complexity in the topology of the log-likelihood surface, andthe Expected-Maximization algorithm used for maximizing the log-likelihood function in the fits
described in Batista et al. (2021) converges, in general, to the global maximum. However, thenumber of local maxima increases with at least K!. This increases the topological complexityof the log-likelihood function, and the Expected-Maximization algorithm gets stuck more often
in sub-optimal solutions. The full Bayesian approach that we propose with Nested Sampling
does not suffer from this limitation, since it explores the full posterior probability surface. Wewill discuss these advantages of our modelling procedure in the full paper. The partitioning inFigure 1 depicts that the subnetwork representing region 4 is not fully connected. In the fullpaper, we will also discuss how geographical features of the network (e.g. the presence of rivers
which can act as natural borders) should be utilized as a first partitioning level before applying
our proposed model. In this step, we can adopt for example priors based on those features (e.g.
geographical features).
1The notation "!" refers to the factorial of 5, i.e. 5! = 5 · 4 · 3 · 2 · 1 = 120.

TRISTAN XI Symposium

Original abstract submittal

Batista et al.

4

Table 1 – Parameter estimates determined for each Gaussian component, using the GMM fitting
method described in Batista et al. (2021) and the full Bayesian treatment.
Region12345GMM (Batista et al., 2021)
ϕkxc,kyc,kσk0.242 683222 5237910 956
0.170 678967 5236958 814
0.335 681464 5237387 969
0.139 685247 5239092 925
0.114 675817 5236282 624

GMM Bayesianxc,kyc,k684005 5238256
679007 5236953
681695 5237427
685728 5239891
675818 5236278

ϕk
0.114
0.179
0.397
0.262
0.049

σk1084
821
988
415
623

6.0

y [km]

4.5

41

3.0

32

1.5

500

3.5

7.0

10.5

14.0

x [km]

Figure 1 – Innsbruck (Austria) city network partitioned into 5 regions.

ACKNOWLEDGEMENTS
The authors acknowledge support by the NYUAD Center for Interacting Urban Networks (CITIES),
funded by Tamkeen under the NYUAD Research Institute Award CG001.

References
Ambühl, L., Loder, A., Zheng, N., Axhausen, K. W., & Menendez, M. 2019. Approximative network
partitioning for MFDs from stationary sensor data. Transportation Research Record.
Batista, Sérgio F. A., Lopez, Clélia, & Menéndez, Mónica. 2021. On the partitioning of urban networks
for MFD-based applications using Gaussian Mixture Models. Pages 1–6 of: 2021 7th International
Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS).
Buscicchio, R., Roebber, E., Goldstein, J.M., & Moore, C.J. 2019. Label switching problem in Bayesiananalysis for gravitational wave astronomy. Physical Review D, 100, 084041.
Casadei, G., Bertrand, V., Gouin, B., & Canudas-de-Wit, C. 2018. Aggregation and travel time calculation over large scale traffic networks: An empiric study on the Grenoble City. Transportation ResearchPart C: Emerging Technologies, 95, 713–730.
Frühwirth-Schnatter, S., Celeux, G., & Robert, C.P. 2018. Handbook of Mixture Analysis. Chapman andHall/CRC.
Geroliminis, N., & Daganzo, C. 2008. Existence of urban-scale macroscopic fundamental diagrams: Someexperimental findings. Transportation Research Part B: Methodological, 42, 759–770.
Ji, Y., & Geroliminis, N. 2012. On the spatial partitioning of urban transportation networks. Transportation Research Part B: Methodological, 46, 1639–1656.
Lopez, C., Leclercq, L., Krishnakumari, P., Chiabaut, N., & van Lint, H. 2017. Revealing the day-to-day
regularity of urban congestion patterns with 3D speed maps. Scientific Reports, 7, 1–11.
OpenStreetMap contributors. 2020. Innsbruck dump retrieved from https://planet.osm.org .
Saeedmanesh, M., & Geroliminis, N. 2016. Clustering of heterogeneous networks with directional flows
based on ”Snake” similarities. Transportation Research Part B: Methodological, 91, 250–269.
Speagle, J.S. 2020. DYNESTY: a dynamic nested sampling package for estimating Bayesian posteriors
and evidences. MNRAS, 3132–3158.

TRISTAN XI Symposium

Original abstract submittal