Detection of clusters and outlying nodes in spatial networks

ABSTRACT Construction of network clusters and identifying hub nodes from networks has attracted more and more attentions in spatial network analysis. In this paper, we proposed clustering algorithm and outlying node detection algorithm for spatial road network analysis. Network clustering algorithm consists of constructing clusters and creating a simplified structure of the network. When performing clustering on the network, we introduced the definitions of strong cluster and weak cluster, where each node has more connections within the cluster than with the rest of the graph, for achieving reliable and reasonable clusters. For users’ understanding the structure of the network, we constructed a simplified graph approximation of the network, whose nodes were representative nodes in clusters of the network, and edges were the connections between those representative nodes. In outlying n ode detection algorithm, a node is identified as an outlier, not because of its distribution different from that of other nodes but for its unexpected sta tistical information. Whether a node is an outlier or not is examined with centrality index. The larger the node has centrality indexes, the more probabilistically it may be identified as an outlier. The experime ntal results on artificial data sets demonstrated that two algorithms are very efficient and effective. Keywords: Spatial network, network Clustering, Outlying node detection