Detection of multi‐scale clusters in network space

Abstract

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.

Keywords:

• Clump
• Cluster detection
• Network
• Point pattern analysis

Acknowledgements

The authors greatly appreciate the input from Professor Atsuyuki Okabe in the early stage of the study. The authors are also indebted to three anonymous referees for their valuable comments. This study was supported in part by Grants‐in‐Aid for Scientific Research, Ministry of Education, Culture, Sports, Science and Technology, Japan.