Spatial partitioning of large urban road networks

Tarique Anwar, Chengfei Liu, Hai L. Vu, Christopher Leckie

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

24 Citations (Scopus)


The rapid global migration of people towards urban areas is multiplying the traffic volume on urban road networks. As a result these networks are rapidly growing in size, in which different sub-networks exhibit distinctive traffic flow patterns. In this paper, we propose a scalable framework for traffic congestion-based spatial partitioning of large urban road networks. It aims to identify different sub-networks or partitions that exhibit homogeneous traffic congestion patterns internally, but heterogenous to others externally. To this end, we develop a two-stage procedure within our framework that first transforms the large road graph into a well-structured and condensed supergraph via clustering and link aggregation based on traffic density and adjacency connectivity, respectively. We then devise a spectral theory based novel graph cut (referred as α-Cut) to partition the supergraph and compare its performance with that of an existing method for partitioning urban networks. Our results show that the proposed method outperforms the normalized cut based existing method in all the performance evaluation metrics for small road networks and provides good results for much larger networks where other methods may face serious problems of time and space complexities.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2014
Subtitle of host publication17th International Conference on Extending Database Technology, Proceedings
Number of pages12
ISBN (Electronic)9783893180653
Publication statusPublished - 2014
Externally publishedYes
EventExtending Database Technology 2014 - Athens, Greece
Duration: 24 Mar 201428 Mar 2014
Conference number: 17th (Proceedings)


ConferenceExtending Database Technology 2014
Abbreviated titleEDBT 2014
OtherEDBT/ICDT 2014 Joint Conference
March 24-28, 2014 - Athens, Greece

EDBT: 17th International Conference on Extending Database Technology
ICDT: 17th International Conference on Database Theory,
Internet address


  • Graph partitioning
  • Road networks
  • Spectral clustering

Cite this