Detection of multi-scale clusters in network space

This paper proposes a new type of point-pattern analytical method, Network-Based Variable-Distance Clumping Method (NT-VCM), to analyse the distribution pattern of point objects and phenomena observed on a network. It is an extension of Planar Variable-Distance Clumping Method (PL-VCM) that was previously defined for point pattern analysis in Euclidian space. The purpose for developing NT-VCM is to identify point agglomerations across different scales called multi-scale network-based clumps among distributed points along a network. The paper first defines a network-based clump as a set of points where all its elements are found within a certain shortest-path distance from at least one other element of the same set. It then proposes NT-VCM as a technique to extract statistically significant multi-scale clumps on a network. The paper also proposes an efficient algorithm for computing NT-VCM, which involves the use of the Voronoi diagram, the Delaunay diagram and the minimum spanning tree that are adapted and newly extended for the purpose of analysis on a network. A comparative study of NT-VCM and PL-VCM using commercial facility data reveals a notable difference in the location as well as the size of the significant multi-scale clumps detected in the both cases. Results from the empirical study confirm that NT-VCM accounts for the actual network distance between the points, thus providing a more accurate description of point agglomerations along the network than PL-VCM does.