Topological Structure Matching Measure between Two Graphs. (June 2017)

• Record Type: Journal Article
• Authors: Jiang, Kai‐Zhong; Zheng, Zhong‐Tuan; Li, Lu
• Is Part Of: Computer-aided civil and infrastructure engineering. Volume 32:Number 6(2017:Jun.)
• Page Start: 515
• Page End: 524
• Publication Date: 2017-06
• Subjects: Civil engineering -- Data processing -- Periodicals; Computer-aided engineering -- Periodicals; 624.0285
• DOI: 10.1111/mice.12270
• Languages: English
• ISSNs: 1093-9687

Abstract

Abstract: There have been a plethora of algorithms and techniques for the one‐to‐one correspondence matching between two small graphs at the element level. However, it is a daunting task for large graphs. It is necessary to design an aggregate statistical measurement to measure the degree of matching at the coarse grained level between two large graphs. This work presents a novel contribution with the proposal of an aggregate statistical measurement of the matching between two large networks at the macro topological structure level. In the viewpoint of strategic planning application, decision makers want to know whether the road infrastructure network meets the traffic flow network at the macro level rather than the micro level. The macro topological structure of the graph is described by a partition of all the vertices by the singular value decomposition based on the weighted vertex‐path incidence matrix. The topological structure matching measurement (TSMM) of the two graphs is defined as the degree of similarity between two partitions. As a case study, the TSMM is considered between the road network and the traffic flow network for Shanghai. The result is 0.2129, which shows that the two networks mismatch to a certain degree. This, agreeing with the current situation of the traffic congestion in Shanghai, suggests the improvement in the urban traffic.