Clustering of heterogeneous networks with directional flows based on “Snake” similarities

• Clustering heterogeneously connected networks with directional flows and missing data.
• Identifying local connected components that minimize a heterogeneity index while forcing connectivity.
• Developing a ‘snake’ similarity metric to capture spatial correlations.
• Integrating Symmetric Nonnegative Matrix Factorization to unveil nonlinear hidden patterns in big data set.

Aggregated network level modeling and control of traffic in urban networks have recently gained a lot of interest due to unpredictability of travel behaviors and high complexity of physical modeling in microscopic level. Recent research has shown the existence of well-defined Macroscopic Fundamental Diagrams (MFDs) relating average flow and density in homogeneous networks. The concept of MFD allows to design real-time traffic control schemes specifically hierarchical perimeter control approaches to alleviate or postpone congestion. Considering the fact that congestion is spatially correlated in adjacent roads and it propagates spatiotemporaly with finite speed, describing the main pockets of congestion in a heterogeneous city with small number of clusters is conceivable. In this paper, we propose a three-step clustering algorithm to partition heterogeneous networks into connected homogeneous regions, which makes the application of perimeter control feasible. The advantages of the proposed method compared to the existing ones are the ability of finding directional congestion within a cluster, robustness with respect to parameters calibration, and its good performance for networks with low connectivity and missing data. Firstly, we start to find a connected homogeneous area around each road of the network in an iterative way (i.e. it forms a sequence of roads). Each sequence of roads, defined as ‘snake’, is built by starting from a single road and iteratively adding one adjacent road based on its similarity to join previously added roads in that sequence. Secondly, based on the obtained sequences from the first step, a similarity measure is defined between each pair of the roads in the network. The similarities are computed in a way that put more weight on neighboring roads and facilitate connectivity of the clusters. Finally, Symmetric Non-negative Matrix Factorization (SNMF) framework is utilized to assign roads to proper clusters with high intra-similarity and low inter-similarity. SNMF partitions the data by providing a lower rank approximation of the similarity matrix. The proposed clustering framework is applied in medium and large-size networks based on micro-simulation and empirical data from probe vehicles. In addition, the extension of the algorithm is proposed to deal with the networks with sparse measurements where information of some links is missing. The results show the effectiveness and robustness of the extended algorithm applied to simulated network under different penetration rates (percentage of links with data).