DASSCAN: A Density and Adjacency Expansion-Based Spatial Structural Community Detection Algorithm for Networks

Existing spatial community detection algorithms are usually modularity based. Motivated by different applications, these algorithms build appropriate spatial null models to describe spatial effects on the connection of nodes. Then, by choosing certain modularity maximizing strategies, they try to find interesting community structures hidden behind the null models. In this paper, a novel structural similarity-based spatial network community is defined, which is based on the shared neighbors of nodes. In addition, there are two other special node roles defined: the spatial hub and outlier. Then, a density and adjacency expansion-based spatial structural community detection algorithm for networks (DASSCAN) is proposed for mining these communities, hubs and outliers. DASSCAN uses structural similarity to measure the relationship between nodes, and then, structurally similar and spatially adjacent nodes are merged into communities using a density-based clustering method and spatial adjacency expansion strategy. Comparative experiments on two kinds of Chinese train line networks clarified the accuracy and efficiency of DASSCAN in finding the spatial structural communities, spatial hubs and outliers. The communities found can be used to uncover more interesting spatial structural patterns, and the hubs and outliers are more accurate and have more valuable meanings.