King's College London

Research portal

Detection of multi-scale clusters in network space

Research output: Contribution to journalArticle

Shino Shiode, Narushige Shiode

Original languageEnglish
Pages (from-to)75-92
Number of pages18
JournalINTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
Volume23
Issue number1
DOIs
Publication statusPublished - 2009

King's Authors

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454