Skeleton Network Extraction and Analysis on Bicycle Sharing Networks

Introduction

In this Big Data era, enormous data modeled by complex networks has far exceeded the capability of most available technologies to interpret and analyze real-world networks appropriately. An increased volume of data creates a rise in the number of network connections and noisy information that makes a network’s structure highly complex. Additionally, the real-world networks in this century not only correspond to common data attributes but can also be broadened to spatial attributes. Such a network is known as a spatial network whose vertices and edges are associated with the spatial elements (Li, Wang, & Deyi, 2015). The extent of these issues expands on the difficulty in complex network analysis and visualization algorithms. These issues cause real networks more difficult to explore, characterize, and eventually make them more challenging to find practical uses for.

To overcome these issues, analyzing complex networks is recently under the discriminating network’s essential structure. Skeleton network extraction is an alternate solution to understanding the whole network’s functions from the abstracted backbone. It relies on the concept of minimizing large-scale networks while still preserves the essential information of the original network (Grady, Thiemann, & Brockmann, 2012). Thus, the extracted skeleton network can be used instead of investigating the entire network which is complex and computationally expensive.

The literature of skeleton network extraction has received attention in different approaches. Most research has proposed methods to deal with edge reduction scheme, for instance: edge weighting and thresholding (Zhang & Zhu, 2013), edge sampling (Blagus, Šubelj, & Bajec, 2015), statistical importance of links (Serrano, Boguna, & Vespignani, 2009), and unexpected noise connections (Coscia & Neffke, 2017). Nevertheless, the methods which are used to define criteria for the relevance of nodes are adopted unevenly. In geographical contexts, the efficient methods used are not only supposed to reduce the size of the spatial network but are also intended to preserve the key topology and spatial features (Dai, Derudder, & Liu, 2018). Although some of the existing methods can be applied in spatial networks, they are purely statistical, and this has negligible implications in a spatial sense. Moreover, the methods do not potentially be confirmed their effectiveness under the spatial factor. Disregarding spatial attributes embodied with nodes may lead to frustration in discovering meaningful insights from the extracted networks. For this reason, it requires specific skeleton network extraction methods that are sensitive to network topology and geography.

To demonstrate the methodology, this article focus on the bicycle sharing networks that typically allow users to take/return bicycles from/to automated docking stations (Zaltz Austwick, O’Brien, Strano, & Viana, 2013). Bicycle networks display characteristics of moving objects since the bicycle usages are related to specific locations and are updated overtime (Sultan, Tanier, & Safar, 2014). This fact makes skeletonizing process a complex proposition and leads this research to the following question: How would skeleton network extraction be influenced by the spatial attributes? Based on spatial attributes, the skeleton networks might be extracted appropriately. Inspired by this, the authors propose the hypothesis that a skeleton network could be constructed by a small portion of the important nodes which carry not only the topological information but also spatial information.

The main objectives of this article are as follows. First, the authors propose a skeleton network extraction method based on the spatial information of the nodes and their importance identified by algorithm. Second, this method is applied to explore the real-world bicycle sharing networks. The contributions are summarized as follows: